論文の概要: Lower Generalization Bounds for GD and SGD in Smooth Stochastic Convex
Optimization
- arxiv url: http://arxiv.org/abs/2303.10758v2
- Date: Wed, 10 May 2023 15:16:59 GMT
- ステータス: 処理完了
- システム内更新日: 2023-05-11 16:30:14.560111
- Title: Lower Generalization Bounds for GD and SGD in Smooth Stochastic Convex
Optimization
- Title（参考訳）: 滑らかな確率凸最適化におけるGDとSGDの低次一般化境界
- Authors: Peiyuan Zhang, Jiaye Teng, Jingzhao Zhang
- Abstract要約: トレーニングステップ$T$とStep-size$eta$は、滑らかな凸最適化(SCO)問題の認定に影響を与える可能性がある。
まず、グラディエントDescent(GD)とグラディエントDescent(SGD)の厳密な過剰リスク低境界を提供する。
近年の作業は、より良い速度で達成できるが、トレーニング時間が長い場合には改善が減少する。
- 参考スコア（独自算出の注目度）: 9.019243171993553
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: This work studies the generalization error of gradient methods. More
specifically, we focus on how training steps $T$ and step-size $\eta$ might
affect generalization in smooth stochastic convex optimization (SCO) problems.
We first provide tight excess risk lower bounds for Gradient Descent (GD) and
Stochastic Gradient Descent (SGD) under the general non-realizable smooth SCO
setting, suggesting that existing stability analyses are tight in step-size and
iteration dependence, and that overfitting provably happens. Next, we study the
case when the loss is realizable, i.e. an optimal solution minimizes all the
data points. Recent works show better rates can be attained but the improvement
is reduced when training time is long. Our paper examines this observation by
providing excess risk lower bounds for GD and SGD in two realizable settings:
1) $\eta T = \bigO{n}$, and (2) $\eta T = \bigOmega{n}$, where $n$ is the size
of dataset. In the first case $\eta T = \bigOmega{n}$, our lower bounds tightly
match and certify the respective upper bounds. However, for the case $\eta T =
\bigOmega{n}$, our analysis indicates a gap between the lower and upper bounds.
A conjecture is proposed that the gap can be closed by improving upper bounds,
supported by analyses in two special scenarios.
- Abstract（参考訳）: 本研究は勾配法の一般化誤差を考察する。
より具体的には、smoous stochastic convex optimization (sco)問題における一般化に、トレーニングステップ$t$とステップサイズ$\eta$がどのように影響するかに注目します。
まず、一般の非実現可能な滑らかなSCO設定の下で、グラディエント・ディクエント・ディクエント(GD)と確率グラディエント・ディクエント・ディクエント・ディクエント(SGD)に対して厳密な過大なリスク低いバウンダリを提供し、既存の安定性解析がステップサイズおよびイテレーション依存性において厳密であり、オーバーフィッティングが確実に起こることを示唆する。
次に、損失が実現可能な場合、すなわち最適解がすべてのデータポイントを最小化する場合について検討する。
近年の作業は、より良い速度で達成できるが、トレーニング時間が長い場合には改善が減少する。
本稿では,GD と SGD の過剰なリスク低境界を2つの実現可能な設定で提供することにより,この観測を検証した。
1) $\eta T = \bigO{n}$, and (2) $\eta T = \bigOmega{n}$ ここで$n$はデータセットのサイズである。
最初の場合、$\eta t = \bigomega{n}$ では、下限は密に一致し、各上限を証明します。
しかし、$\eta T = \bigOmega{n}$ の場合、解析は下界と上界の間のギャップを示している。
2つの特別なシナリオの分析によって支持される上界を改善することでギャップを閉じることができるという予想が提案されている。
関連論文リスト
- Convergence Rate Analysis of LION [54.28350823319057]
LION は、勾配カルシュ=クーン=T (sqrtdK-)$で測定された $cal(sqrtdK-)$ の反復を収束する。
従来のSGDと比較して,LIONは損失が小さく,性能も高いことを示す。
論文 参考訳（メタデータ） (2024-11-12T11:30:53Z) - Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic
Shortest Path [80.60592344361073]
線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。
エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。
既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
論文 参考訳（メタデータ） (2024-02-14T07:52:00Z) - Breaking the Heavy-Tailed Noise Barrier in Stochastic Optimization Problems [56.86067111855056]
構造密度の重み付き雑音によるクリップ最適化問題を考察する。
勾配が有限の順序モーメントを持つとき、$mathcalO(K-(alpha - 1)/alpha)$よりも高速な収束率が得られることを示す。
得られた推定値が無視可能なバイアスと制御可能な分散を持つことを示す。
論文 参考訳（メタデータ） (2023-11-07T17:39:17Z) - Empirical Risk Minimization with Shuffled SGD: A Primal-Dual Perspective
and Improved Bounds [12.699376765058137]
勾配降下法(SGD)は、おそらく現代の機械学習において最も一般的な最適化法である。
SGDを交換せずにサンプリングするSGDが分析されたのはごく最近のことだ。
データマトリックスに依存し、既存の境界によって予測されるものよりも決して悪くない、きめ細かい複雑性境界を証明します。
論文 参考訳（メタデータ） (2023-06-21T18:14:44Z) - Towards Noise-adaptive, Problem-adaptive Stochastic Gradient Descent [7.176107039687231]
雑音に対して勾配降下(SGD)を適応させるステップサイズスキームを設計する。
我々は、Nesterov反復によるSGDの$T$反復がほぼ最適であることを示す。
他のステップサイズスキームと比較して、新しい指数的なステップサイズスキームの有効性を実証する。
論文 参考訳（メタデータ） (2021-10-21T19:22:14Z) - The Convergence Rate of SGD's Final Iterate: Analysis on Dimension
Dependence [2.512827436728378]
Gradient Descent (SGD) は最適化において最も単純で一般的な手法の一つである。
定次元設定におけるSGDの最終点収束を特徴付ける方法を示す。
論文 参考訳（メタデータ） (2021-06-28T11:51:04Z) - High-probability Bounds for Non-Convex Stochastic Optimization with
Heavy Tails [55.561406656549686]
我々は、勾配推定が末尾を持つ可能性のある一階アルゴリズムを用いたヒルベルト非最適化を考える。
本研究では, 勾配, 運動量, 正規化勾配勾配の収束を高確率臨界点に収束させることと, 円滑な損失に対する最もよく知られた繰り返しを示す。
論文 参考訳（メタデータ） (2021-06-28T00:17:01Z) - Last iterate convergence of SGD for Least-Squares in the Interpolation
regime [19.05750582096579]
基本最小二乗構成におけるノイズレスモデルについて検討する。
最適予測器が完全に入力に適合すると仮定し、$langletheta_*, phi(X) rangle = Y$, ここで$phi(X)$は無限次元の非線型特徴写像を表す。
論文 参考訳（メタデータ） (2021-02-05T14:02:20Z) - On the Almost Sure Convergence of Stochastic Gradient Descent in
Non-Convex Problems [75.58134963501094]
本稿では,勾配降下(SGD)の軌跡を解析する。
我々はSGDが厳格なステップサイズポリシーのために1ドルでサドルポイント/マニフォールドを避けることを示す。
論文 参考訳（メタデータ） (2020-06-19T14:11:26Z) - Stability of Stochastic Gradient Descent on Nonsmooth Convex Losses [52.039438701530905]
任意のリプシッツ非平滑凸損失に対して,数種類の勾配勾配降下(SGD)に対して,鋭い上下境界を与える。
我々の限界は、極端に過剰な集団リスクを伴う、微分的にプライベートな非平滑凸最適化のための新しいアルゴリズムを導出することを可能にする。
論文 参考訳（メタデータ） (2020-06-12T02:45:21Z) - Better Theory for SGD in the Nonconvex World [2.6397379133308214]
大規模な非最適化問題は、現代の機械学習ではユビキタスである。
我々は, 広範囲の合成ミニバッチサイズがグラディエントDescent (SG) 問題に与える影響について実験を行った。
論文 参考訳（メタデータ） (2020-02-09T09:56:06Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。