論文の概要: Dimension-Optimal Dynamic Regret in Exp-Concave Online Learning
- arxiv url: http://arxiv.org/abs/2610.20187v2
- Date: Mon, 19 Oct 2026 17:10:48 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-10-21 06:32:45.300565
- Title: Dimension-Optimal Dynamic Regret in Exp-Concave Online Learning
- Title（参考訳）: Exp-Concaveオンライン学習における次元最適動的レグレット
- Abstract要約: 我々は、未知の経路長に適応する$mathbbRd$のコンパクト凸部分集合上で、適切な情報学習者を開発する。
直径1のユークリッド球上の一致する下界は、$Tgtrsim d2$のときの対数係数までミニマックスフロンティアを確立する。
- 参考スコア（独自算出の注目度）: 43.561169894527005
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Tracking changing comparators is a central problem in online learning. For exp-concave losses, previous work established the $T^{1/3}P_T^{2/3}$ dependence on the horizon $T$ and Euclidean path length $P_T$ for fixed dimension, while the optimal cost of dimension remained unresolved. We resolve this question by establishing a sharp $d^{1/3}$ curved dimension factor, improving the $d^{2/3}$ factor of recent switching and interval reductions [1, 2]. To achieve this improvement, we develop a proper, full-information learner on compact convex subsets of $\mathbb{R}^d$ that adapts to the unknown path length and, under fixed dimension-independent diameter, gradient, and curvature parameters, guarantees $$\operatorname{Reg}_T(u_{1:T}) \le \widetilde{O}\left(d+\min\left\{d^{1/3}T^{1/3}P_T^{2/3},\sqrt{TP_T},T\right\}\right).$$ A matching lower bound on a diameter-one Euclidean ball establishes the minimax frontier up to logarithmic factors when $T\gtrsim d^2$, including the transition from the curved rate to larger path budgets. The lower bound already holds for losses that depend on only one coordinate per round, isolating an unavoidable cost of learning across directions. Our upper bound follows from square-root Gaussian KL control of comparator movement and a cancellation argument that pays for history restarts. The curved learner maintains $O(\log^2 T)$ Gaussian states, uses one gradient per round, and runs in time near-linear in $T$ under a Mahalanobis-projection oracle.
- Abstract（参考訳）: コンパレータの変更を追跡することは、オンライン学習において重要な問題である。
exp-concaveの損失に対して、以前の研究は水平線への依存$T^{1/3}P_T^{2/3}$と固定次元に対するユークリッドパス長$P_T$を確立したが、次元の最適コストは未解決のままであった。
この問題は、鋭い$d^{1/3}$曲線次元因子を定め、最近のスイッチングとインターバル縮小の$d^{2/3}$因子を改善して解決する[1, 2]。
この改善を達成するために、未知の経路長に適応し、固定次元独立な直径、勾配、曲率パラメータの下で、$$\operatorname{Reg}_T(u_{1:T}) \le \widetilde{O}\left(d+\min\left\{d^{1/3}T^{1/3}P_T^{2/3},\sqrt{TP_T},T\right\right\right} のコンパクト凸部分集合上の適切な情報学習器を開発する。
直径1のユークリッド球上の下界に一致する$Aは、曲線速度からより大きな経路予算への遷移を含む、$T\gtrsim d^2$のときの対数係数までのミニマックスフロンティアを確立する。
ローバウンドは1ラウンド当たり1つの座標にのみ依存する損失をすでに保持しており、回避不可能な学習コストを回避している。
我々の上限は、二乗根ガウスKLによるコンパレータ運動の制御と、歴史のために支払うキャンセル引数から従う。
曲線学習者は、$O(\log^2 T)$ Gaussian状態を維持し、ラウンドごとに1つの勾配を使い、マハラノビス射影オラクルの下では、T$でほぼ直線的に走る。
関連論文リスト
- Parameter-Free Interval-Dynamic Regret under Heavy-Tailed Noise [55.29259818039367]
オンライン凸最適化を1ラウンドに1つの偏りのない下位段階と、未知の有限条件の雑音モーメントであるp$th, $1ple2$で検討する。
長さ$n$の固定区間$I$に対して、学習者は最適な全水平静的レートを含む1+log(T/n)$を達成する。
論文 参考訳（メタデータ） (2026-09-30T21:03:03Z) - Optimal Tradeoffs Between Network Size and Parameter Magnitude in Neural Approximation and Minimax Regression [12.592251634771314]
パラメータ等級は、両方の点において役割を定量化しなければならない別のリソースを提供する。
我々は1つの境界付き1ドルLipschitz Dyadic--Triangular Activationを用いて、一定の深さでシャープな幅-マグニチュードトレードオフを確立する。
これにより、単位パラメータ半径から固定ネットワークサイズまで、統計的に最適な選択の連続性が得られる。
論文 参考訳（メタデータ） (2026-09-22T05:28:37Z) - Constrained Online Learning with Noisy Constraint Values [55.29259818039367]
一般的な実現可能性の下では、我々のLEDGERアルゴリズムは、期待される損失$O(sqrt T)と期待される予算違反$O(sqrtTlog(eT))を達成します。
スレーター条件、フィードバックチャネル間の独立性、絶対的制約値境界は不要である。
論文 参考訳（メタデータ） (2026-09-07T01:38:41Z) - Nonstationary Generalized Linear Bandits with Discounted Online Mirror Descent [39.805192541498634]
本研究では,非定常線形計算(GLBs)について検討し,期待される報酬を未知の時間変化パラメータを持つ非線形リンク関数を用いてモデル化する。
本稿では,パラメータ推定に割引オンラインミラー降下(DOMD)を利用する非定常GLBに対する新しいアルゴリズムを提案する。
論文 参考訳（メタデータ） (2026-05-25T08:40:32Z) - Tight Bounds for Logistic Regression with Large Stepsize Gradient Descent in Low Dimension [36.3266119975955]
分離可能なデータを用いた二項分類のための線形モデルを訓練するために、降下によるロジスティック勾配を最小化する最適化問題を考察する。
十分な学習率を持つGDが$mathcalO (1/(T))$よりも小さく、$T geq (n/+ 1/2)$の場合、$n$はデータセットサイズであることを示す。
論文 参考訳（メタデータ） (2026-02-12T22:58:18Z) - Improved Algorithm for Adversarial Linear Mixture MDPs with Bandit
Feedback and Unknown Transition [71.33787410075577]
線形関数近似,未知遷移,および逆損失を用いた強化学習について検討した。
我々は高い確率で$widetildeO(dsqrtHS3K + sqrtHSAK)$ regretを実現する新しいアルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-03-07T15:03:50Z) - On the $O(\frac{\sqrt{d}}{T^{1/4}})$ Convergence Rate of RMSProp and Its Momentum Extension Measured by $\ell_1$ Norm [54.28350823319057]
本稿では、RMSPropとその運動量拡張を考察し、$frac1Tsum_k=1Tの収束速度を確立する。
我々の収束率は、次元$d$を除くすべての係数に関して下界と一致する。
収束率は$frac1Tsum_k=1Tと類似していると考えられる。
論文 参考訳（メタデータ） (2024-02-01T07:21:32Z) - Variance-Aware Confidence Set: Variance-Dependent Bound for Linear
Bandits and Horizon-Free Bound for Linear Mixture MDP [76.94328400919836]
線形バンドイットと線形混合決定プロセス(mdp)に対する分散認識信頼セットの構築方法を示す。
線形バンドイットに対しては、$d を特徴次元とする$widetildeo(mathrmpoly(d)sqrt1 + sum_i=1ksigma_i2) が成り立つ。
線形混合 MDP に対し、$widetildeO(mathrmpoly(d)sqrtK)$ regret bound を得る。
論文 参考訳（メタデータ） (2021-01-29T18:57:52Z) - Large-time asymptotics in deep learning [0.0]
トレーニングにおける最終時間の$T$(対応するResNetの深さを示す可能性がある)の影響について検討する。
古典的な$L2$-正規化経験的リスク最小化問題に対して、トレーニングエラーが$mathcalOleft(frac1Tright)$のほとんどであることを示す。
$ellp$-距離損失の設定において、トレーニングエラーと最適パラメータの両方が$mathcalOleft(e-mu)の順序のほとんどであることを示す。
論文 参考訳（メタデータ） (2020-08-06T07:33:17Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。