論文の概要: The Convergence Rate of SGD's Final Iterate: Analysis on Dimension
Dependence
- arxiv url: http://arxiv.org/abs/2106.14588v1
- Date: Mon, 28 Jun 2021 11:51:04 GMT
- ステータス: 処理完了
- システム内更新日: 2021-06-29 13:50:27.409830
- Title: The Convergence Rate of SGD's Final Iterate: Analysis on Dimension
Dependence
- Title（参考訳）: SGDの最終イテレーションの収束速度:次元依存性の分析
- Authors: Daogao Liu, Zhou Lu
- Abstract要約: Gradient Descent (SGD) は最適化において最も単純で一般的な手法の一つである。
定次元設定におけるSGDの最終点収束を特徴付ける方法を示す。
- 参考スコア（独自算出の注目度）: 2.512827436728378
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Stochastic Gradient Descent (SGD) is among the simplest and most popular
methods in optimization. The convergence rate for SGD has been extensively
studied and tight analyses have been established for the running average
scheme, but the sub-optimality of the final iterate is still not
well-understood. shamir2013stochastic gave the best known upper bound for the
final iterate of SGD minimizing non-smooth convex functions, which is $O(\log
T/\sqrt{T})$ for Lipschitz convex functions and $O(\log T/ T)$ with additional
assumption on strongly convexity. The best known lower bounds, however, are
worse than the upper bounds by a factor of $\log T$. harvey2019tight gave
matching lower bounds but their construction requires dimension $d= T$. It was
then asked by koren2020open how to characterize the final-iterate convergence
of SGD in the constant dimension setting.
In this paper, we answer this question in the more general setting for any
$d\leq T$, proving $\Omega(\log d/\sqrt{T})$ and $\Omega(\log d/T)$ lower
bounds for the sub-optimality of the final iterate of SGD in minimizing
non-smooth Lipschitz convex and strongly convex functions respectively with
standard step size schedules. Our results provide the first general dimension
dependent lower bound on the convergence of SGD's final iterate, partially
resolving a COLT open question raised by koren2020open. We also present further
evidence to show the correct rate in one dimension should be
$\Theta(1/\sqrt{T})$, such as a proof of a tight $O(1/\sqrt{T})$ upper bound
for one-dimensional special cases in settings more general than koren2020open.
- Abstract（参考訳）: Stochastic Gradient Descent (SGD) は最適化において最も単純で最も人気のある手法の一つである。
SGDの収束速度は広く研究され、ランニング平均スキームの厳密な解析が確立されているが、最終イテレーションの準最適性はまだよく理解されていない。
Shamir2013stochastic は、非滑らか凸函数を最小化する SGD の最終イテレートに対して最もよく知られた上限を与え、これは、リプシッツ凸函数に対して$O(\log T/\sqrt{T})$ と$O(\log T/T)$ である。
しかし、最もよく知られた下界は、$\log T$ の係数によって上界よりも悪い。
harvey2019tightは一致した下界を与えるが、その構成には次元$d=T$が必要である。
その後、koren2020open により、定数次元設定におけるsgdの最終イテレート収束を特徴付ける方法が求められた。
本稿では,任意の$d\leq T$に対してより一般的な設定で,SGDの最終イテレーションの最適値に対する$\Omega(\log d/\sqrt{T})$と$\Omega(\log d/T)$の下限を証明し,非滑らかリプシッツ凸と強凸関数をそれぞれ標準ステップサイズスケジュールで最小化する。
以上の結果から,SGD の最終反復の収束度に従属する第1次一般次元下界が得られ,コレン2020open が提起した COLT の開問題の部分解が得られた。
また, 1 次元の正解率は,koren2020open よりも一般の設定において 1 次元の特別な場合に対して,タイトな $o(1/\sqrt{t})$ の証明のように,\theta(1/\sqrt{t})$ であるべきであることを示すさらなる証拠を示す。
関連論文リスト
- Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic
Shortest Path [80.60592344361073]
線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。
エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。
既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
論文 参考訳（メタデータ） (2024-02-14T07:52:00Z) - On the $O(\frac{\sqrt{d}}{T^{1/4}})$ Convergence Rate of RMSProp and Its Momentum Extension Measured by $\ell_1$ Norm [59.65871549878937]
本稿では、RMSPropとその運動量拡張を考察し、$frac1Tsum_k=1Tの収束速度を確立する。
我々の収束率は、次元$d$を除くすべての係数に関して下界と一致する。
収束率は$frac1Tsum_k=1Tと類似していると考えられる。
論文 参考訳（メタデータ） (2024-02-01T07:21:32Z) - Revisiting the Last-Iterate Convergence of Stochastic Gradient Methods [25.831462008050387]
グラディエント・Descent(SGD)アルゴリズムは、実際の性能が良く、理論的な理解が欠如していることから、人々の関心を喚起している。
有限収束がより広い合成最適化や非ユークリッドノルムに証明可能な拡張が可能かどうかはまだ不明である。
論文 参考訳（メタデータ） (2023-12-13T21:41:06Z) - Convergence Rates for Stochastic Approximation: Biased Noise with Unbounded Variance, and Applications [2.0584253077707477]
本研究では、与えられた目的関数の定常点を求めるグラディエント・Descent(SGD)法の収束特性について検討する。
この結果は、すべての定常点が大域最小値である性質を持つ invex' 関数のクラスに適用できる。
論文 参考訳（メタデータ） (2023-12-05T15:22:39Z) - Lower Generalization Bounds for GD and SGD in Smooth Stochastic Convex
Optimization [9.019243171993553]
トレーニングステップ$T$とStep-size$eta$は、滑らかな凸最適化(SCO)問題の認定に影響を与える可能性がある。
まず、グラディエントDescent(GD)とグラディエントDescent(SGD)の厳密な過剰リスク低境界を提供する。
近年の作業は、より良い速度で達成できるが、トレーニング時間が長い場合には改善が減少する。
論文 参考訳（メタデータ） (2023-03-19T20:24:33Z) - Private Stochastic Convex Optimization: Optimal Rates in $\ell_1$
Geometry [69.24618367447101]
対数要因まで $(varepsilon,delta)$-differently private の最適過剰人口損失は $sqrtlog(d)/n + sqrtd/varepsilon n.$ です。
損失関数がさらなる滑らかさの仮定を満たすとき、余剰損失は$sqrtlog(d)/n + (log(d)/varepsilon n)2/3で上界(対数因子まで)であることが示される。
論文 参考訳（メタデータ） (2021-03-02T06:53:44Z) - 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) - Hybrid Stochastic-Deterministic Minibatch Proximal Gradient:
Less-Than-Single-Pass Optimization with Nearly Optimal Generalization [83.80460802169999]
HSDMPGは、学習モデル上で過大なエラーの順序である$mathcalObig(1/sttnbig)$を達成可能であることを示す。
損失係数について、HSDMPGは学習モデル上で過大なエラーの順序である$mathcalObig(1/sttnbig)$を達成できることを示す。
論文 参考訳（メタデータ） (2020-09-18T02:18:44Z) - On the Almost Sure Convergence of Stochastic Gradient Descent in
Non-Convex Problems [75.58134963501094]
本稿では,勾配降下(SGD)の軌跡を解析する。
我々はSGDが厳格なステップサイズポリシーのために1ドルでサドルポイント/マニフォールドを避けることを示す。
論文 参考訳（メタデータ） (2020-06-19T14:11:26Z) - A Simple Convergence Proof of Adam and Adagrad [74.24716715922759]
我々はAdam Adagradと$O(d(N)/st)$アルゴリズムの収束の証明を示す。
Adamはデフォルトパラメータで使用する場合と同じ収束$O(d(N)/st)$で収束する。
論文 参考訳（メタデータ） (2020-03-05T01:56:17Z) - Closing the convergence gap of SGD without replacement [9.109788577327503]
モデルトレーニングでは,置換サンプリングを伴わない勾配降下が広く用いられている。
置換のない SGD は、関数の和が二次であるときに $mathcalOleft(frac1T2+fracn2T3right)$ を達成することを示す。
論文 参考訳（メタデータ） (2020-02-24T17:37:28Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。