論文の概要: Tight Bounds for Logistic Regression with Large Stepsize Gradient Descent in Low Dimension

• arxiv url: http://arxiv.org/abs/2602.12471v1
• Date: Thu, 12 Feb 2026 22:58:18 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-02-16 23:37:53.784095
• Title: Tight Bounds for Logistic Regression with Large Stepsize Gradient Descent in Low Dimension
• Title（参考訳）: 低次元の段差勾配の大きいロジスティック回帰のためのタイトバウンド
• Authors: Michael Crawshaw, Mingrui Liu,
• Abstract要約: 分離可能なデータを用いた二項分類のための線形モデルを訓練するために、降下によるロジスティック勾配を最小化する最適化問題を考察する。 十分な学習率を持つGDが$mathcalO (1/(T))$よりも小さく、$T geq (n/+ 1/2)$の場合、$n$はデータセットサイズであることを示す。
• 参考スコア（独自算出の注目度）: 36.3266119975955
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider the optimization problem of minimizing the logistic loss with gradient descent to train a linear model for binary classification with separable data. With a budget of $T$ iterations, it was recently shown that an accelerated $1/T^2$ rate is possible by choosing a large step size $η= Θ(γ^2 T)$ (where $γ$ is the dataset's margin) despite the resulting non-monotonicity of the loss. In this paper, we provide a tighter analysis of gradient descent for this problem when the data is two-dimensional: we show that GD with a sufficiently large learning rate $η$ finds a point with loss smaller than $\mathcal{O}(1/(ηT))$, as long as $T \geq Ω(n/γ+ 1/γ^2)$, where $n$ is the dataset size. Our improved rate comes from a tighter bound on the time $τ$ that it takes for GD to transition from unstable (non-monotonic loss) to stable (monotonic loss), via a fine-grained analysis of the oscillatory dynamics of GD in the subspace orthogonal to the max-margin classifier. We also provide a lower bound of $τ$ matching our upper bound up to logarithmic factors, showing that our analysis is tight.
• Abstract（参考訳）: 線形モデルを用いた分別データの線形分類を学習するために,勾配降下によるロジスティック損失を最小限に抑えるという最適化問題を考察する。 予算が$T$の反復により、損失の非単調性にもかかわらず、大きなステップサイズが$η= (γ^2 T)$ (ここで$γ$はデータセットのマージン)を選択することで、1/T^2$の加速が可能であることが最近示されている。 本稿では,2次元データである場合の勾配勾配の厳密な解析を行い,十分な学習率を持つ GD が$\mathcal{O}(1/(ηT))$,$T \geq Ω(n/γ+ 1/γ^2)$,$n$ がデータセットサイズである場合に,損失が$\mathcal{O}(1/(ηT))$より小さい点を求めることを示した。 我々の改善率は、GDが不安定な(非単調な損失)から安定な(単調な損失)に移行するのに要する時間τ$の時間でより厳密な境界から来ている。 また、この上界を対数的因子に合わせるための$τ$の低いバウンダリも提供し、分析が厳密であることを示します。

関連論文リスト

• Convergence Rate Analysis of LION [54.28350823319057]
  LION は、勾配カルシュ=クーン=T (sqrtdK-)$で測定された $cal(sqrtdK-)$ の反復を収束する。 従来のSGDと比較して,LIONは損失が小さく,性能も高いことを示す。
  論文  参考訳（メタデータ） (2024-11-12T11:30:53Z)
• Large Stepsize Gradient Descent for Logistic Loss: Non-Monotonicity of the Loss Improves Optimization Efficiency [47.8739414267201]
  線形分離可能なデータを用いたロジスティック回帰に一定の段差を持つ勾配降下(GD)を考える。 GD はこの初期振動位相を急速に終了し、$mathcalO(eta)$ steps となり、その後$tildemathcalO (1 / (eta t) )$ convergence rate が得られることを示す。 我々の結果は、予算が$T$ ステップであれば、GD は攻撃的なステップサイズで $tildemathcalO (1/T2)$ の加速損失を達成できることを示している。
  論文  参考訳（メタデータ） (2024-02-24T23:10:28Z)
• Almost Linear Constant-Factor Sketching for $\ell_1$ and Logistic Regression [74.28017932704704]
  我々は,従来の難解なスケッチとターンタイルストリーミングの結果を$ell_1$とロジスティック回帰で改善する。 また、入力空間の間隔で1+varepsilon$近似を出力するトレードオフも行います。 我々のスケッチは、データ依存正規化器が個々のロジスティック損失の分散に対応するような、正規化されたロジスティック回帰を近似するために拡張することができる。
  論文  参考訳（メタデータ） (2023-03-31T18:12:33Z)
• Lower Generalization Bounds for GD and SGD in Smooth Stochastic Convex Optimization [9.019243171993553]
  トレーニングステップ$T$とStep-size$eta$は、滑らかな凸最適化(SCO)問題の認定に影響を与える可能性がある。 まず、グラディエントDescent(GD)とグラディエントDescent(SGD)の厳密な過剰リスク低境界を提供する。 近年の作業は、より良い速度で達成できるが、トレーニング時間が長い場合には改善が減少する。
  論文  参考訳（メタデータ） (2023-03-19T20:24:33Z)
• Gradient-Based Empirical Risk Minimization using Local Polynomial Regression [39.29885444997579]
  この論文の主な目標は、勾配降下(GD)や勾配降下(SGD)といった異なるアルゴリズムを比較することである。 損失関数がデータのスムーズな場合、各反復でオラクルを学習し、GDとSGDの両方のオラクル複雑度に打ち勝つことができることを示す。
  論文  参考訳（メタデータ） (2020-11-04T20:10:31Z)
• 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)
• Online Robust Regression via SGD on the l1 loss [19.087335681007477]
  ストリーミング方式でデータにアクセス可能なオンライン環境において、ロバストな線形回帰問題を考察する。 この研究で、$ell_O( 1 / (1 - eta)2 n )$損失の降下は、汚染された測定値に依存しない$tildeO( 1 / (1 - eta)2 n )$レートで真のパラメータベクトルに収束することを示した。
  論文  参考訳（メタデータ） (2020-07-01T11:38:21Z)

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

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