論文の概要: Large Stepsize Gradient Descent for Logistic Loss: Non-Monotonicity of the Loss Improves Optimization Efficiency

• arxiv url: http://arxiv.org/abs/2402.15926v2
• Date: Mon, 10 Jun 2024 03:32:05 GMT
• ステータス: 処理完了
• システム内更新日: 2024-06-12 01:13:35.299901
• Title: Large Stepsize Gradient Descent for Logistic Loss: Non-Monotonicity of the Loss Improves Optimization Efficiency
• Title（参考訳）: ロジスティック損失に対する大きなステップサイズのグラディエントDescent:損失の非単調性は最適化効率を向上する
• Authors: Jingfeng Wu, Peter L. Bartlett, Matus Telgarsky, 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 はこの初期振動位相を急速に終了し、$\mathcal{O}(\eta)$ step となり、その後$\tilde{\mathcal{O}}(1 / (\eta t) )$ convergence rate を得る。 我々の結果は、T$の予算が与えられた場合、GDはアクティベートされた$\eta:= \Theta(T)$で$\tilde{\mathcal{O}}(1/T^2)$の損失を、運動量や可変ステップ化スケジューラを使わずに達成できることを示している。 我々の証明手法は汎用的であり、一般的な分類損失関数(指数的テールが$\tilde{\mathcal{O}}(1/T^2)$Acceleration)、ニューラルタンジェントカーネルの非線形予測器、オンライン確率勾配降下(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)

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

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