論文の概要: The Dimension Strikes Back with Gradients: Generalization of Gradient
Methods in Stochastic Convex Optimization
- arxiv url: http://arxiv.org/abs/2401.12058v1
- Date: Mon, 22 Jan 2024 15:50:32 GMT
- ステータス: 処理完了
- システム内更新日: 2024-01-23 13:37:38.331952
- Title: The Dimension Strikes Back with Gradients: Generalization of Gradient
Methods in Stochastic Convex Optimization
- Title（参考訳）: 勾配による次元逆戻り:確率凸最適化における勾配法の一般化
- Authors: Matan Schliserman and Uri Sherman and Tomer Koren
- Abstract要約: 基本凸最適化設定における勾配法の一般化性能について検討する。
同様の構成手法を適用すると、SGDのサンプル複雑性に対して同様の$Omega(sqrtd)$ローバウンドが得られ、非自明な経験的誤差に達することが示される。
- 参考スコア（独自算出の注目度）: 30.26365073195728
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study the generalization performance of gradient methods in the
fundamental stochastic convex optimization setting, focusing on its dimension
dependence. First, for full-batch gradient descent (GD) we give a construction
of a learning problem in dimension $d=O(n^2)$, where the canonical version of
GD (tuned for optimal performance of the empirical risk) trained with $n$
training examples converges, with constant probability, to an approximate
empirical risk minimizer with $\Omega(1)$ population excess risk. Our bound
translates to a lower bound of $\Omega (\sqrt{d})$ on the number of training
examples required for standard GD to reach a non-trivial test error, answering
an open question raised by Feldman (2016) and Amir, Koren, and Livni (2021b)
and showing that a non-trivial dimension dependence is unavoidable.
Furthermore, for standard one-pass stochastic gradient descent (SGD), we show
that an application of the same construction technique provides a similar
$\Omega(\sqrt{d})$ lower bound for the sample complexity of SGD to reach a
non-trivial empirical error, despite achieving optimal test performance. This
again provides an exponential improvement in the dimension dependence compared
to previous work (Koren, Livni, Mansour, and Sherman, 2022), resolving an open
question left therein.
- Abstract（参考訳）: 基本確率凸最適化設定における勾配法の一般化性能について検討し,その次元依存性に着目した。
まず、フルバッチ勾配降下 (gd) に対して、d=o(n^2)$ 次元の学習問題の構成を与える。ここでは、n$ のトレーニング例で訓練された gd の標準版(経験的リスクの最適性能を調整)は、一定の確率で、$\omega(1)$ の人口過剰リスクを持つ近似経験的リスク最小化に収束する。
我々の境界は、標準GDが非自明なテスト誤差に到達するのに必要なトレーニング例の数に対して$\Omega (\sqrt{d})$の低い境界に翻訳され、Feldman (2016) と Amir, Koren, Livni (2021b) が提起したオープンな質問に答え、非自明な次元依存は避けられないことを示す。
さらに,sgd (standard one-pass stochasticgradient descent) では,sgd のサンプル複雑性に対して同じ$\omega(\sqrt{d})$lowbound を同じ構成手法で適用することで,最適テスト性能を保ったにもかかわらず,非自明な経験的誤差に達することを示した。
このことは、以前の研究 (Koren, Livni, Mansour, and Sherman, 2022) と比較して次元依存の指数関数的な改善をもたらし、そこで残された開問題を解決する。
関連論文リスト
- Convergence Rate Analysis of LION [54.28350823319057]
LION は、勾配カルシュ=クーン=T (sqrtdK-)$で測定された $cal(sqrtdK-)$ の反復を収束する。
従来のSGDと比較して,LIONは損失が小さく,性能も高いことを示す。
論文 参考訳（メタデータ） (2024-11-12T11:30:53Z) - Convergence Analysis of Adaptive Gradient Methods under Refined Smoothness and Noise Assumptions [18.47705532817026]
AdaGradは特定の条件下では$d$でSGDより優れていることを示す。
これを動機として、目的物の滑らかさ構造と勾配のばらつきを仮定する。
論文 参考訳（メタデータ） (2024-06-07T02:55:57Z) - Restricted Strong Convexity of Deep Learning Models with Smooth
Activations [31.003601717265006]
本研究では,スムーズなアクティベーション機能を持つディープラーニングモデルの最適化問題について検討する。
Restricted Strong Convexity (RSC) に基づく最適化の新しい解析手法を提案する。
深層学習モデルのためのRCCに基づくGDの幾何収束性を確立するための最初の結果である。
論文 参考訳（メタデータ） (2022-09-29T21:24:26Z) - Benign Underfitting of Stochastic Gradient Descent [72.38051710389732]
本研究では,適切な学習データを得ることで,一般化性能を実現する「従来型」学習ルールとして,勾配降下度(SGD)がどの程度理解されるかを検討する。
類似現象が起こらない近縁な交換SGDを解析し、その集団リスクが実際に最適な速度で収束することを証明する。
論文 参考訳（メタデータ） (2022-02-27T13:25:01Z) - A general sample complexity analysis of vanilla policy gradient [101.16957584135767]
政策勾配(PG)は、最も一般的な強化学習(RL)問題の1つである。
PG軌道の「バニラ」理論的理解は、RL問題を解く最も一般的な方法の1つである。
論文 参考訳（メタデータ） (2021-07-23T19:38:17Z) - SGD Generalizes Better Than GD (And Regularization Doesn't Help) [39.588906680621825]
我々は、勾配勾配(SGD)の一般化性能と全バッチ勾配(GD)の分離結果を与える。
同じステップ数で、GD はオーバーフィットし、$Omega(1)$ generalization error で解を出力することを示した。
本稿では,GDによる経験的リスクの最小化が,基本的には上記の結果を変えるものではないことを論じ,安定性,暗黙バイアス,一般化における学習アルゴリズムの役割を再考する。
論文 参考訳（メタデータ） (2021-02-01T19:18:40Z) - Robust High Dimensional Expectation Maximization Algorithm via Trimmed
Hard Thresholding [24.184520829631587]
本研究では,高次元空間における任意の劣化サンプルを用いた潜在変数モデルの推定問題について検討する。
本稿では,トリミング勾配ステップを付加したトリミング予測最大化法を提案する。
アルゴリズムは汚損防止であり、幾何学的に(ほぼ)最適統計率に収束することを示す。
論文 参考訳（メタデータ） (2020-10-19T15:00:35Z) - Large-Scale Methods for Distributionally Robust Optimization [53.98643772533416]
我々のアルゴリズムは、トレーニングセットのサイズとパラメータの数によらず、多くの評価勾配を必要とすることを証明している。
MNIST と ImageNet の実験により,本手法の 9-36 倍の効率性を持つアルゴリズムの理論的スケーリングが確認された。
論文 参考訳（メタデータ） (2020-10-12T17:41:44Z) - Private Stochastic Non-Convex Optimization: Adaptive Algorithms and
Tighter Generalization Bounds [72.63031036770425]
有界非次元最適化のための差分プライベート(DP)アルゴリズムを提案する。
標準勾配法に対する経験的優位性について,2つの一般的なディープラーニング手法を実証する。
論文 参考訳（メタデータ） (2020-06-24T06:01:24Z) - On the Almost Sure Convergence of Stochastic Gradient Descent in
Non-Convex Problems [75.58134963501094]
本稿では,勾配降下(SGD)の軌跡を解析する。
我々はSGDが厳格なステップサイズポリシーのために1ドルでサドルポイント/マニフォールドを避けることを示す。
論文 参考訳（メタデータ） (2020-06-19T14:11:26Z) - Better Theory for SGD in the Nonconvex World [2.6397379133308214]
大規模な非最適化問題は、現代の機械学習ではユビキタスである。
我々は, 広範囲の合成ミニバッチサイズがグラディエントDescent (SG) 問題に与える影響について実験を行った。
論文 参考訳（メタデータ） (2020-02-09T09:56:06Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。