論文の概要: A Unified Convergence Analysis for Shuffling-Type Gradient Methods
- arxiv url: http://arxiv.org/abs/2002.08246v2
- Date: Mon, 20 Sep 2021 00:44:31 GMT
- ステータス: 処理完了
- システム内更新日: 2022-12-30 13:34:24.471298
- Title: A Unified Convergence Analysis for Shuffling-Type Gradient Methods
- Title（参考訳）: シャッフル型勾配法の統一収束解析
- Authors: Lam M. Nguyen, Quoc Tran-Dinh, Dzung T. Phan, Phuong Ha Nguyen, Marten
van Dijk
- Abstract要約: 有限項問題を解くための一般化勾配シャッフル型法に対する統一収束解析を提案する。
以上の結果から,特定の神経シャッフル変種でのトレーニングに適する選択が示唆された。
- 参考スコア（独自算出の注目度）: 32.8097849940763
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In this paper, we propose a unified convergence analysis for a class of
generic shuffling-type gradient methods for solving finite-sum optimization
problems. Our analysis works with any sampling without replacement strategy and
covers many known variants such as randomized reshuffling, deterministic or
randomized single permutation, and cyclic and incremental gradient schemes. We
focus on two different settings: strongly convex and nonconvex problems, but
also discuss the non-strongly convex case. Our main contribution consists of
new non-asymptotic and asymptotic convergence rates for a wide class of
shuffling-type gradient methods in both nonconvex and convex settings. We also
study uniformly randomized shuffling variants with different learning rates and
model assumptions. While our rate in the nonconvex case is new and
significantly improved over existing works under standard assumptions, the rate
on the strongly convex one matches the existing best-known rates prior to this
paper up to a constant factor without imposing a bounded gradient condition.
Finally, we empirically illustrate our theoretical results via two numerical
examples: nonconvex logistic regression and neural network training examples.
As byproducts, our results suggest some appropriate choices for diminishing
learning rates in certain shuffling variants.
- Abstract（参考訳）: 本稿では,有限サム最適化問題の解法として,一般シャッフル型勾配法の一群に対する統一収束解析を提案する。
本分析は,代替戦略を用いず,無作為化再シャッフル,決定論的あるいは無作為化単一置換,循環的および漸進的勾配スキームなど,多くの既知の変種をカバーする。
我々は、強い凸問題と非凸問題という2つの異なる設定に焦点を当てている。
本研究の主な貢献は,非凸および凸の双方において,シャッフル型勾配法を多種に含む新しい非漸近および漸近収束率である。
また,学習率の異なる一様化シャッフル変種とモデル仮定についても検討した。
非凸の場合の速度は、標準仮定の下での既存の作業よりも新しく、大幅に改善されているが、強い凸の場合の速度は、有界勾配条件を課すことなく、この論文以前の既知の最もよく知られた速度と一致する。
最後に、非凸ロジスティック回帰とニューラルネットワークトレーニングの2つの数値例を通して、理論的結果を実証的に説明する。
副産物として,特定のシャッフル変種における学習率の低下に対する適切な選択が示唆された。
関連論文リスト
- Methods for Convex $(L_0,L_1)$-Smooth Optimization: Clipping, Acceleration, and Adaptivity [50.25258834153574]
我々は、(強に)凸 $(L0)$-smooth 関数のクラスに焦点を当て、いくつかの既存のメソッドに対する新しい収束保証を導出する。
特に,スムーズなグラディエント・クリッピングを有するグラディエント・ディフレッシュと,ポリアク・ステップサイズを有するグラディエント・ディフレッシュのコンバージェンス・レートの改善を導出した。
論文 参考訳（メタデータ） (2024-09-23T13:11:37Z) - On the Stochastic (Variance-Reduced) Proximal Gradient Method for Regularized Expected Reward Optimization [10.36447258513813]
我々は、強化学習(RL)における既存の問題の多くを網羅する非文献設定における正規化期待報酬最適化問題を考える。
特に、標準条件下では、$O(epsilon-4)$サンプルを$epsilon$-stationaryポイントに含めることが示されている。
分析の結果,サンプルの複雑さは,追加条件下では$O(epsilon-4)$から$O(epsilon-3)$に改善できることがわかった。
論文 参考訳（メタデータ） (2024-01-23T06:01:29Z) - High-Probability Convergence for Composite and Distributed Stochastic Minimization and Variational Inequalities with Heavy-Tailed Noise [96.80184504268593]
グラデーション、クリッピングは、優れた高確率保証を導き出すアルゴリズムの鍵となる要素の1つである。
クリッピングは、合成および分散最適化の一般的な方法の収束を損なう可能性がある。
論文 参考訳（メタデータ） (2023-10-03T07:49:17Z) - Convex and Non-convex Optimization Under Generalized Smoothness [69.69521650503431]
凸法と非最適化法の分析は、しばしばリプシッツ勾配を必要とし、この軌道による解析を制限する。
最近の研究は、非一様滑らか性条件を通した勾配設定を一般化している。
論文 参考訳（メタデータ） (2023-06-02T04:21:59Z) - First Order Methods with Markovian Noise: from Acceleration to Variational Inequalities [91.46841922915418]
本稿では,一階変分法の理論解析のための統一的アプローチを提案する。
提案手法は非線形勾配問題とモンテカルロの強い問題の両方をカバーする。
凸法最適化問題の場合、オラクルに強く一致するような境界を与える。
論文 参考訳（メタデータ） (2023-05-25T11:11:31Z) - High-Probability Bounds for Stochastic Optimization and Variational
Inequalities: the Case of Unbounded Variance [59.211456992422136]
制約の少ない仮定の下で高確率収束結果のアルゴリズムを提案する。
これらの結果は、標準機能クラスに適合しない問題を最適化するために検討された手法の使用を正当化する。
論文 参考訳（メタデータ） (2023-02-02T10:37:23Z) - Adaptive Sampling Quasi-Newton Methods for Zeroth-Order Stochastic
Optimization [1.7513645771137178]
勾配情報のない制約のない最適化問題を考察する。
適応的なサンプリング準ニュートン法を提案し、共通乱数フレームワーク内の有限差を用いてシミュレーション関数の勾配を推定する。
そこで本研究では, 標準試験と内積準ニュートン試験の修正版を開発し, 近似に使用する試料サイズを制御し, 最適解の近傍に大域収束結果を与える。
論文 参考訳（メタデータ） (2021-09-24T21:49:25Z) - Zeroth-Order Hybrid Gradient Descent: Towards A Principled Black-Box
Optimization Framework [100.36569795440889]
この作業は、一階情報を必要としない零次最適化(ZO)の反復である。
座標重要度サンプリングにおける優雅な設計により,ZO最適化法は複雑度と関数クエリコストの両面において効率的であることを示す。
論文 参考訳（メタデータ） (2020-12-21T17:29:58Z) - Distributed Stochastic Nonconvex Optimization and Learning based on
Successive Convex Approximation [26.11677569331688]
本稿では,ネットワーク内のエージェントの総和の分散アルゴリズム最小化のための新しいフレームワークを提案する。
提案手法は分散ニューラルネットワークに適用可能であることを示す。
論文 参考訳（メタデータ） (2020-04-30T15:36:46Z) - Sampling and Update Frequencies in Proximal Variance-Reduced Stochastic
Gradient Methods [0.0]
本稿では, 一般近似分散還元勾配法を提案し, 強い凸性仮定の下で解析する。
このアルゴリズムの特別な例は、SAGA、L-SVRGとその近位変種である。
論文 参考訳（メタデータ） (2020-02-13T14:56:05Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。