論文の概要: Algorithmic Stability of Heavy-Tailed Stochastic Gradient Descent on Least Squares

• arxiv url: http://arxiv.org/abs/2206.01274v1
• Date: Thu, 2 Jun 2022 19:59:48 GMT
• ステータス: 処理完了
• システム内更新日: 2022-06-07 06:47:08.719310
• Title: Algorithmic Stability of Heavy-Tailed Stochastic Gradient Descent on Least Squares
• Title（参考訳）: 重り付き確率勾配の最小方形におけるアルゴリズム安定性
• Authors: Anant Raj, Melih Barsbey, Mert G\"urb\"uzbalaban, Lingjiong Zhu and Umut \c{S}im\c{s}ekli
• Abstract要約: 近年の研究では、重い尾が最適化において出現し、尾の重みが一般化誤差と関連していることが示されている。 アルゴリズム安定性のレンズによる勾配降下(SGD)のテール挙動と一般化特性の新たなリンクを確立する。 我々は、合成および実際のニューラルネットワーク実験で理論を支持する。
• 参考スコア（独自算出の注目度）: 12.2950446921662
• License: http://creativecommons.org/publicdomain/zero/1.0/
• Abstract: Recent studies have shown that heavy tails can emerge in stochastic optimization and that the heaviness of the tails has links to the generalization error. While these studies have shed light on interesting aspects of the generalization behavior in modern settings, they relied on strong topological and statistical regularity assumptions, which are hard to verify in practice. Furthermore, it has been empirically illustrated that the relation between heavy tails and generalization might not always be monotonic in practice, contrary to the conclusions of existing theory. In this study, we establish novel links between the tail behavior and generalization properties of stochastic gradient descent (SGD), through the lens of algorithmic stability. We consider a quadratic optimization problem and use a heavy-tailed stochastic differential equation as a proxy for modeling the heavy-tailed behavior emerging in SGD. We then prove uniform stability bounds, which reveal the following outcomes: (i) Without making any exotic assumptions, we show that SGD will not be stable if the stability is measured with the squared-loss $x\mapsto x^2$, whereas it in turn becomes stable if the stability is instead measured with a surrogate loss $x\mapsto |x|^p$ with some $p<2$. (ii) Depending on the variance of the data, there exists a \emph{`threshold of heavy-tailedness'} such that the generalization error decreases as the tails become heavier, as long as the tails are lighter than this threshold. This suggests that the relation between heavy tails and generalization is not globally monotonic. (iii) We prove matching lower-bounds on uniform stability, implying that our bounds are tight in terms of the heaviness of the tails. We support our theory with synthetic and real neural network experiments.
• Abstract（参考訳）: 近年の研究では、重い尾は確率的最適化において出現し、尾の重みは一般化誤差と関連があることが示されている。 これらの研究は、現代における一般化行動の興味深い側面に光を当ててきたが、実際には検証が難しい強い位相的および統計的正則性の仮定に依存していた。 さらに、重尾と一般化の関係は、既存の理論の結論とは対照的に、実際には必ずしも単調であるとは限らないことが実証的に示されている。 本研究では,確率勾配降下(SGD)のテール挙動と一般化特性を,アルゴリズム的安定性のレンズを通して新たなリンクを確立する。 二次最適化問題を考えると,重み付き確率微分方程式をsgdに現れる重み付き振舞いのモデル化の指標として用いる。 次に、一様安定性境界を証明し、以下の結果を明らかにする。 (i) エキゾチックな仮定をすることなく、安定度が2乗損失の$x\mapsto x^2$ で測定された場合、sgd は安定しないが、安定度がサロゲート損失 $x\mapsto |x|^p$ で測定されても安定になることを示した。 (ii) データのばらつきによっては、このしきい値よりもテールが軽い限り、テールが重くなるにつれて一般化誤差が減少する'emph{`threshold of Heavy-tailedness'} が存在する。 これは、重い尾と一般化の関係が全体単調ではないことを示唆する。 3) 均一安定性の低いバウンドが一致することを証明し, テールの重みの点で我々のバウンドがきついことを示唆する。 我々は、合成および実際のニューラルネットワーク実験で理論を支持する。

関連論文リスト

• The Implicit Regularization of Dynamical Stability in Stochastic Gradient Descent [32.25490196411385]
  動的安定レンズによる勾配降下(SGD)の暗黙的正則化について検討する。 2層ReLUネットワークと対角線ネットワークの一般化特性を解析する。
  論文  参考訳（メタデータ） (2023-05-27T14:54:21Z)
• 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)
• Fat-Tailed Variational Inference with Anisotropic Tail Adaptive Flows [53.32246823168763]
  脂肪尾密度は、一般に、ロバストモデルとスケール混合における後縁および辺縁分布として生じる。 我々はまず、尾が尾崩壊の速度にどのように影響するかを定量化することで、リプシッツフローの尾に関する以前の理論を改善した。 次に、テール異方性に敏感なテールパラメータの代替理論を開発する。
  論文  参考訳（メタデータ） (2022-05-16T18:03:41Z)
• 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)
• Benign Overfitting of Constant-Stepsize SGD for Linear Regression [122.70478935214128]
  帰納バイアスは 経験的に過剰フィットを防げる中心的存在です この研究は、この問題を最も基本的な設定として考慮している: 線形回帰に対する定数ステップサイズ SGD。 我々は、(正規化されていない)SGDで得られるアルゴリズム正則化と、通常の最小二乗よりも多くの顕著な違いを反映する。
  論文  参考訳（メタデータ） (2021-03-23T17:15:53Z)
• Convergence Rates of Stochastic Gradient Descent under Infinite Noise Variance [14.06947898164194]
  ヘビーテールは様々なシナリオで勾配降下 (sgd) で現れる。 SGDの収束保証は、潜在的に無限のばらつきを持つ状態依存性および重尾ノイズ下で提供します。 その結果,SGDは無限に分散した重尾雑音下であっても,地球最適値に収束できることが示された。
  論文  参考訳（メタデータ） (2021-02-20T13:45:11Z)
• Toward Better Generalization Bounds with Locally Elastic Stability [41.7030651617752]
  局所的な弾性安定性は、一様安定性に基づいて導出されたものよりも厳密な一般化境界を意味すると論じる。 我々は、有界支持ベクトルマシン、正規化最小二乗回帰、勾配降下の例を再考する。
  論文  参考訳（メタデータ） (2020-10-27T02:04:53Z)
• Fine-Grained Analysis of Stability and Generalization for Stochastic Gradient Descent [55.85456985750134]
  我々は,SGDの反復的リスクによって制御される新しい境界を開発する,平均モデル安定性と呼ばれる新しい安定性尺度を導入する。 これにより、最良のモデルの振舞いによって一般化境界が得られ、低雑音環境における最初の既知の高速境界が導かれる。 我々の知る限りでは、このことはSGDの微分不能な損失関数でさえも初めて知られている安定性と一般化を与える。
  論文  参考訳（メタデータ） (2020-06-15T06:30:19Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。