論文の概要: Anytime Acceleration of Gradient Descent
- arxiv url: http://arxiv.org/abs/2411.17668v1
- Date: Tue, 26 Nov 2024 18:29:44 GMT
- ステータス: 翻訳完了
- システム内更新日: 2024-11-27 13:36:21.789469
- Title: Anytime Acceleration of Gradient Descent
- Title（参考訳）: 緩やかな輝きの時限加速
- Authors: Zihan Zhang, Jason D. Lee, Simon S. Du, Yuxin Chen,
- Abstract要約: 我々は,任意の停止時間に対して,勾配降下が$O(T-1.03)$の収束保証を達成するための段階的スケジュールを提案する。
我々はこの理論を拡張して、滑らかで強い凸最適化のために$exp(-Omega(T/kappa0.97)$の収束を保証する。
- 参考スコア（独自算出の注目度）: 92.02082223856479
- License:
- Abstract: This work investigates stepsize-based acceleration of gradient descent with {\em anytime} convergence guarantees. For smooth (non-strongly) convex optimization, we propose a stepsize schedule that allows gradient descent to achieve convergence guarantees of $O(T^{-1.03})$ for any stopping time $T$, where the stepsize schedule is predetermined without prior knowledge of the stopping time. This result provides an affirmative answer to a COLT open problem \citep{kornowski2024open} regarding whether stepsize-based acceleration can yield anytime convergence rates of $o(T^{-1})$. We further extend our theory to yield anytime convergence guarantees of $\exp(-\Omega(T/\kappa^{0.97}))$ for smooth and strongly convex optimization, with $\kappa$ being the condition number.
- Abstract（参考訳）: 本研究は, 収束保証を伴う勾配勾配勾配の段階的加速度について検討する。
円滑な(非強めの)凸最適化のために、停止時間の事前知識なくステップ化スケジュールを定めている任意の停止時間$T$に対して、勾配降下が$O(T^{-1.03})$の収束保証を達成するためのステップ化スケジュールを提案する。
この結果は COLT の開問題 \citep{kornowski2024open} に対して、段階的加速度が $o(T^{-1})$ の任意の時間収束率を得ることができるかどうかについて肯定的な答えを与える。
さらに我々の理論を拡張して、条件数である$\kappa$を滑らかで強凸な最適化のために、$\exp(-\Omega(T/\kappa^{0.97})$の任意の時間収束保証を与える。
関連論文リスト
- Open Problem: Anytime Convergence Rate of Gradient Descent [37.300102993926046]
また, ベニラ勾配降下は, 段差列を変化させることで, 滑らかな凸目標に対して加速可能であることを示す。
古典的な$mathcalO (1/T)$収束率を加速する勾配降下の段階的なスケジュールは、幻の停止時間$T$で存在するか?
論文 参考訳（メタデータ） (2024-06-19T23:34:47Z) - Accelerated Quasi-Newton Proximal Extragradient: Faster Rate for Smooth
Convex Optimization [26.328847475942894]
我々は,本手法が$Obigl(minfrac1k2, fracsqrtdlog kk2.5bigr)$の収束率を達成できることを証明した。
我々の知る限りでは、この結果はネステロフの加速勾配に対する準ニュートン型法の証明可能な利得を示す最初のものである。
論文 参考訳（メタデータ） (2023-06-03T23:31:27Z) - Breaking the Lower Bound with (Little) Structure: Acceleration in
Non-Convex Stochastic Optimization with Heavy-Tailed Noise [28.780192812703948]
重み付き雑音状態において、滑らかだが必ずしも凸な目標を持つ最適化問題を考察する。
簡単な構造しか持たない低境界の$Omega(Tfrac1-p3p-2)$よりも高速な速度が得られることを示す。
また、軽度条件下では、高い確率収束率が$O(log(T/delta)Tfrac1-p3p-2)$であることを保証する。
論文 参考訳（メタデータ） (2023-02-14T00:23:42Z) - ReSQueing Parallel and Private Stochastic Convex Optimization [59.53297063174519]
本稿では,BFG凸最適化(SCO: Reweighted Query (ReSQue) 推定ツールを提案する。
我々はSCOの並列およびプライベート設定における最先端の複雑さを実現するアルゴリズムを開発した。
論文 参考訳（メタデータ） (2023-01-01T18:51:29Z) - Sharper Convergence Guarantees for Asynchronous SGD for Distributed and
Federated Learning [77.22019100456595]
通信周波数の異なる分散計算作業者のトレーニングアルゴリズムを示す。
本研究では,より厳密な収束率を$mathcalO!!(sigma2-2_avg!)とする。
また,不均一性の項は,作業者の平均遅延によっても影響されることを示した。
論文 参考訳（メタデータ） (2022-06-16T17:10:57Z) - Asynchronous Stochastic Optimization Robust to Arbitrary Delays [54.61797739710608]
遅延勾配の最適化を考えると、ステップt$毎に、アルゴリズムは古い計算を使って更新する - d_t$ for arbitrary delay $d_t gradient。
本実験は,遅延分布が歪んだり重くなったりした場合のアルゴリズムの有効性とロバスト性を示す。
論文 参考訳（メタデータ） (2021-06-22T15:50:45Z) - On the Convergence of Step Decay Step-Size for Stochastic Optimization [27.02857082612736]
神経系の収束は、特にネットワーク問題などの非数学問題において、ステップサイズ率に大きく依存する。
非スムース状態における崩壊の収束を提供し、勾配ノルムが消えることを保証する。
強い凸の場合、$(T/ST)$レートを確立し、$(T/ST)$レートであることも証明します。
論文 参考訳（メタデータ） (2021-02-18T14:37:25Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。