論文の概要: Large Stepsize Gradient Descent for Logistic Loss: Non-Monotonicity of
the Loss Improves Optimization Efficiency
- arxiv url: http://arxiv.org/abs/2402.15926v1
- Date: Sat, 24 Feb 2024 23:10:28 GMT
- ステータス: 処理完了
- システム内更新日: 2024-02-27 16:21:37.650591
- Title: Large Stepsize Gradient Descent for Logistic Loss: Non-Monotonicity of
the Loss Improves Optimization Efficiency
- Title（参考訳）: ロジスティックロスのための大規模グラディエントディフレクション:損失の非単調性は最適化効率を向上する
- Authors: Jingfeng Wu, Peter L. Bartlett, Matus Telgarsky, and Bin Yu
- Abstract要約: 線形分離可能なデータを用いたロジスティック回帰に一定の段差を持つ勾配降下(GD)を考える。
GD はこの初期振動位相を急速に終了し、$mathcalO(eta)$ steps となり、その後$tildemathcalO (1 / (eta t) )$ convergence rate が得られることを示す。
我々の結果は、予算が$T$ ステップであれば、GD は攻撃的なステップサイズで $tildemathcalO (1/T2)$ の加速損失を達成できることを示している。
- 参考スコア（独自算出の注目度）: 47.8739414267201
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We consider gradient descent (GD) with a constant stepsize applied to
logistic regression with linearly separable data, where the constant stepsize
$\eta$ is so large that the loss initially oscillates. We show that GD exits
this initial oscillatory phase rapidly -- in $\mathcal{O}(\eta)$ steps -- and
subsequently achieves an $\tilde{\mathcal{O}}(1 / (\eta t) )$ convergence rate
after $t$ additional steps. Our results imply that, given a budget of $T$
steps, GD can achieve an accelerated loss of $\tilde{\mathcal{O}}(1/T^2)$ with
an aggressive stepsize $\eta:= \Theta( T)$, without any use of momentum or
variable stepsize schedulers. Our proof technique is versatile and also handles
general classification loss functions (where exponential tails are needed for
the $\tilde{\mathcal{O}}(1/T^2)$ acceleration), nonlinear predictors in the
neural tangent kernel regime, and online stochastic gradient descent (SGD) with
a large stepsize, under suitable separability conditions.
- Abstract（参考訳）: 線形分離可能なデータを持つロジスティック回帰に適用する定ステップ付き勾配降下 (gd) について検討し, 定ステップ化 $\eta$ が大きすぎて, 損失は初期振動する。
すると、gd はこの初期振動位相を急速に終了し、その後$t$ の追加ステップの後に$\tilde{\mathcal{o}}(1 / (\eta t) )$ の収束率が得られる。
我々の結果は、t$ステップの予算が与えられると、gdは、運動量や可変ステップを使わずに、攻撃的なステップで$\eta:= \theta(t)$ で$\tilde{\mathcal{o}}(1/t^2)$の損失を加速できることを示している。
この証明手法は汎用性があり,一般分類損失関数($\tilde{\mathcal{o}}(1/t^2)$accelerate に対して指数的テールを必要とする)や,神経接核系における非線形予測関数,大規模ステップ化を伴うオンライン確率勾配降下 (sgd) を適切な分離条件下で処理する。
関連論文リスト
- Implicit Bias of Gradient Descent for Logistic Regression at the Edge of
Stability [69.01076284478151]
機械学習の最適化において、勾配降下(GD)はしばしば安定性の端(EoS)で動く
本稿では,EoS系における線形分離可能なデータに対するロジスティック回帰のための定数段差GDの収束と暗黙バイアスについて検討する。
論文 参考訳（メタデータ） (2023-05-19T16:24:47Z) - High-dimensional Asymptotics of Feature Learning: How One Gradient Step
Improves the Representation [89.21686761957383]
2層ネットワークにおける第1層パラメータ $boldsymbolW$ の勾配降下ステップについて検討した。
我々の結果は、一つのステップでもランダムな特徴に対してかなりの優位性が得られることを示した。
論文 参考訳（メタデータ） (2022-05-03T12:09:59Z) - Towards Noise-adaptive, Problem-adaptive Stochastic Gradient Descent [7.176107039687231]
雑音に対して勾配降下(SGD)を適応させるステップサイズスキームを設計する。
我々は、Nesterov反復によるSGDの$T$反復がほぼ最適であることを示す。
他のステップサイズスキームと比較して、新しい指数的なステップサイズスキームの有効性を実証する。
論文 参考訳（メタデータ） (2021-10-21T19:22:14Z) - On the Convergence of Step Decay Step-Size for Stochastic Optimization [27.02857082612736]
神経系の収束は、特にネットワーク問題などの非数学問題において、ステップサイズ率に大きく依存する。
非スムース状態における崩壊の収束を提供し、勾配ノルムが消えることを保証する。
強い凸の場合、$(T/ST)$レートを確立し、$(T/ST)$レートであることも証明します。
論文 参考訳（メタデータ） (2021-02-18T14:37:25Z) - 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) - Sample Complexity Bounds for Two Timescale Value-based Reinforcement
Learning Algorithms [65.09383385484007]
2つの時間スケール近似(SA)は、値に基づく強化学習アルゴリズムで広く使われている。
本稿では,2つの時間スケール線形および非線形TDCとGreedy-GQアルゴリズムの漸近収束率について検討する。
論文 参考訳（メタデータ） (2020-11-10T11:36:30Z) - Direction Matters: On the Implicit Bias of Stochastic Gradient Descent
with Moderate Learning Rate [105.62979485062756]
本稿では,中等度学習におけるSGDの特定の正規化効果を特徴付けることを試みる。
SGDはデータ行列の大きな固有値方向に沿って収束し、GDは小さな固有値方向に沿って収束することを示す。
論文 参考訳（メタデータ） (2020-11-04T21:07:52Z) - Gradient Methods Never Overfit On Separable Data [31.714928102950584]
標準勾配法は分離可能なデータに過度に適合しないことを示す。
データセットに対するマージン違反数の非漸近的境界を示す。
論文 参考訳（メタデータ） (2020-06-30T18:01:46Z) - On the Almost Sure Convergence of Stochastic Gradient Descent in
Non-Convex Problems [75.58134963501094]
本稿では,勾配降下(SGD)の軌跡を解析する。
我々はSGDが厳格なステップサイズポリシーのために1ドルでサドルポイント/マニフォールドを避けることを示す。
論文 参考訳（メタデータ） (2020-06-19T14:11:26Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。