論文の概要: The Sample Complexity of Gradient Descent in Stochastic Convex Optimization
- arxiv url: http://arxiv.org/abs/2404.04931v1
- Date: Sun, 7 Apr 2024 12:07:33 GMT
- ステータス: 処理完了
- システム内更新日: 2024-04-09 18:51:34.454545
- Title: The Sample Complexity of Gradient Descent in Stochastic Convex Optimization
- Title(参考訳): 確率凸最適化における勾配輝度のサンプル複素性
- Authors: Roi Livni,
- Abstract要約: フルバッチ勾配 Descent の一般化誤差は $tilde Theta(d/m + 1/sqrtm)$ であり、$d$ は次元、$m$ は標本サイズである。
これは、Emphworst型経験的リスク最小化器のサンプル複雑さと一致する。
- 参考スコア(独自算出の注目度): 14.268363583731848
- License: http://creativecommons.org/licenses/by-sa/4.0/
- Abstract: We analyze the sample complexity of full-batch Gradient Descent (GD) in the setup of non-smooth Stochastic Convex Optimization. We show that the generalization error of GD, with (minmax) optimal choice of hyper-parameters, can be $\tilde \Theta(d/m + 1/\sqrt{m})$, where $d$ is the dimension and $m$ is the sample size. This matches the sample complexity of \emph{worst-case} empirical risk minimizers. That means that, in contrast with other algorithms, GD has no advantage over naive ERMs. Our bound follows from a new generalization bound that depends on both the dimension as well as the learning rate and number of iterations. Our bound also shows that, for general hyper-parameters, when the dimension is strictly larger than number of samples, $T=\Omega(1/\epsilon^4)$ iterations are necessary to avoid overfitting. This resolves an open problem by \citet*{schliserman2024dimension, amir2021sgd}, and improves over previous lower bounds that demonstrated that the sample size must be at least square root of the dimension.
- Abstract(参考訳): 我々は,非滑らかな確率凸最適化のセットアップにおいて,GD (Full-batch Gradient Descent) のサンプル複雑性を解析した。
極小パラメータを最適に選択した GD の一般化誤差は $\tilde \Theta(d/m + 1/\sqrt{m})$ であり、$d$ は次元、$m$ は標本サイズである。
これは \emph{worst-case} 経験的リスク最小化器のサンプル複雑性と一致する。
つまり、他のアルゴリズムとは対照的に、GDは単純なERMよりも有利である。
我々の境界は、次元と学習率と反復数の両方に依存する新しい一般化境界から従う。
我々のバウンダリはまた、一般のハイパーパラメーターに対して、次元がサンプルの数より厳密に大きい場合、$T=\Omega(1/\epsilon^4)$ iterationsはオーバーフィッティングを避けるために必要であることを示している。
これにより、開問題は \citet*{schliserman2024dimension, amir2021sgd} によって解決され、サンプルサイズが次元の少なくとも2乗根でなければならないことを示す以前の下界よりも改善される。
関連論文リスト
- The Dimension Strikes Back with Gradients: Generalization of Gradient
Methods in Stochastic Convex Optimization [30.26365073195728]
基本凸最適化設定における勾配法の一般化性能について検討する。
同様の構成手法を適用すると、SGDのサンプル複雑性に対して同様の$Omega(sqrtd)$ローバウンドが得られ、非自明な経験的誤差に達することが示される。
論文 参考訳(メタデータ) (2024-01-22T15:50:32Z) - The Sample Complexity Of ERMs In Stochastic Convex Optimization [13.896417716930687]
実際に$tildeO(fracdepsilon+frac1epsilon2)$データポイントも十分であることを示す。
さらに、この結果を一般化し、全ての凸体に対して同様の上界が成り立つことを示す。
論文 参考訳(メタデータ) (2023-11-09T14:29:25Z) - Stochastic Approximation Approaches to Group Distributionally Robust
Optimization [96.26317627118912]
群分散ロバスト最適化(GDRO)
オンライン学習技術は、各ラウンドに必要なサンプル数をm$から1$に減らし、同じサンプルを保持する。
分布依存収束率を導出できる重み付きGDROの新規な定式化。
論文 参考訳(メタデータ) (2023-02-18T09:24:15Z) - Best Policy Identification in Linear MDPs [70.57916977441262]
縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。
複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
論文 参考訳(メタデータ) (2022-08-11T04:12:50Z) - Multi-block-Single-probe Variance Reduced Estimator for Coupled
Compositional Optimization [49.58290066287418]
構成問題の複雑さを軽減するために,MSVR (Multi-block-probe Variance Reduced) という新しい手法を提案する。
本研究の結果は, 試料の複雑さの順序や強靭性への依存など, 様々な面で先行して改善された。
論文 参考訳(メタデータ) (2022-07-18T12:03:26Z) - Stochastic regularized majorization-minimization with weakly convex and
multi-convex surrogates [0.0]
提案アルゴリズムの最初の最適性ギャップは,非テンソル依存データ設定下での様々な手法の期待損失率で減衰することを示す。
非テンション依存データ設定の下で, 各種手法の収束点を求める。
論文 参考訳(メタデータ) (2022-01-05T15:17:35Z) - The Sample Complexity of Robust Covariance Testing [56.98280399449707]
i. i. d.
形式 $Z = (1-epsilon) X + epsilon B$ の分布からのサンプル。ここで $X$ はゼロ平均で未知の共分散である Gaussian $mathcalN(0, Sigma)$ である。
汚染がない場合、事前の研究は、$O(d)$サンプルを使用するこの仮説テストタスクの単純なテスターを与えた。
サンプル複雑性の上限が $omega(d2)$ for $epsilon$ an arbitrarily small constant and $gamma であることを証明します。
論文 参考訳(メタデータ) (2020-12-31T18:24:41Z) - Robust High Dimensional Expectation Maximization Algorithm via Trimmed
Hard Thresholding [24.184520829631587]
本研究では,高次元空間における任意の劣化サンプルを用いた潜在変数モデルの推定問題について検討する。
本稿では,トリミング勾配ステップを付加したトリミング予測最大化法を提案する。
アルゴリズムは汚損防止であり、幾何学的に(ほぼ)最適統計率に収束することを示す。
論文 参考訳(メタデータ) (2020-10-19T15:00:35Z) - Hybrid Stochastic-Deterministic Minibatch Proximal Gradient:
Less-Than-Single-Pass Optimization with Nearly Optimal Generalization [83.80460802169999]
HSDMPGは、学習モデル上で過大なエラーの順序である$mathcalObig(1/sttnbig)$を達成可能であることを示す。
損失係数について、HSDMPGは学習モデル上で過大なエラーの順序である$mathcalObig(1/sttnbig)$を達成できることを示す。
論文 参考訳(メタデータ) (2020-09-18T02:18:44Z) - Optimal Robust Linear Regression in Nearly Linear Time [97.11565882347772]
学習者が生成モデル$Y = langle X,w* rangle + epsilon$から$n$のサンプルにアクセスできるような高次元頑健な線形回帰問題について検討する。
i) $X$ is L4-L2 hypercontractive, $mathbbE [XXtop]$ has bounded condition number and $epsilon$ has bounded variance, (ii) $X$ is sub-Gaussian with identity second moment and $epsilon$ is
論文 参考訳(メタデータ) (2020-07-16T06:44:44Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。