論文の概要: Nesterov Accelerated Shuffling Gradient Method for Convex Optimization
- arxiv url: http://arxiv.org/abs/2202.03525v1
- Date: Mon, 7 Feb 2022 21:23:17 GMT
- ステータス: 処理完了
- システム内更新日: 2022-02-09 15:04:18.693202
- Title: Nesterov Accelerated Shuffling Gradient Method for Convex Optimization
- Title(参考訳): 凸最適化のためのNesterov Accelerated Shuffling Gradient Method
- Authors: Trang H. Tran, Lam M. Nguyen, Katya Scheinberg
- Abstract要約: このアルゴリズムは,統一シャッフル方式を用いて,$mathcalO (1/T)$の改善率を示す。
我々の収束解析は有界領域や有界勾配条件に関する仮定を必要としない。
数値シミュレーションはアルゴリズムの効率を実証する。
- 参考スコア(独自算出の注目度): 15.908060383231371
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In this paper, we propose Nesterov Accelerated Shuffling Gradient (NASG), a
new algorithm for the convex finite-sum minimization problems. Our method
integrates the traditional Nesterov's acceleration momentum with different
shuffling sampling schemes. We show that our algorithm has an improved rate of
$\mathcal{O}(1/T)$ using unified shuffling schemes, where $T$ is the number of
epochs. This rate is better than that of any other shuffling gradient methods
in convex regime. Our convergence analysis does not require an assumption on
bounded domain or a bounded gradient condition. For randomized shuffling
schemes, we improve the convergence bound further. When employing some initial
condition, we show that our method converges faster near the small neighborhood
of the solution. Numerical simulations demonstrate the efficiency of our
algorithm.
- Abstract(参考訳): 本稿では,凸有限サム最小化問題に対する新しいアルゴリズムであるNesterov Accelerated Shuffling Gradient (NASG)を提案する。
本手法は,従来のネステロフ加速運動量と異なるシャッフルサンプリングスキームを統合する。
我々は,このアルゴリズムが統合シャッフルスキームを用いて$\mathcal{O}(1/T)$の改善率を示し,そこでは$T$がエポックの数である。
この値は凸系における他のシャッフル勾配法よりも優れている。
我々の収束解析は有界領域や有界勾配条件に関する仮定を必要としない。
ランダムなシャッフルスキームでは、収束境界をさらに改善する。
初期条件を用いる場合, この手法は解の小さな近傍付近でより高速に収束することを示す。
数値シミュレーションはアルゴリズムの効率を実証する。
関連論文リスト
- Methods for Convex $(L_0,L_1)$-Smooth Optimization: Clipping, Acceleration, and Adaptivity [50.25258834153574]
我々は、(強に)凸 $(L0)$-smooth 関数のクラスに焦点を当て、いくつかの既存のメソッドに対する新しい収束保証を導出する。
特に,スムーズなグラディエント・クリッピングを有するグラディエント・ディフレッシュと,ポリアク・ステップサイズを有するグラディエント・ディフレッシュのコンバージェンス・レートの改善を導出した。
論文 参考訳(メタデータ) (2024-09-23T13:11:37Z) - Variance reduction techniques for stochastic proximal point algorithms [5.374800961359305]
そこで本研究では,近点アルゴリズムにおける分散低減手法の統一化研究を提案する。
我々は,SVRG,SAGA,およびそれらの変種の近位バージョンを提供するために特定可能な,汎用的近位アルゴリズムを提案する。
本実験は, 勾配法よりも近似分散還元法の利点を実証する。
論文 参考訳(メタデータ) (2023-08-18T05:11:50Z) - Strictly Low Rank Constraint Optimization -- An Asymptotically
$\mathcal{O}(\frac{1}{t^2})$ Method [5.770309971945476]
最適解における空間性を促進するために,テキスト規則化を用いた非テキスト・非滑らかな問題のクラスを提案する。
我々のアルゴリズムは、滑らかな凸問題に対する一階法に対するネステロフの最適収束と全く同じ$Ofrac(t2)$の特異収束を達成することができることを示す。
論文 参考訳(メタデータ) (2023-07-04T16:55:41Z) - Explicit Second-Order Min-Max Optimization Methods with Optimal Convergence Guarantee [86.05440220344755]
我々は,非制約のmin-max最適化問題のグローバルなサドル点を求めるために,不正確な正規化ニュートン型手法を提案し,解析する。
提案手法は有界集合内に留まるイテレートを生成し、その反復は制限関数の項で$O(epsilon-2/3)$内の$epsilon$-saddle点に収束することを示す。
論文 参考訳(メタデータ) (2022-10-23T21:24:37Z) - Optimal Extragradient-Based Bilinearly-Coupled Saddle-Point Optimization [116.89941263390769]
滑らかな凸凹凸結合型サドル点問題, $min_mathbfxmax_mathbfyF(mathbfx) + H(mathbfx,mathbfy)$ を考える。
漸進的勾配指数(AG-EG)降下指数アルゴリズムについて述べる。
論文 参考訳(メタデータ) (2022-06-17T06:10:20Z) - Hessian Averaging in Stochastic Newton Methods Achieves Superlinear
Convergence [69.65563161962245]
ニュートン法を用いて,滑らかで強凸な目的関数を考える。
最適段階において局所収束に遷移する普遍重み付き平均化スキームが存在することを示す。
論文 参考訳(メタデータ) (2022-04-20T07:14:21Z) - Accelerated SGD for Non-Strongly-Convex Least Squares [14.010916616909743]
非強凸設定における最小二乗回帰問題の近似を考察する。
本稿では,問題のノイズに依存して最適な予測誤差率を実現するための,最初の実用的なアルゴリズムを提案する。
論文 参考訳(メタデータ) (2022-03-03T14:39:33Z) - Minibatch vs Local SGD with Shuffling: Tight Convergence Bounds and
Beyond [63.59034509960994]
シャッフルに基づく変種(ミニバッチと局所ランダムリシャッフル)について検討する。
ポリアック・ロジャシエヴィチ条件を満たす滑らかな函数に対して、これらのシャッフル型不変量(英語版)(shuffling-based variants)がそれらの置換式よりも早く収束することを示す収束境界を得る。
我々は, 同期シャッフル法と呼ばれるアルゴリズムの修正を提案し, ほぼ均一な条件下では, 下界よりも収束速度が速くなった。
論文 参考訳(メタデータ) (2021-10-20T02:25:25Z) - A Unified Analysis of First-Order Methods for Smooth Games via Integral
Quadratic Constraints [10.578409461429626]
本研究では、滑らかで強可変なゲームやイテレーションのための一階法に積分二次的制約理論を適用する。
我々は、負の運動量法(NM)に対して、既知の下界と一致する複雑性$mathcalO(kappa1.5)$で、初めて大域収束率を与える。
一段階のメモリを持つアルゴリズムでは,バッチ毎に1回だけ勾配を問合せすれば,高速化は不可能であることを示す。
論文 参考訳(メタデータ) (2020-09-23T20:02:00Z) - Exploiting Higher Order Smoothness in Derivative-free Optimization and
Continuous Bandits [99.70167985955352]
強凸関数のゼロ次最適化問題について検討する。
予測勾配降下アルゴリズムのランダム化近似を考察する。
その結果,0次アルゴリズムはサンプルの複雑性や問題パラメータの点でほぼ最適であることが示唆された。
論文 参考訳(メタデータ) (2020-06-14T10:42:23Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。