論文の概要: On the Universal Near Optimality of Hedge in Combinatorial Settings

• arxiv url: http://arxiv.org/abs/2510.17099v1
• Date: Mon, 20 Oct 2025 02:05:22 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-10-25 00:56:39.28335
• Title: On the Universal Near Optimality of Hedge in Combinatorial Settings
• Title（参考訳）: 組合せ設定におけるヘッジの普遍的最適性について
• Authors: Zhiyuan Fan, Arnab Maiti, Kevin Jamieson, Lillian J. Ratliff, Gabriele Farina,
• Abstract要約: 任意の$X 部分集合 0,1d$ に対して、Hedge は、最大$sqrtlog d$ factor まで、ほぼ最適であり、$Omegabig(sqrtT log(|X|/log dbig)$ の下位境界を確立することによって示される。 また,DAGにおける最短パス問題に対する準最適正規化器も確立した。
• 参考スコア（独自算出の注目度）: 40.84925385308883
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this paper, we study the classical Hedge algorithm in combinatorial settings. In each round, the learner selects a vector $\boldsymbol{x}_t$ from a set $X \subseteq \{0,1\}^d$, observes a full loss vector $\boldsymbol{y}_t \in \mathbb{R}^d$, and incurs a loss $\langle \boldsymbol{x}_t, \boldsymbol{y}_t \rangle \in [-1,1]$. This setting captures several important problems, including extensive-form games, resource allocation, $m$-sets, online multitask learning, and shortest-path problems on directed acyclic graphs (DAGs). It is well known that Hedge achieves a regret of $O\big(\sqrt{T \log |X|}\big)$ after $T$ rounds of interaction. In this paper, we ask whether Hedge is optimal across all combinatorial settings. To that end, we show that for any $X \subseteq \{0,1\}^d$, Hedge is near-optimal--specifically, up to a $\sqrt{\log d}$ factor--by establishing a lower bound of $\Omega\big(\sqrt{T \log(|X|)/\log d}\big)$ that holds for any algorithm. We then identify a natural class of combinatorial sets--namely, $m$-sets with $\log d \leq m \leq \sqrt{d}$--for which this lower bound is tight, and for which Hedge is provably suboptimal by a factor of exactly $\sqrt{\log d}$. At the same time, we show that Hedge is optimal for online multitask learning, a generalization of the classical $K$-experts problem. Finally, we leverage the near-optimality of Hedge to establish the existence of a near-optimal regularizer for online shortest-path problems in DAGs--a setting that subsumes a broad range of combinatorial domains. Specifically, we show that the classical Online Mirror Descent (OMD) algorithm, when instantiated with the dilated entropy regularizer, is iterate-equivalent to Hedge, and therefore inherits its near-optimal regret guarantees for DAGs.
• Abstract（参考訳）: 本稿では,従来のHedgeアルゴリズムを組合せ設定で検討する。 各ラウンドにおいて、学習者は、集合 $X \subseteq \{0,1\}^d$ からベクトル $\boldsymbol{x}_t$ を選択し、完全な損失ベクトル $\boldsymbol{y}_t \mathbb{R}^d$ を観察し、損失 $\langle \boldsymbol{x}_t, \boldsymbol{y}_t \rangle \in [-1,1]$ を得る。 この設定は、広範囲なフォームゲーム、リソース割り当て、$m$-sets、オンラインマルチタスク学習、有向非巡回グラフ(DAG)上の最短パス問題など、いくつかの重要な問題を捉えている。 ヘッジは相互作用のラウンドの後に$O\big(\sqrt{T \log |X|}\big)$を後悔する。 本稿では,Hedgeがすべての組合せ設定において最適であるかどうかを問う。 その目的のために、任意の$X \subseteq \{0,1\}^d$ に対して、Hedge は特に、任意のアルゴリズムに持つ $\Omega\big(\sqrt{T \log(|X|)/\log d}\big)$ の下位境界を確立することにより、$\sqrt{\log d}$ factor- までほぼ最適であることを示す。 すると、結合集合の自然なクラス、すなわち、$m$-sets with $\log d \leq m \leq \sqrt{d}$-for this lower bound is tight, and that Hedge is Proprovably subtimal by a factor of $\sqrt{\log d}$ を同定する。 同時に、Hedgeは古典的な$K$-experts問題の一般化であるオンラインマルチタスク学習に最適であることを示す。 最後に、Hedgeのほぼ最適性を生かして、DAGにおけるオンライン最短パス問題に対する準最適正規化器の存在を確立する。 具体的には、拡張エントロピー正規化器でインスタンス化されると、古典的オンラインミラードライザー(OMD)アルゴリズムがHedgeと同値であり、DAGのほぼ最適後悔保証を継承することを示す。

関連論文リスト

• Actively Learning Halfspaces without Synthetic Data [34.777547976926456]
  我々は、点合成なしでハーフスペースを学習するための効率的なアルゴリズムを設計する。 コーナリーとして、軸整合半空間に対して最適な$O(d + log n)$クエリ決定論的学習器を得る。 我々のアルゴリズムはブール関数を$f$ over $n$要素で学習するより一般的な問題を解く。
  論文  参考訳（メタデータ） (2025-09-25T07:39:25Z)
• Efficient Near-Optimal Algorithm for Online Shortest Paths in Directed Acyclic Graphs with Bandit Feedback Against Adaptive Adversaries [34.38978643261337]
  本稿では,適応的相手に対する帯域フィードバックの下で,有向非巡回グラフ(DAG)における最短経路問題について検討する。 我々は,任意の適応的敵に対して高い確率で$tilde O(sqrt|E|Tlog |X|)$の最小限の最小残差を求めるアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2025-04-01T06:35:42Z)
• Sparsity-Based Interpolation of External, Internal and Swap Regret [4.753557469026313]
  本稿では,オンライン学習におけるエキスパート問題に焦点をあてる。 最適な$O(sqrtTlog d)$external regret bound when $dmathrmunif_phi=d$, the standard $tilde O(sqrtT)$ internal regret bound when $dmathrmself_phi=d-1$, and the optimal $tilde O(sqrtdT)$ swap regret bound in the worst case, we improve on existing algorithm in the intermediate regimes。
  論文  参考訳（メタデータ） (2025-02-06T22:47:52Z)
• Monge-Kantorovich Fitting With Sobolev Budgets [6.748324975906262]
  我々は、$rho$が$mtext-d$集合の近くに集中しているとき、これをノイズのあるデータを持つ多様体学習問題と解釈できることを示した。 Monge-Kantorovich $p$-cost $mathbbW_pp(rho, nu)$を介して$rho$を近似する際の$nu$のパフォーマンスを定量化し、$mathrmsupp nu$を$f : mathbbRmでカバーできるようにすることで複雑さを制限します。
  論文  参考訳（メタデータ） (2024-09-25T01:30:16Z)
• Optimal and Efficient Algorithms for Decentralized Online Convex Optimization [51.00357162913229]
  分散オンライン凸最適化(D-OCO)は、局所計算と通信のみを用いて、グローバルな損失関数の列を最小化するように設計されている。 我々は,凸関数と強凸関数の残差を$tildeO(nrho-1/4sqrtT)$と$tildeO(nrho-1/2log T)$に削減できる新しいD-OCOアルゴリズムを開発した。 我々の分析によると、射影自由多様体は$O(nT3/4)$と$O(n)を達成できる。
  論文  参考訳（メタデータ） (2024-02-14T13:44:16Z)
• Contextual Recommendations and Low-Regret Cutting-Plane Algorithms [49.91214213074933]
  本稿では、ナビゲーションエンジンやレコメンデーションシステムにおけるルーティングアプリケーションによって動機付けられた、コンテキスト線形帯域の次の変種について考察する。 我々は、真の点$w*$と分離オラクルが返す超平面の間の全距離を、低い「回帰」を持つ新しい切断平面アルゴリズムを設計する。
  論文  参考訳（メタデータ） (2021-06-09T05:39:05Z)
• Optimal Regret Algorithm for Pseudo-1d Bandit Convex Optimization [51.23789922123412]
  我々は,バンディットフィードバックを用いてオンライン学習を学習する。 learnerは、コスト/リワード関数が"pseudo-1d"構造を許可するゼロ次オラクルのみにアクセスできる。 我々は、$T$がラウンドの数である任意のアルゴリズムの後悔のために$min(sqrtdT、T3/4)$の下限を示しています。 ランダム化オンライングラデーション下降とカーネル化指数重み法を組み合わせた新しいアルゴリズムsbcalgを提案し,疑似-1d構造を効果的に活用する。
  論文  参考訳（メタデータ） (2021-02-15T08:16:51Z)
• Taking a hint: How to leverage loss predictors in contextual bandits? [63.546913998407405]
  我々は,損失予測の助けを借りて,文脈的包帯における学習を研究する。 最適な後悔は$mathcalO(minsqrtT, sqrtmathcalETfrac13)$である。
  論文  参考訳（メタデータ） (2020-03-04T07:36:38Z)
• Agnostic Q-learning with Function Approximation in Deterministic Systems: Tight Bounds on Approximation Error and Sample Complexity [94.37110094442136]
  本稿では,決定論的システムにおける関数近似を用いたQ$学習の問題について検討する。 もし$delta = Oleft(rho/sqrtdim_Eright)$なら、$Oleft(dim_Eright)$を使って最適なポリシーを見つけることができる。
  論文  参考訳（メタデータ） (2020-02-17T18:41:49Z)

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

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