論文の概要: Partially Lazy Gradient Descent for Smoothed Online Learning

• arxiv url: http://arxiv.org/abs/2601.15984v1
• Date: Thu, 22 Jan 2026 14:05:08 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-01-23 21:37:20.618559
• Title: Partially Lazy Gradient Descent for Smoothed Online Learning
• Title（参考訳）: Smoothed Online Learningのための部分遅延グラディエントDescent
• Authors: Naram Mhaisen, George Iosifidis,
• Abstract要約: $k$-lazyGDは、greedy Online Gradient Descent(OGD)とlazy GD/Dual-averaging($k=T$)のギャップを埋める このスペクトルをSmoothed Online Convex Optimization (SOCO) で解析し、学習者が打つコストと運動コストの両方を発生させる。
• 参考スコア（独自算出の注目度）: 8.708728702853966
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We introduce $k$-lazyGD, an online learning algorithm that bridges the gap between greedy Online Gradient Descent (OGD, for $k=1$) and lazy GD/dual-averaging (for $k=T$), creating a spectrum between reactive and stable updates. We analyze this spectrum in Smoothed Online Convex Optimization (SOCO), where the learner incurs both hitting and movement costs. Our main contribution is establishing that laziness is possible without sacrificing hitting performance: we prove that $k$-lazyGD achieves the optimal dynamic regret $\mathcal{O}(\sqrt{(P_T+1)T})$ for any laziness slack $k$ up to $Θ(\sqrt{T/P_T})$, where $P_T$ is the comparator path length. This result formally connects the allowable laziness to the comparator's shifts, showing that $k$-lazyGD can retain the inherently small movements of lazy methods without compromising tracking ability. We base our analysis on the Follow the Regularized Leader (FTRL) framework, and derive a matching lower bound. Since the slack depends on $P_T$, an ensemble of learners with various slacks is used, yielding a method that is provably stable when it can be, and agile when it must be.
• Abstract（参考訳）: 私たちは、greedy Online Gradient Descent(OGD、$k=1$)とlazy GD/dual-averaging($k=T$)のギャップを埋めるオンライン学習アルゴリズムである$k$-lazyGDを紹介します。 このスペクトルをSmoothed Online Convex Optimization (SOCO) で解析し、学習者が打つコストと運動コストの両方を発生させる。 k$-lazyGDが最適な動的後悔を達成できることを証明します $\mathcal{O}(\sqrt{(P_T+1)T})$ for any laziness slack $k$ up to $ (\sqrt{T/P_T})$, ここで$P_T$はコンパレータパス長です。 この結果はコンパレータのシフトに許容される遅延性を正式に結合し、$k$-lazyGDはトラッキング能力を損なうことなく遅延メソッドの本質的に小さな動きを維持できることを示した。 我々は、FTRL(Follow the Regularized Leader)フレームワークに基づいて分析を行い、一致した下位境界を導出します。 slackは$P_T$に依存するため、様々なスラックスを持つ学習者のアンサンブルが使用され、可能であれば確実に安定し、必要であればアジャイルになる。

関連論文リスト

• 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)
• Online Inverse Linear Optimization: Efficient Logarithmic-Regret Algorithm, Robustness to Suboptimality, and Lower Bound [25.50155563108198]
  ラウンド単位の複雑さが$T$に依存しない最初の対数-回帰法を提案する。 我々の方法は極めて単純であり、オンラインニュートンステップ(ONS)を適切なexp-concave損失関数に適用する。 また、$Omega(n)$ の下限を示し、$O(nln T)$ 境界が $O(ln T)$ 係数まで固であることを示す。
  論文  参考訳（メタデータ） (2025-01-24T09:19:15Z)
• The Optimization Landscape of SGD Across the Feature Learning Strength [102.1353410293931]
  オンライントレーニング環境で、さまざまなモデルやデータセットに$gamma$をスケーリングする効果について検討する。 最適なオンラインパフォーマンスは、しばしば大きな$gamma$で見られます。 以上の結果から,大容量ガンマ$限界の解析的研究は,実演モデルにおける表現学習のダイナミクスに関する有用な知見をもたらす可能性が示唆された。
  論文  参考訳（メタデータ） (2024-10-06T22:30:14Z)
• Non-stationary Delayed Online Convex Optimization: From Full-information to Bandit Setting [71.82716109461967]
  遅延勾配が利用できる全情報ケースに対して Mild-OGD というアルゴリズムを提案する。 ミルド-OGDのダイナミックな後悔は、順番の仮定の下で$O(sqrtbardT(P_T+1))$で自動的に束縛されることを示す。 Mild-OGDのバンディット版も開発し,損失値の遅れのみを考慮に入れた,より困難なケースについて検討した。
  論文  参考訳（メタデータ） (2023-05-20T07:54:07Z)
• Horizon-Free and Variance-Dependent Reinforcement Learning for Latent Markov Decision Processes [62.90204655228324]
  我々は,後期マルコフ決定過程(LMDP)における強化学習(RL)の文脈を考慮した後悔の最小化について検討した。 我々は,モデル最適化と値最適化の両手法でインスタンス化できる,新しいモデルベースアルゴリズムフレームワークを設計する。
  論文  参考訳（メタデータ） (2022-10-20T21:32:01Z)

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

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