論文の概要: Small Gradient Norm Regret for Online Convex Optimization
- arxiv url: http://arxiv.org/abs/2601.13519v1
- Date: Tue, 20 Jan 2026 02:11:01 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-01-21 22:47:23.119292
- Title: Small Gradient Norm Regret for Online Convex Optimization
- Title（参考訳）: オンライン凸最適化のための小さなグラディエントノルムレグレット
- Authors: Wenzhi Gao, Chang He, Madeleine Udell,
- Abstract要約: 我々は、$Gstar$後悔は、既存の$Lstar$(小さな損失)後悔を厳しく洗練させることを示した。
結果をダイナミックな後悔と盗賊の設定にまで拡張します。
- 参考スコア（独自算出の注目度）: 19.699405661554845
- License: http://creativecommons.org/licenses/by-nc-sa/4.0/
- Abstract: This paper introduces a new problem-dependent regret measure for online convex optimization with smooth losses. The notion, which we call the $G^\star$ regret, depends on the cumulative squared gradient norm evaluated at the decision in hindsight $\sum_{t=1}^T \|\nabla \ell(x^\star)\|^2$. We show that the $G^\star$ regret strictly refines the existing $L^\star$ (small loss) regret, and that it can be arbitrarily sharper when the losses have vanishing curvature around the hindsight decision. We establish upper and lower bounds on the $G^\star$ regret and extend our results to dynamic regret and bandit settings. As a byproduct, we refine the existing convergence analysis of stochastic optimization algorithms in the interpolation regime. Some experiments validate our theoretical findings.
- Abstract（参考訳）: 本稿では,スムーズな損失を伴うオンライン凸最適化のための問題依存的後悔尺度を提案する。
G^\star$ regret という概念は、後述の $\sum_{t=1}^T \|\nabla \ell(x^\star)\|^2$ における決定において評価される累積二乗勾配ノルムに依存する。
G^\star$ 後悔は、既存の$L^\star$ (小さな損失) 後悔を厳格に洗練し、損失が後続の判断で曲率を消失した場合、それを任意に鋭くすることができることを示す。
我々は、$G^\star$の後悔に対する上限と下限を確立し、その結果を動的後悔と盗賊の設定にまで拡張する。
副産物として、補間系における確率最適化アルゴリズムの既存の収束解析を洗練する。
いくつかの実験は、我々の理論的な結果を検証する。
関連論文リスト
- Scale-Invariant Regret Matching and Online Learning with Optimal Convergence: Bridging Theory and Practice in Zero-Sum Games [60.871651115241406]
ゼロサムゲームにおける理論と実践の間、何十年にもわたってかなりのシャズムが一階法によって浸食されてきた。
我々は、IREG-PRM$+$と呼ぶPRM$+$の新しいスケール不変かつパラメータフリーな変種を提案する。
ベンチマークゲームでは, PRM$+$と同等でありながら, 最適収束保証を$T-1/2$, $T-1$とする。
論文 参考訳（メタデータ） (2025-10-06T00:33:20Z) - Exploiting Curvature in Online Convex Optimization with Delayed Feedback [6.390468088226495]
曲面損失と遅延フィードバックを用いたオンライン凸最適化問題について検討する。
次数$minsigma_maxln T, sqrtd_mathrmtot$を後悔する規則化リーダの変種を提案する。
次に、exp-concave損失を検討し、適応的な学習率チューニングで遅延を処理するためにOnline Newton Stepアルゴリズムを拡張した。
論文 参考訳（メタデータ） (2025-06-09T09:49:54Z) - Improved Regret for Bandit Convex Optimization with Delayed Feedback [50.46856739179311]
遅延フィードバックを伴うバンド凸最適化(BCO)。
我々は,新しいアルゴリズムを開発し,一般にO(sqrtnT3/4+sqrtdT)$の後悔境界を満足していることを証明する。
提案アルゴリズムは,強い凸関数に対して$O((nT)2/3log/3T+dlog T)$に制限された後悔を改善することができることを示す。
論文 参考訳（メタデータ） (2024-02-14T13:08:26Z) - Horizon-Free and Variance-Dependent Reinforcement Learning for Latent
Markov Decision Processes [62.90204655228324]
我々は,後期マルコフ決定過程(LMDP)における強化学習(RL)の文脈を考慮した後悔の最小化について検討した。
我々は,モデル最適化と値最適化の両手法でインスタンス化できる,新しいモデルベースアルゴリズムフレームワークを設計する。
論文 参考訳（メタデータ） (2022-10-20T21:32:01Z) - Lazy OCO: Online Convex Optimization on a Switching Budget [34.936641201844054]
我々は、オンライン凸最適化の変形について研究し、プレイヤーは、T$ラウンドを通して、最大$S$で決定を切り替えることを許されている。
離散的な決定セットの事前の作業や、より最近の連続的な設定では、適応的な逆数でのみ、同様の問題が解決されている。
論文 参考訳（メタデータ） (2021-02-07T14:47:19Z) - Projection-free Online Learning over Strongly Convex Sets [24.517908972536432]
我々は,強い凸集合に対するオンライン学習の特別な事例について検討し,OWが一般凸集合の損失に対して$O(T2/3)$よりも良い後悔の限界を享受できることを最初に証明した。
一般凸集合に対する$O(sqrtT)$の後悔境界と強凸集合に対する$O(sqrtT)$の後悔境界を達成することを示す。
論文 参考訳（メタデータ） (2020-10-16T05:42:50Z) - Naive Exploration is Optimal for Online LQR [49.681825576239355]
最適後悔尺度は$widetildeTheta(sqrtd_mathbfu2 d_mathbfx T)$で、$T$は時間ステップの数、$d_mathbfu$は入力空間の次元、$d_mathbfx$はシステム状態の次元である。
我々の下界は、かつての$mathrmpoly(logT)$-regretアルゴリズムの可能性を排除する。
論文 参考訳（メタデータ） (2020-01-27T03:44:54Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。