論文の概要: Large-Step Last-Iterate Convergence of Random-Reshuffling Stochastic Gradient Descent
- arxiv url: http://arxiv.org/abs/2610.19444v1
- Date: Wed, 14 Oct 2026 02:34:06 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-10-16 12:10:45.443709
- Title: Large-Step Last-Iterate Convergence of Random-Reshuffling Stochastic Gradient Descent
- Title（参考訳）: ランダムリシャッフル確率勾配の大規模最終Iterate収束
- Abstract要約: 制約のない問題に対する標準RR-SGDの最終繰り返しに対する目的ゲップバウンダリを提案する。
ステップサイズ制限から、明示的な1/n$係数を取り除きます。
この結果は,対数因子までの平均収束率と一致した。
- 参考スコア（独自算出の注目度）: 17.131069269126776
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Random reshuffling stochastic gradient descent (RR-SGD) is widely used for finite-sum optimization in machine learning. For convex $L$-smooth components, recent work establishes convergence guarantees for an averaged iterate with component stepsizes as large as order $1/L$. However, the final iterate is a natural output in practice, and existing last-iterate guarantees in this setting require stepsizes that scale inversely with the number of components $n$. We establish an expected objective-gap bound for the last iterate of standard RR-SGD on unconstrained problems with a constant component stepsize satisfying $0<η\lesssim 1/(L(1 + \log(nK)))$, where $K$ is the number of epochs. By retaining the sampling bias at random comparison points, we remove the explicit $1/n$ factor from the stepsize restriction. Combined with existing small-step bounds, our result matches the corresponding averaged-iterate convergence rate up to logarithmic factors.
- Abstract（参考訳）: ランダムリシャッフル確率勾配勾配(RR-SGD)は機械学習における有限サム最適化に広く用いられている。
凸$L$-smooth成分に対して、最近の研究は、コンポーネントが1/L$のオーダーでステップ化される平均的な反復に対して収束保証を確立する。
しかし、最終的なイテレートは実際は自然な出力であり、この設定における既存の最終イテレート保証は、$n$のコンポーネントの数と逆のスケールを必要とする。
我々は、0<η\lesssim 1/(L(1 + \log(nK))$を満足する定数成分をステップ化した非制約問題に対して、標準RR-SGDの最終反復に対して期待の客観的ギャップを定め、ここでは、$K$はエポック数である。
サンプリングバイアスをランダムな比較点に保持することにより、ステップサイズ制限から明示的な1/n$係数を除去する。
既存の小段階境界と組み合わせて, 実測値の平均収束率と対数係数とを一致させる。
関連論文リスト
- A Single-Loop, Constant-Batch First-Order Penalty Method for Stochastic Bilevel Optimization [66.48718943929202]
非強凸二値問題の場合、既存の一階法はネストループに依存するのが一般的である。
2つの相補成分を組み合わせたSingle-loop Constant-1次ペナルティ法(ICOS)を提案する。
論文 参考訳（メタデータ） (2026-10-05T19:26:20Z) - Last-Iterate Convergence Rate of Normalized Gradient Descent under Hölder Smoothness [19.54293832549439]
凸, $(,M_)$-Hlder-smooth 目的に対する正規化勾配勾配勾配の最終定値収束について検討した。
線形に減少するステップサイズは$mathcalObigl(T-(1+)/2bigr)$で、最良値/重み付き平均値の順序に一致する。
論文 参考訳（メタデータ） (2026-10-05T10:04:34Z) - Fast Last-Iterate Convergence of SGD in the Smooth Interpolation Regime [26.711510824243803]
本研究では, 最適騒音が0または0に近い政権において, 円滑な凸目標に対する勾配降下(SGD)の集団収束保証について検討した。
十分に調整されたステップサイズでは、最後の繰り返しに対してほぼ最適な$widetildeO (1/T + sigma_star/sqrtT)$レートを得る。
論文 参考訳（メタデータ） (2025-07-15T12:52:47Z) - From Continual Learning to SGD and Back: Better Rates for Continual Linear Models [50.11453013647086]
以前見られたタスクの損失を、$k$の繰り返しの後、忘れること、すなわち、分析する。
実現可能な最小二乗の設定において、新しい最上界を創出する。
我々は、タスクを繰り返しないランダム化だけで、十分に長いタスクシーケンスで破滅的な事態を防げることを初めて証明した。
論文 参考訳（メタデータ） (2025-04-06T18:39:45Z) - A New Random Reshuffling Method for Nonsmooth Nonconvex Finite-sum Optimization [6.314057999212246]
ランダムリシャッフル型手法の収束と加速度効果は, 設定においてかなり良好であることを示す。
具体的には、(局所的な)クルディカ・ロジャシエヴィチの不等式の下で、ノルムPRRの反復全体の列が収束することが示される。
論文 参考訳（メタデータ） (2023-12-02T07:12:00Z) - Hessian Averaging in Stochastic Newton Methods Achieves Superlinear
Convergence [69.65563161962245]
ニュートン法を用いて,滑らかで強凸な目的関数を考える。
最適段階において局所収束に遷移する普遍重み付き平均化スキームが存在することを示す。
論文 参考訳（メタデータ） (2022-04-20T07:14:21Z) - Last iterate convergence of SGD for Least-Squares in the Interpolation
regime [19.05750582096579]
基本最小二乗構成におけるノイズレスモデルについて検討する。
最適予測器が完全に入力に適合すると仮定し、$langletheta_*, phi(X) rangle = Y$, ここで$phi(X)$は無限次元の非線型特徴写像を表す。
論文 参考訳（メタデータ） (2021-02-05T14:02:20Z) - On the Almost Sure Convergence of Stochastic Gradient Descent in
Non-Convex Problems [75.58134963501094]
本稿では,勾配降下(SGD)の軌跡を解析する。
我々はSGDが厳格なステップサイズポリシーのために1ドルでサドルポイント/マニフォールドを避けることを示す。
論文 参考訳（メタデータ） (2020-06-19T14:11:26Z) - SGD with shuffling: optimal rates without component convexity and large
epoch requirements [60.65928290219793]
我々はRandomShuffle(各エポックの開始時のシャッフル)とSingleShuffle(1回だけシャッフル)を考える。
我々はこれらのアルゴリズムの最小収束速度をポリログ係数ギャップまで確立する。
我々は、すべての先行芸術に共通する欠点を取り除くことにより、RandomShuffleの厳密な収束結果をさらに強化する。
論文 参考訳（メタデータ） (2020-06-12T05:00:44Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。