大步长让正则逻辑回归梯度下降更快收敛，突破传统理论限制。
Large Stepsizes Accelerate Gradient Descent for Regularized Logistic Regression
- 用大固定步长替代小步长，打破目标函数单调下降的限制。
- 在条件数κ下实现√κ阶收敛，比经典方法快一倍以上。
- 适用于数据线性可分场景，适合追求高效优化的研究者。
我们研究了在ℓ₂正则化逻辑回归中使用固定步长的梯度下降（GD）方法，针对线性可分数据的情况。经典理论认为需采用小步长以保证目标函数单调下降，并在˜O(κ)步内实现指数收敛，其中κ为条件数。令人惊讶的是，我们证明通过使用大步长——尽管目标函数非单调变化——可将收敛速度提升至˜O(√κ)。该加速效果同样适用于可分分布下的总体风险最小化，优于现有最佳上界。此外，我们刻画了局部收敛的最大步长，在特定情况下也决定了全局收敛性。本结果将Wu等（2024）从最小值位于无穷远的凸情形扩展至具有有限最小值的强凸情形。
原文摘要 · Abstract (English)
We study gradient descent (GD) with a constant stepsize for $\ell_2$-regularized logistic regression with linearly separable data. Classical theory suggests small stepsizes to ensure monotonic reduction of the optimization objective, achieving exponential convergence in $\widetilde{\mathcal{O}}(κ)$ steps with $κ$ being the condition number. Surprisingly, we show that this can be accelerated to $\widetilde{\mathcal{O}}(\sqrtκ)$ by simply using a large stepsize -- for which the objective evolves nonmonotonically. The acceleration brought by large stepsizes extends to minimizing the population risk for separable distributions, improving on the best-known upper bounds on the number of steps to reach a near-optimum. Finally, we characterize the largest stepsize for the local convergence of GD, which also determines the global convergence in special scenarios. Our results extend the analysis of Wu et al. (2024) from convex settings with minimizers at infinity to strongly convex cases with finite minimizers.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。