論文の概要: Large deviations rates for stochastic gradient descent with strongly
convex functions
- arxiv url: http://arxiv.org/abs/2211.00969v1
- Date: Wed, 2 Nov 2022 09:15:26 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-03 13:00:28.424637
- Title: Large deviations rates for stochastic gradient descent with strongly
convex functions
- Title(参考訳): 強凸関数をもつ確率勾配降下に対する大きな偏差率
- Authors: Dragana Bajovic, Dusan Jakovetic, Soummya Kar
- Abstract要約: 勾配降下を伴う一般高確率境界の研究のための公式な枠組みを提供する。
強い凸関数を持つSGDの上限となる大きな偏差が見つかる。
- 参考スコア(独自算出の注目度): 11.247580943940916
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Recent works have shown that high probability metrics with stochastic
gradient descent (SGD) exhibit informativeness and in some cases advantage over
the commonly adopted mean-square error-based ones. In this work we provide a
formal framework for the study of general high probability bounds with SGD,
based on the theory of large deviations. The framework allows for a generic
(not-necessarily bounded) gradient noise satisfying mild technical assumptions,
allowing for the dependence of the noise distribution on the current iterate.
Under the preceding assumptions, we find an upper large deviations bound for
SGD with strongly convex functions. The corresponding rate function captures
analytical dependence on the noise distribution and other problem parameters.
This is in contrast with conventional mean-square error analysis that captures
only the noise dependence through the variance and does not capture the effect
of higher order moments nor interplay between the noise geometry and the shape
of the cost function. We also derive exact large deviation rates for the case
when the objective function is quadratic and show that the obtained function
matches the one from the general upper bound hence showing the tightness of the
general upper bound. Numerical examples illustrate and corroborate theoretical
findings.
- Abstract(参考訳): 近年の研究では、確率勾配降下(SGD)の高い確率測定値が情報性を示し、場合によっては平均二乗誤差ベースよりも有利であることが示されている。
本研究では,大偏差の理論に基づくsgdを用いた一般高確率境界の研究のための形式的枠組みを提案する。
このフレームワークは、穏やかな技術的仮定を満たす一般的な(必ずしも境界のない)勾配ノイズを許容し、現在の反復にノイズ分布の依存性を許容する。
前述した仮定の下では、強い凸関数を持つSGDに対して有界な大きな偏差が見つかる。
対応するレート関数は、ノイズ分布および他の問題パラメータに対する解析的依存性をキャプチャする。
これは、分散によるノイズ依存のみをキャプチャし、高次モーメントの効果やノイズ幾何とコスト関数の形状との相互作用をキャプチャしない従来の平均二乗誤差解析とは対照的である。
また,目的関数が2次関数である場合の偏差率の絶対値から導出し,得られた関数が一般上界からの偏差と一致することを示すことにより,一般上界の密度を示す。
数値的な例は理論的な発見を示し、裏付ける。
関連論文リスト
- High-Probability Bounds for Stochastic Optimization and Variational
Inequalities: the Case of Unbounded Variance [59.211456992422136]
制約の少ない仮定の下で高確率収束結果のアルゴリズムを提案する。
これらの結果は、標準機能クラスに適合しない問題を最適化するために検討された手法の使用を正当化する。
論文 参考訳(メタデータ) (2023-02-02T10:37:23Z) - Algorithmic Stability of Heavy-Tailed SGD with General Loss Functions [13.431453056203226]
ワッサースタイン降下(SGD)における重尾現象は、いくつかの経験的な観測が報告されている。
本稿では一般化関数と一般勾配関数のバウンダリを開発する。
彼らは最近、損失関数の一般性のおかげで、経験的な観測により多くの光を当てた。
論文 参考訳(メタデータ) (2023-01-27T17:57:35Z) - Clipped Stochastic Methods for Variational Inequalities with
Heavy-Tailed Noise [64.85879194013407]
単調なVIPと非単調なVIPの解法における信頼度に対数的依存を持つ最初の高確率結果が証明された。
この結果は光尾の場合で最もよく知られたものと一致し,非単調な構造問題に新鮮である。
さらに,多くの実用的な定式化の勾配雑音が重く,クリッピングによりSEG/SGDAの性能が向上することを示す。
論文 参考訳(メタデータ) (2022-06-02T15:21:55Z) - Nonconvex Stochastic Scaled-Gradient Descent and Generalized Eigenvector
Problems [98.34292831923335]
オンライン相関解析の問題から,emphStochastic Scaled-Gradient Descent (SSD)アルゴリズムを提案する。
我々はこれらのアイデアをオンライン相関解析に適用し、局所収束率を正規性に比例した最適な1時間スケールのアルゴリズムを初めて導いた。
論文 参考訳(メタデータ) (2021-12-29T18:46:52Z) - On the Double Descent of Random Features Models Trained with SGD [78.0918823643911]
勾配降下(SGD)により最適化された高次元におけるランダム特徴(RF)回帰特性について検討する。
本研究では, RF回帰の高精度な非漸近誤差境界を, 定常および適応的なステップサイズSGD設定の下で導出する。
理論的にも経験的にも二重降下現象を観察する。
論文 参考訳(メタデータ) (2021-10-13T17:47:39Z) - Global Convergence and Stability of Stochastic Gradient Descent [0.0]
我々は,SGDがほぼ任意の非特異性および雑音モデルの下で定常点に収束することを示す。
我々は,SGDがグローバルな信頼の収束に関する様々な問題に適用可能であることを示す。
論文 参考訳(メタデータ) (2021-10-04T19:00:50Z) - Deconfounded Score Method: Scoring DAGs with Dense Unobserved
Confounding [101.35070661471124]
本研究では,観測データ分布に特徴的フットプリントが残っており,突発的・因果的影響を解消できることを示す。
汎用ソルバで実装し,高次元問題へのスケールアップが可能なスコアベース因果検出アルゴリズムを提案する。
論文 参考訳(メタデータ) (2021-03-28T11:07:59Z) - On the Convergence of SGD with Biased Gradients [28.400751656818215]
偏り勾配法 (SGD) の導出領域を解析し, 個々の更新を圧縮によって劣化させる。
偏差精度と収束率の影響の程度を定量化する。
論文 参考訳(メタデータ) (2020-07-31T19:37:59Z) - Shape Matters: Understanding the Implicit Bias of the Noise Covariance [76.54300276636982]
勾配降下のノイズはパラメータ化モデルに対するトレーニングにおいて重要な暗黙の正則化効果をもたらす。
ミニバッチやラベルの摂動によって引き起こされるパラメータ依存ノイズはガウスノイズよりもはるかに効果的であることを示す。
分析の結果,パラメータ依存ノイズは局所最小値に偏りを生じさせるが,球状ガウス雑音は生じないことがわかった。
論文 参考訳(メタデータ) (2020-06-15T18:31:02Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。