論文の概要: Gradient-Variation Regret Bounds for Unconstrained Online Learning
- arxiv url: http://arxiv.org/abs/2604.11151v1
- Date: Mon, 13 Apr 2026 08:14:37 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-04-14 20:13:16.420127
- Title: Gradient-Variation Regret Bounds for Unconstrained Online Learning
- Title（参考訳）: 制約のないオンライン学習のための勾配変動レグレクト境界
- Authors: Yuheng Zhao, Andrew Jacobsen, Nicolò Cesa-Bianchi, Peng Zhao,
- Abstract要約: 我々は、未制約オンライン学習のためのパラメータフリーアルゴリズムを後悔せずに開発する。
L$-smooth convex loss に対して、完全適応的アルゴリズムを提供し、次数 $widetildeO(|u|sqrtV_T(u) + L|u|2+G4)$ をノルム $|u|$, Lipschitz constant $G$, smoothness $L$ の事前の知識を必要としない。
- 参考スコア（独自算出の注目度）: 27.020402628254917
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We develop parameter-free algorithms for unconstrained online learning with regret guarantees that scale with the gradient variation $V_T(u) = \sum_{t=2}^T \|\nabla f_t(u)-\nabla f_{t-1}(u)\|^2$. For $L$-smooth convex loss, we provide fully-adaptive algorithms achieving regret of order $\widetilde{O}(\|u\|\sqrt{V_T(u)} + L\|u\|^2+G^4)$ without requiring prior knowledge of comparator norm $\|u\|$, Lipschitz constant $G$, or smoothness $L$. The update in each round can be computed efficiently via a closed-form expression. Our results extend to dynamic regret and find immediate implications to the stochastically-extended adversarial (SEA) model, which significantly improves upon the previous best-known result [Wang et al., 2025].
- Abstract（参考訳）: V_T(u) = \sum_{t=2}^T \|\nabla f_t(u)-\nabla f_{t-1}(u)\|^2$。
L$-smooth convex loss に対して、完全適応的なアルゴリズムを提供し、次数 $\widetilde{O}(\|u\|\sqrt{V_T(u)} + L\|u\|^2+G^4)$ を、コンパレータノルム $\|u\|$, Lipschitz constant $G$, smoothness $L$ の事前の知識を必要としない。
各ラウンドの更新はクローズドフォーム式によって効率的に計算できる。
以上の結果から,従来の最もよく知られた結果 (Wang et al , 2025) を大きく改善する確率的拡張対位法 (SEA) モデルへの即時的影響が示唆された。
関連論文リスト
- Adaptivity and Universality: Problem-dependent Universal Regret for Online Convex Optimization [64.88607416000376]
普遍性と適応性の両方を達成する新しいアプローチであるUniGradを紹介し、UniGrad.CorrectとUniGrad.Bregmanの2つの異なる実現法を提案する。
どちらのメソッドも勾配の変動に適応し、強い凸関数に対する $mathcalO(log V_T)$ regret とexp-concave関数に対する $mathcalO(d log V_T)$ regret を同時に達成する。
論文 参考訳（メタデータ） (2025-11-25T05:23:10Z) - 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) - 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) - Logarithmic Regret from Sublinear Hints [76.87432703516942]
自然クエリモデルにより,アルゴリズムが$O(log T)$ regretsを$O(sqrtT)$ hintsで得ることを示す。
また、$o(sqrtT)$ hintsは$Omega(sqrtT)$ regretより保証できないことも示しています。
論文 参考訳（メタデータ） (2021-11-09T16:50:18Z) - 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) - Adaptive Online Learning with Varying Norms [45.11667443216861]
オンライン凸最適化アルゴリズムは、あるドメインで$w_t$を出力する。
この結果を用いて新しい「完全行列」型後悔境界を得る。
論文 参考訳（メタデータ） (2020-02-10T17:22:08Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。