論文の概要: The Benefits of Implicit Regularization from SGD in Least Squares
Problems
- arxiv url: http://arxiv.org/abs/2108.04552v1
- Date: Tue, 10 Aug 2021 09:56:47 GMT
- ステータス: 処理完了
- システム内更新日: 2021-08-11 14:27:38.492285
- Title: The Benefits of Implicit Regularization from SGD in Least Squares
Problems
- Title(参考訳): 最小二乗問題におけるSGDからの急激な正規化のメリット
- Authors: Difan Zou and Jingfeng Wu and Vladimir Braverman and Quanquan Gu and
Dean P. Foster and Sham M. Kakade
- Abstract要約: 勾配降下(SGD)はアルゴリズム正則化効果が強い。
我々は、(正規化されていない)平均SGDで得られる暗黙の正則化とリッジ回帰の明示的な正則化の比較を行う。
- 参考スコア(独自算出の注目度): 116.85246178212616
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Stochastic gradient descent (SGD) exhibits strong algorithmic regularization
effects in practice, which has been hypothesized to play an important role in
the generalization of modern machine learning approaches. In this work, we seek
to understand these issues in the simpler setting of linear regression
(including both underparameterized and overparameterized regimes), where our
goal is to make sharp instance-based comparisons of the implicit regularization
afforded by (unregularized) average SGD with the explicit regularization of
ridge regression. For a broad class of least squares problem instances (that
are natural in high-dimensional settings), we show: (1) for every problem
instance and for every ridge parameter, (unregularized) SGD, when provided with
logarithmically more samples than that provided to the ridge algorithm,
generalizes no worse than the ridge solution (provided SGD uses a tuned
constant stepsize); (2) conversely, there exist instances (in this wide problem
class) where optimally-tuned ridge regression requires quadratically more
samples than SGD in order to have the same generalization performance. Taken
together, our results show that, up to the logarithmic factors, the
generalization performance of SGD is always no worse than that of ridge
regression in a wide range of overparameterized problems, and, in fact, could
be much better for some problem instances. More generally, our results show how
algorithmic regularization has important consequences even in simpler
(overparameterized) convex settings.
- Abstract(参考訳): 確率勾配降下(SGD)はアルゴリズムの正則化効果が強く、現代の機械学習アプローチの一般化に重要な役割を果たしていると仮定されている。
本研究では,これらの問題を,(非正規化)平均SGDと隆起回帰の明示的な正則化による暗黙正則化の鋭いインスタンスベース比較を行うことを目標とする線形回帰(過パラメータ化と過パラメータ化の両方を含む)の簡易な設定で理解することを目的とする。
For a broad class of least squares problem instances (that are natural in high-dimensional settings), we show: (1) for every problem instance and for every ridge parameter, (unregularized) SGD, when provided with logarithmically more samples than that provided to the ridge algorithm, generalizes no worse than the ridge solution (provided SGD uses a tuned constant stepsize); (2) conversely, there exist instances (in this wide problem class) where optimally-tuned ridge regression requires quadratically more samples than SGD in order to have the same generalization performance.
本結果から,SGDの一般化性能は,対数的要因により,広範囲な過パラメータ化問題におけるリッジ回帰よりも常に劣っていることが示唆された。
より一般的には、より単純な(過パラメータ化された)凸設定においてもアルゴリズム正則化が重要な結果をもたらすことを示す。
関連論文リスト
- Improving Implicit Regularization of SGD with Preconditioning for Least Square Problems [19.995877680083105]
最小二乗問題に対する事前条件付き勾配降下(SGD)の一般化性能について検討した。
提案したプレコンディショニング行列は有限標本からのロバストな推定が可能なほど単純であることを示す。
論文 参考訳(メタデータ) (2024-03-13T14:42:06Z) - Risk Bounds of Accelerated SGD for Overparameterized Linear Regression [75.27846230182885]
加速度勾配降下(ASGD)は、深層学習におけるワークホースである。
既存の最適化理論は、ASGDのより高速な収束を説明することしかできないが、より優れた一般化を説明することはできない。
論文 参考訳(メタデータ) (2023-11-23T23:02:10Z) - A Unified Approach to Controlling Implicit Regularization via Mirror
Descent [18.536453909759544]
ミラー降下(MD)は勾配降下(GD)の顕著な一般化である
MDを効率的に実装することができ、適切な条件下での高速収束を享受できることを示す。
論文 参考訳(メタデータ) (2023-06-24T03:57:26Z) - Implicit Regularization or Implicit Conditioning? Exact Risk
Trajectories of SGD in High Dimensions [26.782342518986503]
勾配降下(SGD)は現代の機械学習の柱であり、様々な問題に対するゴート最適化アルゴリズムとして機能している。
HSGD形式をストリーミングSGDに適合させる方法を示し、ストリーミングSGDと比較してマルチパスSGDの過大なリスクを正確に予測できることを示す。
論文 参考訳(メタデータ) (2022-06-15T02:32:26Z) - Risk Bounds of Multi-Pass SGD for Least Squares in the Interpolation
Regime [127.21287240963859]
勾配降下(SGD)は最適化と一般化の両方において優れた性能を持つため、大きな成功を収めている。
本稿では,マルチパスSGDの一般化を強く特徴付けることを目的とする。
我々は,SGDが同じレベルの過剰リスクを達成するためには,GD以上を必要とするが,勾配評価の回数を削減できることを示した。
論文 参考訳(メタデータ) (2022-03-07T06:34:53Z) - Benign Underfitting of Stochastic Gradient Descent [72.38051710389732]
本研究では,適切な学習データを得ることで,一般化性能を実現する「従来型」学習ルールとして,勾配降下度(SGD)がどの程度理解されるかを検討する。
類似現象が起こらない近縁な交換SGDを解析し、その集団リスクが実際に最適な速度で収束することを証明する。
論文 参考訳(メタデータ) (2022-02-27T13:25:01Z) - Last Iterate Risk Bounds of SGD with Decaying Stepsize for
Overparameterized Linear Regression [122.70478935214128]
勾配降下(SGD)は、多くのディープラーニングアプリケーションでよく一般化されている。
本稿では, 崩壊段階のSGDの最終反復リスク境界に関する問題依存解析を行う。
論文 参考訳(メタデータ) (2021-10-12T17:49:54Z) - Benign Overfitting of Constant-Stepsize SGD for Linear Regression [122.70478935214128]
帰納バイアスは 経験的に過剰フィットを防げる中心的存在です
この研究は、この問題を最も基本的な設定として考慮している: 線形回帰に対する定数ステップサイズ SGD。
我々は、(正規化されていない)SGDで得られるアルゴリズム正則化と、通常の最小二乗よりも多くの顕著な違いを反映する。
論文 参考訳(メタデータ) (2021-03-23T17:15:53Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。