論文の概要: Alternating Regret for Online Convex Optimization

• arxiv url: http://arxiv.org/abs/2502.12529v1
• Date: Tue, 18 Feb 2025 04:32:52 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-02-19 14:06:25.083959
• Title: Alternating Regret for Online Convex Optimization
• Title（参考訳）: オンライン凸最適化のための代替レグレット
• Authors: Soumita Hait, Ping Li, Haipeng Luo, Mengxiao Zhang,
• Abstract要約: 連続Hedgeアルゴリズムは,任意の逆数$次元OCO問題に対して,$tildemathcalO(dfrac23Tfrac13)$の繰り返し後悔を実現することを示す。 例えば、Regret Matching 変種に対する$Omega(sqrtT)$ lower boundなどである。
• 参考スコア（独自算出の注目度）: 43.12477663757647
• License:
• Abstract: Motivated by alternating learning dynamics in two-player games, a recent work by Cevher et al.(2024) shows that $o(\sqrt{T})$ alternating regret is possible for any $T$-round adversarial Online Linear Optimization (OLO) problem, and left as an open question whether the same is true for general Online Convex Optimization (OCO). We answer this question in the affirmative by showing that the continuous Hedge algorithm achieves $\tilde{\mathcal{O}}(d^{\frac{2}{3}}T^{\frac{1}{3}})$ alternating regret for any adversarial $d$-dimensional OCO problems. We show that this implies an alternating learning dynamic that finds a Nash equilibrium for any convex-concave zero-sum games or a coarse correlated equilibrium for any convex two-player general-sum games at a rate of $\tilde{\mathcal{O}}(d^{\frac{2}{3}}/T^{\frac{2}{3}})$. To further improve the time complexity and/or the dimension dependence, we propose another simple algorithm, Follow-the-Regularized-Leader with a regularizer whose convex conjugate is 3rd-order smooth, for OCO with smooth and self-concordant loss functions (such as linear or quadratic losses). We instantiate our algorithm with different regularizers and show that, for example, when the decision set is the $\ell_2$ ball, our algorithm achieves $\tilde{\mathcal{O}}(T^{\frac{2}{5}})$ alternating regret with no dimension dependence (and a better $\tilde{\mathcal{O}}(T^{\frac{1}{3}})$ bound for quadratic losses). We complement our results by showing some algorithm-specific alternating regret lower bounds, including a somewhat surprising $\Omega(\sqrt{T})$ lower bound for a Regret Matching variant that is widely used in alternating learning dynamics.
• Abstract（参考訳）: Cevher et al (2024) による最近の研究によると、$o(\sqrt{T})$ alternating regret は任意の$T$ラウンド逆オンライン線形最適化 (OLO) 問題に対して可能であり、一般オンライン凸最適化 (OCO) に対して同じことが正しいかどうかというオープンな疑問として残されている。 この問題は、連続 Hedge アルゴリズムが $\tilde{\mathcal{O}}(d^{\frac{2}{3}}T^{\frac{1}{3}})$ 逆の $d$-dimensional OCO 問題に対する繰り返し後悔を達成できることを示して、肯定的に答える。 これは、任意の凸凸零サムゲームに対するナッシュ平衡や、任意の凸凸2プレーヤ一般サムゲームに対する粗相関平衡を$\tilde{\mathcal{O}}(d^{\frac{2}{3}}/T^{\frac{2}{3}})$で求める交互学習力学を意味する。 さらに時間複雑性と次元依存性を改善するために、線形や二次損失のような滑らかで自己一致の損失関数を持つOCOに対して、凸共役が3次滑らかな正則化器を備えたFollow-the-Regularized-Leaderを提案する。 アルゴリズムを異なる正規化器でインスタンス化し、例えば、決定セットが$\ell_2$ ballであるとき、我々のアルゴリズムは、次元依存のない後悔を繰り返す$\tilde{\mathcal{O}}(T^{\frac{2}{5}})$$(およびより良い$\tilde{\mathcal{O}}(T^{\frac{1}{3}})$)$2次損失のバウンドを達成することを示す。 例えば、学習力学の交互化に広く用いられるRegret Matching variantに対する$\Omega(\sqrt{T})$ lower bound などである。

関連論文リスト

• Towards Optimal Regret in Adversarial Linear MDPs with Bandit Feedback [30.337826346496385]
  線形マルコフ決定過程におけるオンライン強化学習について,敵対的損失と帯域幅フィードバックを用いて検討した。 既存の手法と比較して、後悔性能を向上させるアルゴリズムを2つ導入する。
  論文  参考訳（メタデータ） (2023-10-17T19:43:37Z)
• Projection-free Online Exp-concave Optimization [21.30065439295409]
  LOOをベースとしたONSスタイルのアルゴリズムを提案する。これは全体$O(T)$コールを使用して,$widetildeO(n2/3T2/3)$でバウンドされた最悪のケースを保証します。 我々のアルゴリズムは、重要かつ確実な低次元データシナリオにおいて最も興味深い。
  論文  参考訳（メタデータ） (2023-02-09T18:58:05Z)
• Optimal Dynamic Regret in LQR Control [23.91519151164528]
  我々は、LQR制御という2次的損失の連続を伴う非確率的制御の問題を考察する。 我々は、$tildeO(textmaxn1/3 MathcalTV(M_1:n)2/3, 1)$の最適動的(政治的)後悔を実現するオンラインアルゴリズムを提供する。
  論文  参考訳（メタデータ） (2022-06-18T18:00:21Z)
• Near-Optimal Learning of Extensive-Form Games with Imperfect Information [54.55092907312749]
  本稿では,2プレイヤーゼロサムゲームにおいて,$widetildemathcalO((XA+YB)/varepsilon2)$プレイのエピソードのみを必要とするアルゴリズムの最初の行を,$varepsilon$-approximate Nash平衡を求める。 これにより$widetildemathcalO((X2A+Y2B)/varepsilon2)$が$widetildemathcalO(maxX,
  論文  参考訳（メタデータ） (2022-02-03T18:18:28Z)
• 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)
• Revisiting Smoothed Online Learning [70.09792747315323]
  オンライン学習者がヒットコストとスイッチングコストの両方に苦しむスムーズなオンライン学習の問題を調査します。 競争比を縛るために、各ラウンドで打つコストが学習者に知られていると仮定し、打つコストと切り換えコストの重み付け合計を単純に最小化する勾配アルゴリズムを調査します。
  論文  参考訳（メタデータ） (2021-02-13T14:15:55Z)
• Near-Optimal Reinforcement Learning with Self-Play [50.29853537456737]
  我々は,直接の監督なしに自己対決で最適な政策を学習するセルフプレイアルゴリズムに焦点をあてる。 本稿では,サンプル複雑性を$tildemathcalO(SAB)$,サンプル複雑性を$tildemathcalO(S(A+B)$とする新しいemphNash Vラーニングアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-06-22T05:00:13Z)
• Taking a hint: How to leverage loss predictors in contextual bandits? [63.546913998407405]
  我々は,損失予測の助けを借りて,文脈的包帯における学習を研究する。 最適な後悔は$mathcalO(minsqrtT, sqrtmathcalETfrac13)$である。
  論文  参考訳（メタデータ） (2020-03-04T07:36:38Z)

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

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