論文の概要: Tight Transition Time Bounds for Separable Logistic Regression at the Edge of Stability

• arxiv url: http://arxiv.org/abs/2610.01459v1
• Date: Thu, 01 Oct 2026 10:54:10 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-03 01:19:24.067677
• Title: Tight Transition Time Bounds for Separable Logistic Regression at the Edge of Stability
• Title（参考訳）: 安定端における分離可能なロジスティック回帰のためのタイト遷移時間境界
• Abstract要約: 勾配勾配勾配下での線形分離可能なデータに対するロジスティック回帰を, 大きめのステップサイズ$$で検討した。 既存の作業は、次元$d=2$ as $to infty$として厳密な$(1)$バウンドを提供し、任意の次元において$$$の独立な有界な予想を$dgeq 2$とする。 本稿では,固定されたサンプルサイズ$ngeq 2$および十分に小さなマージン$$に対して,最悪のケース遷移時間は$!left(log)minであることを示すことによって,この予想を否定する。
• 参考スコア（独自算出の注目度）: 15.99295708760811
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study logistic regression on linearly separable data under gradient descent with a large constant stepsize $η$. Such dynamics may exhibit a characteristic Edge of Stability phenomenon, in which the loss initially oscillates before transitioning to a stable phase of monotone decrease. Existing work provides a tight $Θ(1)$ bound in dimension $d=2$ as $η\to \infty$ and conjectures a bound independent of $η$ in arbitrary dimensions $d\geq 2$. In this paper, we disprove this conjecture by showing that, for every fixed sample size $n\geq 2$ and sufficiently small margin $γ$, the worst-case transition time is $$Θ\!\left((\logη)^{\min\{n-2,d-2\}}\right)$$ uniformly over $d\geq2$. The key challenge in establishing a tight bound is that the sample contributing most strongly to the gradient can change repeatedly across iterations. To address this issue, we control such changes by induction on dimension and sample size, and construct matching hard instances.
• Abstract（参考訳）: 勾配勾配勾配下での線形分離可能なデータに対するロジスティック回帰を, 大きな定常ステップサイズ$η$で検討した。 このような力学は、損失がモノトン減少の安定な相に移行する前に最初に振動する、特徴的な安定性現象のエッジを示す可能性がある。 既存の作業は、次元 $d=2$ as $η\to \infty$ の厳密な$(1)$バウンドを提供し、任意の次元の$d\geq 2$ において$η$ の独立な有界な予想を与える。 本稿では、この予想を、固定されたサンプルサイズ$n\geq 2$と十分に小さなマージン$γ$に対して、最悪の場合の遷移時間は$\! \left((\logη)^{\min\{n-2,d-2\}}\right)$$$$$d\geq2$.\left((\logη)^{\min\{n-2,d-2\}}\right)$ タイトなバウンダリを確立する上で重要な課題は、最も勾配に強く寄与するサンプルが反復的に繰り返し変化することだ。 この問題に対処するために、次元とサンプルサイズによる誘導によるこのような変化を制御し、整合性のあるハードインスタンスを構築する。

関連論文リスト

• Ordinary Nonconvex SGD under Distance-Dependent Moments: Finite-Horizon Stationarity and Nagaev Bounds [1.6582968942719265]
  一様雑音-モーメンタリティ境界は、距離によって変動が増加する勾配を除外する。 直接降下すると、スムーズな転位引数が3エプシロン6$を回復する。 局所化半径は、非レート仮定、クリッピング正規化、運動量、バッチサイズの増加といった境界から導かれる。
  論文  参考訳（メタデータ） (2026-09-24T19:37:07Z)
• Constrained Online Learning with Noisy Constraint Values [55.29259818039367]
  一般的な実現可能性の下では、我々のLEDGERアルゴリズムは、期待される損失$O(sqrt T)と期待される予算違反$O(sqrtTlog(eT))を達成します。 スレーター条件、フィードバックチャネル間の独立性、絶対的制約値境界は不要である。
  論文  参考訳（メタデータ） (2026-09-07T01:38:41Z)
• When Does $\ell_2$-Boosting Overfit Benignly? High-Dimensional Risk Asymptotics and the $\ell_1$ Implicit Bias [15.113649527486276]
  良性オーバーフィッティングが線形レートで失敗することを示します。 この局所化機構は信号の存在下で持続するべきであるが、正確な信号-雑音分解は未解決の問題である。
  論文  参考訳（メタデータ） (2026-05-07T14:14:09Z)
• 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)
• 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)
• Measurement-induced phase transition for free fermions above one dimension [46.176861415532095]
  自由フェルミオンモデルに対する$d>1$次元における測定誘起エンタングルメント相転移の理論を開発した。 臨界点は、粒子数と絡み合いエントロピーの第2累積のスケーリング$$elld-1 ln ell$でギャップのない位相を分離する。
  論文  参考訳（メタデータ） (2023-09-21T18:11:04Z)
• Almost Linear Constant-Factor Sketching for $\ell_1$ and Logistic Regression [74.28017932704704]
  我々は,従来の難解なスケッチとターンタイルストリーミングの結果を$ell_1$とロジスティック回帰で改善する。 また、入力空間の間隔で1+varepsilon$近似を出力するトレードオフも行います。 我々のスケッチは、データ依存正規化器が個々のロジスティック損失の分散に対応するような、正規化されたロジスティック回帰を近似するために拡張することができる。
  論文  参考訳（メタデータ） (2023-03-31T18:12:33Z)

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

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