論文の概要: Tracking a Small Set of Experts in Online Convex Optimization

• arxiv url: http://arxiv.org/abs/2610.20416v1
• Date: Wed, 14 Oct 2026 16:13:03 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-15 21:06:16.247385
• Title: Tracking a Small Set of Experts in Online Convex Optimization
• Title（参考訳）: オンライン凸最適化における少数の専門家の追跡
• Abstract要約: 非効率なアルゴリズムは、アクション空間を離散化し、ブーケ-ワーマスアルゴリズムを適用することで導出することができる。 この計算の非効率性は本質的にあり、情報理論と時間的後悔の分離が達成可能であることを示す。
• 参考スコア（独自算出の注目度）: 13.444168804680075
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: For the fundamental problem of prediction from expert advice, Freund asked whether one could compete with a comparator that switches $k$ times among only $m$ experts. For a discrete set of experts, this problem was resolved by Bousquet and Warmuth (2020), who gave an efficient algorithm with optimal regret matching the information-theoretic limit. We study the analogous problem in online convex optimization, where the action space is continuous. An inefficient algorithm can be derived by discretizing the action space and applying the Bousquet--Warmuth algorithm, giving regret of $\widetilde{O}(md+k)$, while the best known efficient algorithm for this problem has regret $\widetilde{O}(dk)$. We show that this computational inefficiency is inherent, establishing a separation between the information-theoretic and polynomial-time regret achievable for this problem. Specifically, under the hypergraphic planted-clique conjecture, we show that for every polynomial-time algorithm there exist instances for which it incurs at least $(k\sqrt d)^{1-o(1)}$ regret.
• Abstract（参考訳）: 専門家のアドバイスから予想される根本的な問題に対して、Freund氏は、わずか$m$の専門家の間で$k$倍の切り替えを行うコンパレータと競合できるかどうかを尋ねた。 Bousquet and Warmuth (2020) は、情報理論の限界に最適な後悔を伴う効率的なアルゴリズムを考案した。 本稿では,オンライン凸最適化における類似問題について検討する。 非効率的なアルゴリズムは、作用空間を離散化し、ブーケ=ワーマスアルゴリズムを適用して導出することができ、$\widetilde{O}(md+k)$を後悔する一方で、この問題の最もよく知られた効率的なアルゴリズムは$\widetilde{O}(dk)$を後悔する。 この計算の非効率性は本質的にあり、この問題に対して情報理論と多項式時間後悔を分離できることが示される。 具体的には,任意の多項式時間アルゴリズムに対して,少なくとも$(k\sqrt d)^{1-o(1)} を後悔する例が存在することを示す。

関連論文リスト

• Optimal Anytime Algorithms for Online Convex Optimization with Adversarial Constraints [7.798233121583888]
  本稿では,対向凸コスト関数の列を学習する問題に対して,任意のオンラインアルゴリズムを提案する。 提案アルゴリズムは,標準的な倍数化手法を使わずに最適な性能バウンダリを実現する。 我々のアルゴリズムは、$O(sqrtt)$ regret と $tildeO(sqrtt)$ cumulative constraint violation bounds for any $tgeq 1$。
  論文  参考訳（メタデータ） (2025-10-26T08:35:37Z)
• Differentially Private Algorithms for Graph Cuts: A Shifting Mechanism Approach and More [5.893651469750359]
  マルチウェイカットと最小$k$cutのためのエッジ微分プライベートアルゴリズムを導入する。 最小$k$-cut問題に対して、指数的メカニズムと近似$k$-cutの数の有界性を組み合わせた別のアプローチを用いる。
  論文  参考訳（メタデータ） (2024-07-09T14:46:33Z)
• Streaming Algorithms for Learning with Experts: Deterministic Versus Robust [62.98860182111096]
  エキスパート問題を伴うオンライン学習では、アルゴリズムは、T$day(または時間)ごとに結果を予測する必要がある。 目標は最小限のコストで予測を行うことだ。 最良専門家が$M$の誤りを犯したとき、後悔する$R$を達成するような決定論的アルゴリズムに対して、$widetildeOmegaleft(fracnMRTright)$の空間下界を示す。
  論文  参考訳（メタデータ） (2023-03-03T04:39:53Z)
• Private Online Prediction from Experts: Separations and Faster Rates [74.52487417350221]
  専門家によるオンライン予測は機械学習の基本的な問題であり、いくつかの研究がプライバシーの制約の下でこの問題を研究している。 本研究では,非適応的敵に対する最良な既存アルゴリズムの残差を克服する新たなアルゴリズムを提案し,解析する。
  論文  参考訳（メタデータ） (2022-10-24T18:40:19Z)
• Efficient and Optimal Algorithms for Contextual Dueling Bandits under Realizability [59.81339109121384]
  我々は,学習者が文脈情報を用いて2つの決定を下す連続的な決定設定であるK$コンテキストデュエルバンディット問題について検討するが,一方の判断が他方よりも優れていることを示唆する強調基準に基づくフィードバックのみを観察する。 提案手法は, 最善応答後悔という新たな概念に対して, 最善応答後悔に対する最適後悔率を実現するアルゴリズムである。
  論文  参考訳（メタデータ） (2021-11-24T07:14:57Z)
• Minimax Optimization with Smooth Algorithmic Adversaries [59.47122537182611]
  対戦相手が展開するスムーズなアルゴリズムに対して,Min-playerの新しいアルゴリズムを提案する。 本アルゴリズムは,制限周期のない単調進行を保証し,適切な勾配上昇数を求める。
  論文  参考訳（メタデータ） (2021-06-02T22:03:36Z)
• Near-Optimal Regret Bounds for Contextual Combinatorial Semi-Bandits with Linear Payoff Functions [53.77572276969548]
  我々は、C$2$UCBアルゴリズムが分割マトロイド制約に対して最適な後悔結合$tildeO(dsqrtkT + dk)$を有することを示した。 一般的な制約に対して,C$2$UCBアルゴリズムで腕の報酬推定値を変更するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-01-20T04:29:18Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。