自适应步长让梯度下降更快，尤其在逻辑回归等任务中可线性收敛。
Armijo Line-search Can Make (Stochastic) Gradient Descent Provably Faster
- 用Armijo线搜索自动调节步长，无需预知光滑常数
- 在逻辑回归等凸问题上实现线性收敛，优于传统方法
- 适合机器学习中的优化问题，特别是需快速收敛的场景
Armijo线搜索（Armijo-LS）是设置梯度下降（GD）步长的标准方法。对于光滑函数，它无需知道全局光滑常数L，能自适应局部光滑性，从而加快收敛速度。已有理论表明，使用Armijo-LS的梯度下降（GD-LS）相比固定1/L步长的梯度下降（GD(1/L)）可获得常数倍加速。本文进一步证明：若目标函数满足特定非均匀光滑性条件，GD-LS的收敛速率将优于GD(1/L)。具体而言，在对应逻辑回归和多分类的凸目标下，GD-LS可实现线性收敛，而GD(1/L)仅为亚线性。此外，对满足梯度支配条件的非凸目标（如强化学习中的softmax策略梯度或带逻辑链接函数的广义线性模型），GD-LS可达到专用于此类问题算法的快速收敛性能。最后，在插值假设下，我们分析了随机梯度下降结合随机线搜索在凸损失下的收敛性。
原文摘要 · Abstract (English)
Armijo line-search (Armijo-LS) is a standard method to set the step-size for gradient descent (GD). For smooth functions, Armijo-LS alleviates the need to know the global smoothness constant L and adapts to the ``local'' smoothness, enabling GD to converge faster. Existing theoretical analyses show that GD with Armijo-LS (GD-LS) can result in constant factor improvements over GD with a 1/L step-size (denoted as GD(1/L)). We strengthen these results and show that if the objective function satisfies a certain non-uniform smoothness condition, GD-LS can result in a faster convergence rate than GD(1/L). In particular, we prove that for convex objectives corresponding to logistic regression and multi-class classification, GD-LS can converge to the optimum at a linear rate, and hence improves over the sublinear convergence of GD(1/L). Furthermore, for non-convex objectives satisfying gradient domination (e.g., those corresponding to the softmax policy gradient in RL or generalized linear models with a logistic link function), GD-LS can match the fast convergence of algorithms tailored for these specific settings. Finally, we analyze the convergence of stochastic GD with a stochastic line-search on convex losses under the interpolation assumption.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。