arXiv:2602.18946cs.LGmath.OC2026-02

通过递增步长实现对分离逻辑回归的指数收敛,无需不稳定区域。

Exponential Convergence of (Stochastic) Gradient Descent for Separable Logistic Regression

  • 采用简单非自适应递增步长策略,保持优化稳定。
  • 在边界条件下实现梯度下降与随机梯度下降的指数收敛。
  • 方法无需预知精度或迭代次数,适合实时应用。

梯度下降和随机梯度下降是现代机器学习的核心,但其在大步长下的理论行为仍不明确。近期研究指出,加速常出现在稳定边缘,此时优化轨迹变得不稳定且难以分析。现有针对可分逻辑回归的方法通过显式利用这种不稳定的区域,采用固定或自适应的大步长实现更快收敛。本文证明,不稳定并非加速的必要条件。我们证明,采用简单的非自适应递增步长调度的梯度下降,在满足边界条件时,可实现可分逻辑回归的指数收敛,且始终处于稳定优化区域内。该方法为任意时间(anytime)算法,无需预先知道优化时长或目标精度。同时,我们还建立了使用轻量级自适应步长规则的随机梯度下降的指数收敛性,避免了线搜索和专门流程,优于现有多项式收敛率。我们的结果表明,仅通过精心设计的步长增长即可实现梯度下降与随机梯度下降的指数加速。

原文摘要 · Abstract (English)

Gradient descent and stochastic gradient descent are central to modern machine learning, yet their behavior under large step sizes remains theoretically unclear. Recent work suggests that acceleration often arises near the edge of stability, where optimization trajectories become unstable and difficult to analyze. Existing results for separable logistic regression achieve faster convergence by explicitly leveraging such unstable regimes through constant or adaptive large step sizes. In this paper, we show that instability is not inherent to acceleration. We prove that gradient descent with a simple, non-adaptive increasing step-size schedule achieves exponential convergence for separable logistic regression under a margin condition, while remaining entirely within a stable optimization regime. The resulting method is anytime and does not require prior knowledge of the optimization horizon or target accuracy. We also establish exponential convergence of stochastic gradient descent using a lightweight adaptive step-size rule that avoids line search and specialized procedures, improving upon existing polynomial-rate guarantees. Together, our results demonstrate that carefully structured step-size growth alone suffices to obtain exponential acceleration for both gradient descent and stochastic gradient descent.

梯度下降指数收敛逻辑回归步长策略

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。