論文の概要: 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乗根でなければならないことを示す以前の下界よりも改善される。

関連論文リスト

• Dimension-free Private Mean Estimation for Anisotropic Distributions [55.86374912608193]
  以前の$mathRd上の分布に関する民間推定者は、次元性の呪いに苦しむ。 本稿では,サンプルの複雑さが次元依存性を改善したアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-11-01T17:59:53Z)
• Precise Asymptotics of Bagging Regularized M-estimators [5.165142221427928]
  我々は,アンサンブル推定器の正方形予測リスクを,正規化M値推定器のサブタグ化(サブサンプルブートストラップ集約)により特徴付ける。 我々の分析の鍵は、重なり合うサブサンプル上の推定値と残差との相関関係の結合挙動に関する新しい結果である。 サブサンプルサイズ,アンサンブルサイズ,正規化の併用最適化は,全データに対してのみ,正規化器の最適化を著しく上回る。
  論文  参考訳（メタデータ） (2024-09-23T17:48:28Z)
• Stochastic First-Order Methods with Non-smooth and Non-Euclidean Proximal Terms for Nonconvex High-Dimensional Stochastic Optimization [2.0657831823662574]
  非問題が非問題である場合、一階法のサンプルは問題次元に線形に依存することがあるが、望ましくない問題に対するものである。 我々のアルゴリズムは距離を使って複雑さを見積もることができる。 MathO (log d) / EuM4。 DISFOM は $mathO (log d) / EuM4 を用いて分散を鋭くすることができることを示す。
  論文  参考訳（メタデータ） (2024-06-27T18:38:42Z)
• Measuring quantum relative entropy with finite-size effect [53.64687146666141]
  相対エントロピー$D(rho|sigma)$を$sigma$が知られているときに推定する。 我々の推定器は次元$d$が固定されたときにCram'er-Rao型境界に達する。
  論文  参考訳（メタデータ） (2024-06-25T06:07:20Z)
• Projection by Convolution: Optimal Sample Complexity for Reinforcement Learning in Continuous-Space MDPs [56.237917407785545]
  本稿では,円滑なベルマン作用素を持つ連続空間マルコフ決定過程(MDP)の一般クラスにおいて,$varepsilon$-optimal Policyを学習する問題を考察する。 我々のソリューションの鍵となるのは、調和解析のアイデアに基づく新しい射影技術である。 我々の結果は、連続空間 MDP における2つの人気と矛盾する視点のギャップを埋めるものである。
  論文  参考訳（メタデータ） (2024-05-10T09:58:47Z)
• 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)
• Best Policy Identification in Linear MDPs [70.57916977441262]
  縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。 複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
  論文  参考訳（メタデータ） (2022-08-11T04:12:50Z)
• 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)

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

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