論文の概要: Gradient descent reaches arbitrary accuracy in a fixed number of large steps on multiclass logistic regression

• arxiv url: http://arxiv.org/abs/2610.26748v1
• Date: Mon, 19 Oct 2026 17:14:12 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-23 01:37:31.861267
• Title: Gradient descent reaches arbitrary accuracy in a fixed number of large steps on multiclass logistic regression
• Title（参考訳）: 多クラスロジスティック回帰における大きなステップの固定数において、勾配降下が任意の精度に達する
• Abstract要約: ステップサイズ$$の勾配降下は、多クラスロジスティック回帰損失に対して$varepsilon$Optimity gapを達成できることを示す。 そのために、ステップサイズ$$は、$varepsilon$の関数として十分に大きく選ばなければならない。
• 参考スコア（独自算出の注目度）: 1.376408511310322
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We show that gradient descent (GD) with step size $η$ can achieve $\varepsilon$ optimality gap on the multiclass logistic regression loss in a number of iterations $T$ that is independent of $\varepsilon$. To do so, the step size $η$ must be chosen large enough as a function of $\varepsilon$ (and properties of the linearly separable dataset), while $T$ is a constant that only depends on the data. The relevant properties of the data include the number of points and their margin (for $T$), and one additional quantity (for $η$) that turns out to be necessary in dimension $d \geq 3$. The proofs build on the known fact that, as $η\to \infty$, suitably rescaled GD becomes the perceptron algorithm, and the latter finds a perfect classifier in $T$ iterations. A similar claim was shown for two classes in dimension $d = 2$ using other proof techniques. This result adds to previous works that showed GD on the logistic regression loss can be accelerated by taking large step sizes. Those provoke a wild, oscillatory initial phase, followed by a stable phase. We provide results of this (qualitatively different) nature, too.
• Abstract（参考訳）: ステップサイズ$η$の勾配降下(GD)は、$\varepsilon$の独立な反復数$T$の多重クラスロジスティック回帰損失に対して、$\varepsilon$の最適性ギャップを達成できることを示す。 そのために、ステップサイズ$η$は$\varepsilon$(および線形分離可能なデータセットの特性)の関数として十分に大きく選ばなければならない。 データの関連する性質には、点の数とそのマージン($T$の場合)と、次元$d \geq 3$の場合に必要な追加量($η$の場合)が含まれる。 証明は、$η\to \infty$として、適切に再スケールされたGDがパーセプトロンアルゴリズムとなり、後者は$T$反復で完全分類器を見つけるという既知の事実に基づいている。 同様の主張が、他の証明手法を用いて次元 $d = 2$ の 2 つのクラスに対して示された。 この結果は、ロジスティック回帰損失のGDが大きなステップサイズを取ることで加速できることを以前の研究に付け加えた。 それらは急激で振動する初期フェーズを刺激し、続いて安定なフェーズを発生させる。 私たちは、この(適度に異なる)性質の結果も提供します。

関連論文リスト

• Tight Transition Time Bounds for Separable Logistic Regression at the Edge of Stability [15.99295708760811]
  勾配勾配勾配下での線形分離可能なデータに対するロジスティック回帰を, 大きめのステップサイズ$$で検討した。 既存の作業は、次元$d=2$ as $to infty$として厳密な$(1)$バウンドを提供し、任意の次元において$$$の独立な有界な予想を$dgeq 2$とする。 本稿では,固定されたサンプルサイズ$ngeq 2$および十分に小さなマージン$$に対して,最悪のケース遷移時間は$!left(log)minであることを示すことによって,この予想を否定する。
  論文  参考訳（メタデータ） (2026-10-01T10:54:10Z)
• Tight Bounds for Logistic Regression with Large Stepsize Gradient Descent in Low Dimension [36.3266119975955]
  分離可能なデータを用いた二項分類のための線形モデルを訓練するために、降下によるロジスティック勾配を最小化する最適化問題を考察する。 十分な学習率を持つGDが$mathcalO (1/(T))$よりも小さく、$T geq (n/+ 1/2)$の場合、$n$はデータセットサイズであることを示す。
  論文  参考訳（メタデータ） (2026-02-12T22:58:18Z)
• Minimax Optimal Convergence of Gradient Descent in Logistic Regression via Large and Adaptive Stepsizes [32.64968378005787]
  線形分離可能なデータに対して,現在のリスクに適応する段差を持つロジスティック回帰のために,$textitgradient descent$(GD)について検討した。 我々は、GDが$exp(-Theta(eta))$で上限付けられたリスクを達成していることを示し、$gamma$はデータセットのマージンである。 特に、古典的な$textitPerceptron$ (Novikoff, 1962)は、一階オンライン法であり、定数でもGDと一致する1/gamma2$のステップ複雑性も達成している。
  論文  参考訳（メタデータ） (2025-04-05T08:34:20Z)
• 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)
• Scaling Up Differentially Private LASSO Regularized Logistic Regression via Faster Frank-Wolfe Iterations [51.14495595270775]
  我々は,Frank-Wolfeアルゴリズムを$L_1$のペナル化線形回帰に適応させ,スパース入力を認識し,有効利用する。 この方法では,プライバシパラメータ$epsilon$の値とデータセットの分散度に応じて,最大2,200times$の係数でランタイムを削減できることを示す。
  論文  参考訳（メタデータ） (2023-10-30T19:52:43Z)
• Almost Linear Constant-Factor Sketching for $\ell_1$ and Logistic Regression [74.28017932704704]
  我々は,従来の難解なスケッチとターンタイルストリーミングの結果を$ell_1$とロジスティック回帰で改善する。 また、入力空間の間隔で1+varepsilon$近似を出力するトレードオフも行います。 我々のスケッチは、データ依存正規化器が個々のロジスティック損失の分散に対応するような、正規化されたロジスティック回帰を近似するために拡張することができる。
  論文  参考訳（メタデータ） (2023-03-31T18:12:33Z)
• High-dimensional Asymptotics of Feature Learning: How One Gradient Step Improves the Representation [89.21686761957383]
  2層ネットワークにおける第1層パラメータ $boldsymbolW$ の勾配降下ステップについて検討した。 我々の結果は、一つのステップでもランダムな特徴に対してかなりの優位性が得られることを示した。
  論文  参考訳（メタデータ） (2022-05-03T12:09:59Z)
• 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)

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

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