Fugu-MT 論文翻訳(概要): A Simple, Optimal and Efficient Algorithm for Online Exp-Concave Optimization

論文の概要: A Simple, Optimal and Efficient Algorithm for Online Exp-Concave Optimization

arxiv url: http://arxiv.org/abs/2512.23190v1
Date: Mon, 29 Dec 2025 03:59:51 GMT
ステータス: 翻訳完了
システム内更新日: 2025-12-30 22:37:30.402026
Title: A Simple, Optimal and Efficient Algorithm for Online Exp-Concave Optimization
Title（参考訳）: オンラインExp-Concave最適化のための単純・最適・効率的なアルゴリズム
Authors: Yi-Han Wang, Peng Zhao, Zhi-Hua Zhou,
Abstract要約: オンラインニュートンステップ(ONS)はオンライン学習における基本的な問題である。 ONSは、各ラウンドにおけるマハラノビス予想のために計算ボトルネックに直面している。本稿では,O(normd2 T + dsqrtTlog)を最適に保ちつつ,全ランタイムを$O(normd2 T + dsqrtTlog)に減らしたONS,LightONSを提案する。この設計により、より広いシナリオにおいて、LightONSはONSの効率的なプラグイン代替として機能する。
参考スコア（独自算出の注目度）: 72.1530234801628
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: Online eXp-concave Optimization (OXO) is a fundamental problem in online learning. The standard algorithm, Online Newton Step (ONS), balances statistical optimality and computational practicality, guaranteeing an optimal regret of $O(d \log T)$, where $d$ is the dimension and $T$ is the time horizon. ONS faces a computational bottleneck due to the Mahalanobis projections at each round. This step costs $Ω(d^ω)$ arithmetic operations for bounded domains, even for the unit ball, where $ω\in (2,3]$ is the matrix-multiplication exponent. As a result, the total runtime can reach $\tilde{O}(d^ωT)$, particularly when iterates frequently oscillate near the domain boundary. For Stochastic eXp-concave Optimization (SXO), computational cost is also a challenge. Deploying ONS with online-to-batch conversion for SXO requires $T = \tilde{O}(d/ε)$ rounds to achieve an excess risk of $ε$, and thereby necessitates an $\tilde{O}(d^{ω+1}/ε)$ runtime. A COLT'13 open problem posed by Koren [2013] asks for an SXO algorithm with runtime less than $\tilde{O}(d^{ω+1}/ε)$. This paper proposes a simple variant of ONS, LightONS, which reduces the total runtime to $O(d^2 T + d^ω\sqrt{T \log T})$ while preserving the optimal $O(d \log T)$ regret. LightONS implies an SXO method with runtime $\tilde{O}(d^3/ε)$, thereby answering the open problem. Importantly, LightONS preserves the elegant structure of ONS by leveraging domain-conversion techniques from parameter-free online learning to introduce a hysteresis mechanism that delays expensive Mahalanobis projections until necessary. This design enables LightONS to serve as an efficient plug-in replacement of ONS in broader scenarios, even beyond regret minimization, including gradient-norm adaptive regret, parametric stochastic bandits, and memory-efficient online learning.
Abstract（参考訳）: オンラインeXp-concave Optimization(OXO)はオンライン学習における基本的な問題である。標準アルゴリズムであるOnline Newton Step (ONS) は、統計的最適性と計算的実用性のバランスをとり、$O(d \log T)$の最適後悔を保証する。 ONSは、各ラウンドにおけるマハラノビス予想のために計算ボトルネックに直面している。このステップは、$ω\in (2,3]$が行列乗法指数である単位球であっても、有界領域に対する$Ω(d^ω)$算術演算である。その結果、総ランタイムは$\tilde{O}(d^ωT)$に到達し、特にドメイン境界付近で頻繁に振動する。 Stochastic eXp-concave Optimization (SXO) では、計算コストも課題である。 SXO のオンラインバッチ変換で ONS をデプロイするには、$T = \tilde{O}(d/ε)$ ラウンドが必要であり、これにより$\tilde{O}(d^{ω+1}/ε)$ ランタイムが必要になる。 Koren [2013] が提起した COLT'13 の開問題では、ランタイムが $\tilde{O}(d^{ω+1}/ε)$ 未満の SXO アルゴリズムが要求される。本稿では,O(d^2 T + d^ω\sqrt{T \log T})$に対して,最適な$O(d \log T)$後悔を保ちながら,O(d^2 T + d^ω\sqrt{T \log T})$に減らしたONS,LightONSの簡単な変種を提案する。 LightONS はランタイム $\tilde{O}(d^3/ε)$ の SXO メソッドを意味する。重要なことに、LightONSはパラメータフリーオンライン学習からドメイン変換技術を活用することでONSのエレガントな構造を保ち、高価なマハラノビス投影を必要に応じて遅らせるヒステリシス機構を導入する。この設計により、LightONSは、勾配ノルム適応的後悔、パラメトリック確率的盗聴、メモリ効率のよいオンライン学習を含む、後悔の最小化を超えて、より広いシナリオにおいて、より効率的なONSのプラグイン代替として機能することができる。

論文の概要: A Simple, Optimal and Efficient Algorithm for Online Exp-Concave Optimization

関連論文リスト