論文の概要: Uniform-in-Time Wasserstein Stability Bounds for (Noisy) Stochastic
Gradient Descent
- arxiv url: http://arxiv.org/abs/2305.12056v1
- Date: Sat, 20 May 2023 01:49:58 GMT
- ステータス: 処理完了
- システム内更新日: 2023-05-24 01:05:11.916486
- Title: Uniform-in-Time Wasserstein Stability Bounds for (Noisy) Stochastic
Gradient Descent
- Title（参考訳）: 確率的勾配降下(ノイズ)に対する一様時間wasserstein安定性境界
- Authors: Lingjiong Zhu, Mert Gurbuzbalaban, Anant Raj, Umut Simsekli
- Abstract要約: この10年で、異なる損失関数に適用された異なるアルゴリズムに対する安定性の増大が見られた。
本稿では,最適化アルゴリズムの安定性を証明するための統一的なガイドラインを導入する。
私たちのアプローチは柔軟で、他の一般的な学習クラスにも容易に適用できます。
- 参考スコア（独自算出の注目度）: 36.08156597506344
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Algorithmic stability is an important notion that has proven powerful for
deriving generalization bounds for practical algorithms. The last decade has
witnessed an increasing number of stability bounds for different algorithms
applied on different classes of loss functions. While these bounds have
illuminated various properties of optimization algorithms, the analysis of each
case typically required a different proof technique with significantly
different mathematical tools. In this study, we make a novel connection between
learning theory and applied probability and introduce a unified guideline for
proving Wasserstein stability bounds for stochastic optimization algorithms. We
illustrate our approach on stochastic gradient descent (SGD) and we obtain
time-uniform stability bounds (i.e., the bound does not increase with the
number of iterations) for strongly convex losses and non-convex losses with
additive noise, where we recover similar results to the prior art or extend
them to more general cases by using a single proof technique. Our approach is
flexible and can be generalizable to other popular optimizers, as it mainly
requires developing Lyapunov functions, which are often readily available in
the literature. It also illustrates that ergodicity is an important component
for obtaining time-uniform bounds -- which might not be achieved for convex or
non-convex losses unless additional noise is injected to the iterates. Finally,
we slightly stretch our analysis technique and prove time-uniform bounds for
SGD under convex and non-convex losses (without additional additive noise),
which, to our knowledge, is novel.
- Abstract（参考訳）: アルゴリズム安定性は、実用的なアルゴリズムの一般化境界を導出するのに強力な重要な概念である。
過去10年間、異なる損失関数のクラスに適用される異なるアルゴリズムの安定性限界が増えている。
これらの境界は最適化アルゴリズムの様々な特性を照らしているが、それぞれのケースの分析には、異なる数学的ツールを持つ異なる証明技術が必要であった。
本研究では,学習理論と応用確率との関係を新たに定義し,確率最適化アルゴリズムに対するwassersteinの安定性境界を証明するための統一ガイドラインを提案する。
確率勾配降下(SGD)に対する我々のアプローチを概説し、強い凸損失と付加雑音による非凸損失に対する時間一様安定性境界(すなわち、反復数で境界が増加することはない)を得る。
我々のアプローチは柔軟であり、他の一般的なオプティマイザにも一般化可能である。
また、エルゴード性は時間一様境界を得るために重要な要素であることも示しており、イテレートに追加のノイズが注入されない限り凸または凸でない損失に対しては達成できない。
最後に, 解析手法をわずかに延長し, 凸および非凸損失(付加雑音を伴わない)下でのsgdの時間一様境界を証明する。
関連論文リスト
- High-Probability Convergence for Composite and Distributed Stochastic Minimization and Variational Inequalities with Heavy-Tailed Noise [96.80184504268593]
グラデーション、クリッピングは、優れた高確率保証を導き出すアルゴリズムの鍵となる要素の1つである。
クリッピングは、合成および分散最適化の一般的な方法の収束を損なう可能性がある。
論文 参考訳（メタデータ） (2023-10-03T07:49:17Z) - High-Probability Bounds for Stochastic Optimization and Variational
Inequalities: the Case of Unbounded Variance [59.211456992422136]
制約の少ない仮定の下で高確率収束結果のアルゴリズムを提案する。
これらの結果は、標準機能クラスに適合しない問題を最適化するために検討された手法の使用を正当化する。
論文 参考訳（メタデータ） (2023-02-02T10:37:23Z) - Mirror Descent Strikes Again: Optimal Stochastic Convex Optimization
under Infinite Noise Variance [17.199063087458907]
我々は一様凸ミラーマップのクラスを用いてミラーDescentアルゴリズムの収束率を定量化する。
このアルゴリズムは明確な勾配クリッピングや正規化を必要としない。
我々は,1次オラクルのみを用いた他のアルゴリズムでは改善率を達成できないことを示す情報理論の下界を補完する。
論文 参考訳（メタデータ） (2022-02-23T17:08:40Z) - On the Convergence of mSGD and AdaGrad for Stochastic Optimization [0.696125353550498]
凸降下(SGD)は、過去10年間に機械学習に大きく開発され、広く応用されてきた。
モーメントベースのSGD(mSGD)や適応的勾配最適化(AdaGrad)など、多くの競合や応用においてSGDよりも優れている修正SGD型アルゴリズムもある。
我々は,機械学習における任意の滑らかな(不可能かもしれない)損失関数に対するmSGDとAdaGradの収束解析に着目する。
論文 参考訳（メタデータ） (2022-01-26T22:02:21Z) - Optimal Rates for Random Order Online Optimization [60.011653053877126]
敵が損失関数を選択できるカテットガルバー2020onlineについて検討するが、一様にランダムな順序で提示される。
2020onlineアルゴリズムが最適境界を達成し,安定性を著しく向上することを示す。
論文 参考訳（メタデータ） (2021-06-29T09:48:46Z) - Stochastic optimization with momentum: convergence, fluctuations, and
traps avoidance [0.0]
本稿では,重球法,ネステロフ加速勾配法(S-NAG),広く使用されているアダム法など,勾配勾配勾配のいくつかの変種を統一する一般最適化手法について検討する。
この回避は、非自明な常微分方程式のノイズ離散化として研究される。
論文 参考訳（メタデータ） (2020-12-07T19:14:49Z) - Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth
Nonlinear TD Learning [145.54544979467872]
本稿では,各ステップごとに1つのデータポイントしか必要としない2つの単一スケールシングルループアルゴリズムを提案する。
本研究の結果は, 同時一次および二重側収束の形で表される。
論文 参考訳（メタデータ） (2020-08-23T20:36:49Z) - Stability of Stochastic Gradient Descent on Nonsmooth Convex Losses [52.039438701530905]
任意のリプシッツ非平滑凸損失に対して,数種類の勾配勾配降下(SGD)に対して,鋭い上下境界を与える。
我々の限界は、極端に過剰な集団リスクを伴う、微分的にプライベートな非平滑凸最適化のための新しいアルゴリズムを導出することを可能にする。
論文 参考訳（メタデータ） (2020-06-12T02:45:21Z) - Fast Objective & Duality Gap Convergence for Non-Convex Strongly-Concave
Min-Max Problems with PL Condition [52.08417569774822]
本稿では,深層学習(深層AUC)により注目度が高まっている,円滑な非凹部min-max問題の解法に焦点をあてる。
論文 参考訳（メタデータ） (2020-06-12T00:32:21Z) - Convergence rates and approximation results for SGD and its
continuous-time counterpart [16.70533901524849]
本稿では,非増加ステップサイズを有する凸勾配Descent (SGD) の完全理論的解析を提案する。
まず、結合を用いた不均一微分方程式(SDE)の解により、SGDを確実に近似できることを示す。
連続的手法による決定論的および最適化手法の最近の分析において, 連続過程の長期的挙動と非漸近的境界について検討する。
論文 参考訳（メタデータ） (2020-04-08T18:31:34Z) - Stochastic Approximation with Markov Noise: Analysis and applications in
reinforcement learning [0.0]
マルコフ雑音によって駆動される2つの時間スケール近似の収束解析を初めて提示する。
両方の時間スケールにおける差分包摂を限定することで、フレームワークの挙動を分析する。
ポリシ評価アルゴリズムの関数近似における最初の情報的誤差境界を求める。
論文 参考訳（メタデータ） (2020-04-08T03:59:21Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。