論文の概要: Taming Nonconvex Stochastic Mirror Descent with General Bregman
Divergence
- arxiv url: http://arxiv.org/abs/2402.17722v1
- Date: Tue, 27 Feb 2024 17:56:49 GMT
- ステータス: 処理完了
- システム内更新日: 2024-02-28 15:03:49.659280
- Title: Taming Nonconvex Stochastic Mirror Descent with General Bregman
Divergence
- Title(参考訳): 一般ブレグマン発散を伴う非凸確率ミラー降下
- Authors: Ilyas Fatkhullin, Niao He
- Abstract要約: 本稿では、現代の非最適化設定における勾配フォワードミラー(SMD)の収束を再考する。
トレーニングのために,線形ネットワーク問題に対する確率収束アルゴリズムを開発した。
- 参考スコア(独自算出の注目度): 25.717501580080846
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: This paper revisits the convergence of Stochastic Mirror Descent (SMD) in the
contemporary nonconvex optimization setting. Existing results for batch-free
nonconvex SMD restrict the choice of the distance generating function (DGF) to
be differentiable with Lipschitz continuous gradients, thereby excluding
important setups such as Shannon entropy. In this work, we present a new
convergence analysis of nonconvex SMD supporting general DGF, that overcomes
the above limitations and relies solely on the standard assumptions. Moreover,
our convergence is established with respect to the Bregman Forward-Backward
envelope, which is a stronger measure than the commonly used squared norm of
gradient mapping. We further extend our results to guarantee high probability
convergence under sub-Gaussian noise and global convergence under the
generalized Bregman Proximal Polyak-{\L}ojasiewicz condition. Additionally, we
illustrate the advantages of our improved SMD theory in various nonconvex
machine learning tasks by harnessing nonsmooth DGFs. Notably, in the context of
nonconvex differentially private (DP) learning, our theory yields a simple
algorithm with a (nearly) dimension-independent utility bound. For the problem
of training linear neural networks, we develop provably convergent stochastic
algorithms.
- Abstract(参考訳): 本稿では, 現代の非凸最適化設定におけるSMD(Stochastic Mirror Descent)の収束を再考する。
バッチフリー非凸SMDの既存の結果は、リプシッツ連続勾配と微分可能な距離生成関数(DGF)の選択を制限し、シャノンエントロピーのような重要な設定を除外する。
本稿では,上記の制限を克服し,標準仮定のみに依存する一般dgfをサポートする非凸smdの新しい収束解析を提案する。
さらに、我々の収束は、一般的に用いられる勾配写像の平方ノルムよりも強い測度であるブレグマンフォワード-バックワードエンベロープに対して確立される。
さらに,この結果をさらに拡張して,サブガウス雑音下での高確率収束と一般化されたブレグマン近位ポリak-{\l}ojasiewicz条件下での大域収束を保証する。
さらに,非滑らかなDGFを利用した各種非凸機械学習タスクにおける改良されたSMD理論の利点について述べる。
特に、非凸微分的プライベート(dp)学習の文脈では、この理論は(ほぼ)次元非依存なユーティリティ境界を持つ単純なアルゴリズムをもたらす。
線形ニューラルネットワークを訓練する問題に対して,確率収束確率アルゴリズムを開発した。
関連論文リスト
- Error Feedback under $(L_0,L_1)$-Smoothness: Normalization and Momentum [56.37522020675243]
機械学習の幅広い問題にまたがる正規化誤差フィードバックアルゴリズムに対する収束の最初の証明を提供する。
提案手法では,許容可能なステップサイズが大きくなったため,新しい正規化エラーフィードバックアルゴリズムは,各種タスクにおける非正規化エラーよりも優れていた。
論文 参考訳(メタデータ) (2024-10-22T10:19:27Z) - Stable Nonconvex-Nonconcave Training via Linear Interpolation [51.668052890249726]
本稿では,ニューラルネットワークトレーニングを安定化(大規模)するための原理的手法として,線形アヘッドの理論解析を提案する。
最適化過程の不安定性は、しばしば損失ランドスケープの非単調性によって引き起こされるものであり、非拡張作用素の理論を活用することによって線型性がいかに役立つかを示す。
論文 参考訳(メタデータ) (2023-10-20T12:45:12Z) - Curvature-Independent Last-Iterate Convergence for Games on Riemannian
Manifolds [77.4346324549323]
本研究では, 多様体の曲率に依存しないステップサイズが, 曲率非依存かつ直線的最終点収束率を達成することを示す。
我々の知る限りでは、曲率非依存率や/または最終点収束の可能性はこれまでに検討されていない。
論文 参考訳(メタデータ) (2023-06-29T01:20:44Z) - Stochastic Methods in Variational Inequalities: Ergodicity, Bias and
Refinements [19.524063429548278]
Extragradient (SEG) と Gradient Descent Ascent (SGDA) は min-max 最適化と変分不等式問題に対する優越アルゴリズムである。
これらのアルゴリズムに固有の本質的な構造を定量化し定量化するための我々の取り組み。
定数のステップサイズSEG/SGDAを時間同質マルコフ連鎖として再キャストすることにより、大数の第一種法則と中心極限定理を確立する。
論文 参考訳(メタデータ) (2023-06-28T18:50:07Z) - Online Bootstrap Inference with Nonconvex Stochastic Gradient Descent
Estimator [0.0]
本稿では,凸問題の文脈における統計的推論のための勾配降下(SGD)の理論的性質について検討する。
多重誤差最小値を含む2つの干渉手順を提案する。
論文 参考訳(メタデータ) (2023-06-03T22:08:10Z) - Benign Underfitting of Stochastic Gradient Descent [72.38051710389732]
本研究では,適切な学習データを得ることで,一般化性能を実現する「従来型」学習ルールとして,勾配降下度(SGD)がどの程度理解されるかを検討する。
類似現象が起こらない近縁な交換SGDを解析し、その集団リスクが実際に最適な速度で収束することを証明する。
論文 参考訳(メタデータ) (2022-02-27T13:25:01Z) - On the Double Descent of Random Features Models Trained with SGD [78.0918823643911]
勾配降下(SGD)により最適化された高次元におけるランダム特徴(RF)回帰特性について検討する。
本研究では, RF回帰の高精度な非漸近誤差境界を, 定常および適応的なステップサイズSGD設定の下で導出する。
理論的にも経験的にも二重降下現象を観察する。
論文 参考訳(メタデータ) (2021-10-13T17:47:39Z) - SGD for Structured Nonconvex Functions: Learning Rates, Minibatching and
Interpolation [17.199023009789308]
予想されるSGD(SGD)の仮定は、非アーティザン関数に対して日常的に使われている。
本稿では,スムーズな非線形設定への収束のパラダイムを示す。
また,異なるステップサイズ条件の理論的保証も提供する。
論文 参考訳(メタデータ) (2020-06-18T07:05:56Z) - Stability of Stochastic Gradient Descent on Nonsmooth Convex Losses [52.039438701530905]
任意のリプシッツ非平滑凸損失に対して,数種類の勾配勾配降下(SGD)に対して,鋭い上下境界を与える。
我々の限界は、極端に過剰な集団リスクを伴う、微分的にプライベートな非平滑凸最適化のための新しいアルゴリズムを導出することを可能にする。
論文 参考訳(メタデータ) (2020-06-12T02:45:21Z) - Better Theory for SGD in the Nonconvex World [2.6397379133308214]
大規模な非最適化問題は、現代の機械学習ではユビキタスである。
我々は, 広範囲の合成ミニバッチサイズがグラディエントDescent (SG) 問題に与える影響について実験を行った。
論文 参考訳(メタデータ) (2020-02-09T09:56:06Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。