論文の概要: Improved Analysis for Sign-based Methods with Momentum Updates
- arxiv url: http://arxiv.org/abs/2507.12091v1
- Date: Wed, 16 Jul 2025 09:54:08 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-07-17 19:00:11.343217
- Title: Improved Analysis for Sign-based Methods with Momentum Updates
- Title（参考訳）: モーメント更新による手話法の改良
- Authors: Wei Jiang, Dingzhi Yu, Sifan Yang, Wenhao Yang, Lijun Zhang,
- Abstract要約: モーメントを更新した符号ベース最適化アルゴリズムの高機能化について述べる。
提案手法は,$mathcalOleft(d1/2T-1/2 + dn-1/2 right)$と$mathcalleft(max d1/4T-1/4 + dn-1/2 right)$の収束率を求める。
- 参考スコア（独自算出の注目度）: 15.679979249491087
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: In this paper, we present enhanced analysis for sign-based optimization algorithms with momentum updates. Traditional sign-based methods, under the separable smoothness assumption, guarantee a convergence rate of $\mathcal{O}(T^{-1/4})$, but they either require large batch sizes or assume unimodal symmetric stochastic noise. To address these limitations, we demonstrate that signSGD with momentum can achieve the same convergence rate using constant batch sizes without additional assumptions. Our analysis, under the standard $l_2$-smoothness condition, improves upon the result of the prior momentum-based signSGD method by a factor of $\mathcal{O}(d^{1/2})$, where $d$ is the problem dimension. Furthermore, we explore sign-based methods with majority vote in distributed settings and show that the proposed momentum-based method yields convergence rates of $\mathcal{O}\left( d^{1/2}T^{-1/2} + dn^{-1/2} \right)$ and $\mathcal{O}\left( \max \{ d^{1/4}T^{-1/4}, d^{1/10}T^{-1/5} \} \right)$, which outperform the previous results of $\mathcal{O}\left( dT^{-1/4} + dn^{-1/2} \right)$ and $\mathcal{O}\left( d^{3/8}T^{-1/8} \right)$, respectively. Numerical experiments further validate the effectiveness of the proposed methods.
- Abstract（参考訳）: 本稿では,モーメント更新を伴う符号ベース最適化アルゴリズムの強化解析について述べる。
従来の手話に基づく手法は、分離可能な滑らかさの仮定の下で、$\mathcal{O}(T^{-1/4})$の収束速度を保証するが、それらは大きなバッチサイズを必要とするか、非特異対称確率ノイズを仮定する。
これらの制約に対処するため,運動量を持つ符号SGDは,仮定を伴わずに一定のバッチサイズで同じ収束率が得られることを示した。
我々の分析は、標準の$l_2$-smoothness条件の下で、$d$が問題次元である$\mathcal{O}(d^{1/2})$の係数により、前回の運動量に基づくSignSGD法の結果を改善する。
さらに、分散環境で多数決された符号ベースの手法を探索し、提案手法が$\mathcal{O}\left(d^{1/2}T^{-1/2} + dn^{-1/2} \right)$と$\mathcal{O}\left( \max \{ d^{1/4}T^{-1/4}, d^{1/10}T^{-1/5} \} \right)$の収束率を示し、$\mathcal{O}\left(dT^{-1/4} + dn^{-1/2} \right)$と$\mathcal{O}\left(d^{3/8}T^{-1/8} \right)$をそれぞれ上回る。
数値実験により,提案手法の有効性がさらに検証された。
関連論文リスト
- Simple Convergence Proof of Adam From a Sign-like Descent Perspective [58.89890024903816]
我々は、Adamが以前の$cal O(fracln TTs14)$よりも$cal O(frac1Ts14)$の最適なレートを達成することを示す。
我々の理論分析は、収束を保証する重要な要因として運動量の役割に関する新たな洞察を提供する。
論文 参考訳（メタデータ） (2025-07-08T13:19:26Z) - Global Convergence for Average Reward Constrained MDPs with Primal-Dual Actor Critic Algorithm [31.539921770584005]
本研究では,高収束率を確保しつつ制約を適切に管理するPrimal-Dual Natural Actor-Criticアルゴリズムを提案する。
この結果はマルコフ決定過程の理論的下限と一致し、平均報酬CMDPの理論的探索において新しいベンチマークを確立する。
論文 参考訳（メタデータ） (2025-05-21T05:49:11Z) - Sign Operator for Coping with Heavy-Tailed Noise in Non-Convex Optimization: High Probability Bounds Under $(L_0, L_1)$-Smoothness [74.18546828528298]
SignSGD with Majority Votingは,Kappakappakappa-1right,Kappakappakappa-1right,Kappakappakappa-1right,Kappakappakappa-1right,Kappaka ppakappa-1right,Kappakappakappa-1right,Kappakappakappa-1right,Kappakappakappa-1right,Kappakappakappa -1right,Kappakappakappa-1right,Kappakappakappa-1right,Kappakappappapa-1right,Kappaを用いて,複雑性の全範囲で堅牢に動作することを示す。
論文 参考訳（メタデータ） (2025-02-11T19:54:11Z) - Nonconvex Stochastic Optimization under Heavy-Tailed Noises: Optimal Convergence without Gradient Clipping [21.865728815935665]
重み付き雑音下での最初の収束を提供するが、切断はしない。
また、テールインデックス$mathfrakp$が事前に不明な場合には、最初の$mathcalO(Tfrac1-mathfrakp3mathfrakp-2)$収束率も設定する。
論文 参考訳（メタデータ） (2024-12-27T08:46:46Z) - Efficient Sign-Based Optimization: Accelerating Convergence via Variance Reduction [16.82220229840038]
それぞれ$mathcalO(d1/2T-1/2 + dn-1/2)$と$mathcalO(d1/4T-1/4)$の収束率を改善する2つの新しいアルゴリズムを導入する。
提案手法の有効性を検証した数値実験を行った。
論文 参考訳（メタデータ） (2024-06-01T16:38:43Z) - Mirror Descent Algorithms with Nearly Dimension-Independent Rates for
Differentially-Private Stochastic Saddle-Point Problems [6.431793114484429]
多面体設定における微分プライベートなサドル点の問題を解くために、$sqrtlog(d)/sqrtn + log(d)/[nvarepsilon]2/5$を提案する。
我々のアルゴリズムは、一定の成功率で$sqrtlog(d)/sqrtn + log(d)/[nvarepsilon]2/5$に達することを示す。
論文 参考訳（メタデータ） (2024-03-05T12:28:00Z) - 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) - Near Optimal Heteroscedastic Regression with Symbiotic Learning [29.16456701187538]
我々は不連続線形回帰の問題を考察する。
正則ノルムにおいて$mathbfw*$を$tildeOleft(|mathbff*|2cdot left(frac1n + left(dnright)2right)$の誤差まで推定し、一致する下界を証明できる。
論文 参考訳（メタデータ） (2023-06-25T16:32:00Z) - Mean-Square Analysis with An Application to Optimal Dimension Dependence
of Langevin Monte Carlo [60.785586069299356]
この研究は、2-ワッサーシュタイン距離におけるサンプリング誤差の非同相解析のための一般的な枠組みを提供する。
我々の理論解析は数値実験によってさらに検証される。
論文 参考訳（メタデータ） (2021-09-08T18:00:05Z) - Optimal Mean Estimation without a Variance [103.26777953032537]
本研究では,データ生成分布の分散が存在しない環境での重み付き平均推定問題について検討する。
最小の信頼区間を$n,d,delta$の関数として得る推定器を設計する。
論文 参考訳（メタデータ） (2020-11-24T22:39:21Z) - Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and
Variance Reduction [63.41789556777387]
非同期Q-ラーニングはマルコフ決定過程(MDP)の最適行動値関数(またはQ-関数)を学習することを目的としている。
Q-関数の入出力$varepsilon$-正確な推定に必要なサンプルの数は、少なくとも$frac1mu_min (1-gamma)5varepsilon2+ fract_mixmu_min (1-gamma)$の順である。
論文 参考訳（メタデータ） (2020-06-04T17:51:00Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。