論文の概要: Full-Batch Gradient Descent Outperforms One-Pass SGD: Sample Complexity Separation in Single-Index Learning

• arxiv url: http://arxiv.org/abs/2602.02431v1
• Date: Mon, 02 Feb 2026 18:31:51 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-02-03 19:28:34.358765
• Title: Full-Batch Gradient Descent Outperforms One-Pass SGD: Sample Complexity Separation in Single-Index Learning
• Title（参考訳）: フルバッチ・グラディエント・ディフレッシュが1パスのSGDより優れる: 単一インデックス学習におけるサンプル複雑度分離
• Authors: Filip Kovačević, Hong Chang Ji, Denny Wu, Mahdi Soltanolkotabi, Marco Mondelli,
• Abstract要約: フルバッチ降下勾配(GD)は常にすべてのデータを再利用する。 1パス勾配降下(オンラインSGD)は、各データポイントを1回だけ使用する。 フルバッチGDは,n simeq d$サンプルで好適な最適化環境を示す。
• 参考スコア（独自算出の注目度）: 46.31579702997505
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: It is folklore that reusing training data more than once can improve the statistical efficiency of gradient-based learning. However, beyond linear regression, the theoretical advantage of full-batch gradient descent (GD, which always reuses all the data) over one-pass stochastic gradient descent (online SGD, which uses each data point only once) remains unclear. In this work, we consider learning a $d$-dimensional single-index model with a quadratic activation, for which it is known that one-pass SGD requires $n\gtrsim d\log d$ samples to achieve weak recovery. We first show that this $\log d$ factor in the sample complexity persists for full-batch spherical GD on the correlation loss; however, by simply truncating the activation, full-batch GD exhibits a favorable optimization landscape at $n \simeq d$ samples, thereby outperforming one-pass SGD (with the same activation) in statistical efficiency. We complement this result with a trajectory analysis of full-batch GD on the squared loss from small initialization, showing that $n \gtrsim d$ samples and $T \gtrsim\log d$ gradient steps suffice to achieve strong (exact) recovery.
• Abstract（参考訳）: トレーニングデータを1回以上再利用することで、勾配学習の統計的効率が向上することが民間伝承である。 しかし、線形回帰を超えた1パス確率勾配勾配(各データポイントのみを使用するオンラインSGD)に対する全バッチ勾配勾配(GD)の理論的優位性は明らかでない。 本研究では,2次アクティベーションを持つ$d$次元単次元インデクスモデルについて検討し,その場合,弱い回復を達成するためには,1パスのSGDが$n\gtrsim d\log d$サンプルを必要とすることが知られている。 相関損失に関して、このサンプル複雑性の$\log d$ factorは、フルバッチ球状GDに対して持続することを示したが、単にアクティベーションを停止させることで、フルバッチGDは、$n \simeq d$ sampleにおいて好適な最適化環境を示し、その結果、統計効率においてワンパスSGD(同じアクティベーション)よりも優れている。 この結果は、小さな初期化による正方形損失に対するフルバッチGDの軌跡解析と補完し、$n \gtrsim d$サンプルと$T \gtrsim\log d$グラデーションステップが強い(実際に)回復を達成するのに十分であることを示す。

関連論文リスト

• Rapid Overfitting of Multi-Pass Stochastic Gradient Descent in Stochastic Convex Optimization [34.451177321785146]
  基本凸最適化(SCO)モデルにおけるマルチパス勾配勾配勾配(SGD)のアウトオブサンプル性能について検討した。 SCOの非平滑なケースでは、SGDのごく一部のエポックが既にそのアウト・オブ・サンプルを著しく損なっており、オーバーフィッティングにつながることが示されている。
  論文  参考訳（メタデータ） (2025-05-13T07:32:48Z)
• Improving the Convergence Rates of Forward Gradient Descent with Repeated Sampling [5.448070998907116]
  前向き勾配降下(FGD)は、生物学的により妥当な勾配降下の代替として提案されている。 本稿では、各トレーニングサンプルに基づいて、$ell$FGDステップを計算することにより、この亜最適係数が$d/(ell wedge d)$となることを示す。 また、繰り返しサンプリングしたFGDは入力分布の低次元構造に適応できることを示す。
  論文  参考訳（メタデータ） (2024-11-26T16:28:16Z)
• SIMPLE: A Gradient Estimator for $k$-Subset Sampling [42.38652558807518]
  この作業では、フォワードパスの離散$k$-subsetサンプリングに戻ります。 勾配推定器 SIMPLE は, 最先端推定器と比較して, バイアスやばらつきが低いことを示す。 実験結果から,線形回帰を説明・スパースする学習性能が向上した。
  論文  参考訳（メタデータ） (2022-10-04T22:33:16Z)
• Adaptive Sketches for Robust Regression with Importance Sampling [64.75899469557272]
  我々は、勾配降下(SGD)による頑健な回帰を解くためのデータ構造を導入する。 我々のアルゴリズムは、サブ線形空間を使用し、データに1回パスするだけで、SGDの$T$ステップを重要サンプリングで効果的に実行します。
  論文  参考訳（メタデータ） (2022-07-16T03:09:30Z)
• Breaking the Sample Complexity Barrier to Regret-Optimal Model-Free Reinforcement Learning [52.76230802067506]
  漸進的強化学習における後悔を最小限に抑えるために,新しいモデルフリーアルゴリズムを提案する。 提案アルゴリズムは、2つのQ-ラーニングシーケンスの助けを借りて、初期設定された参照更新ルールを用いる。 初期の分散還元法の設計原理は、他のRL設定とは独立した関心を持つかもしれない。
  論文  参考訳（メタデータ） (2021-10-09T21:13:48Z)
• Attentional-Biased Stochastic Gradient Descent [74.49926199036481]
  深層学習におけるデータ不均衡やラベルノイズ問題に対処するための証明可能な手法(ABSGD)を提案する。 本手法は運動量SGDの簡易な修正であり,各試料に個別の重み付けを行う。 ABSGDは追加コストなしで他の堅牢な損失と組み合わせられるほど柔軟である。
  論文  参考訳（メタデータ） (2020-12-13T03:41:52Z)
• Direction Matters: On the Implicit Bias of Stochastic Gradient Descent with Moderate Learning Rate [105.62979485062756]
  本稿では,中等度学習におけるSGDの特定の正規化効果を特徴付けることを試みる。 SGDはデータ行列の大きな固有値方向に沿って収束し、GDは小さな固有値方向に沿って収束することを示す。
  論文  参考訳（メタデータ） (2020-11-04T21:07:52Z)
• Least Squares Regression with Markovian Data: Fundamental Limits and Algorithms [69.45237691598774]
  マルコフ連鎖からデータポイントが依存しサンプリングされる最小二乗線形回帰問題について検討する。 この問題を$tau_mathsfmix$という観点から、鋭い情報理論のミニマックス下限を確立する。 本稿では,経験的リプレイに基づくアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-06-16T04:26:50Z)

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

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