自适应步长梯度下降在四阶增长函数上几乎线性收敛
Gradient descent with adaptive stepsize converges (nearly) linearly under fourth-order growth
- 基于函数在极小值附近四阶增长特性，设计自适应步长策略
- 理论证明该方法在矩阵感知、因子分解等任务中实现近线性收敛
- 适用于高维过参数场景，尤其适合非二次型优化问题
优化领域普遍认为，梯度下降线性收敛需函数在极小值点附近呈二次增长。本文指出此观点不准确：对于任意在极小值点附近满足四阶增长的光滑函数，采用自适应步长的梯度下降仍可实现局部（近似）线性收敛。该方法基于一个关键分解定理——此类函数在最优解附近存在一光滑流形（称作‘峡谷’），沿峡谷方向函数增长为常数阶，而垂直于峡谷方向至少为二次增长。利用这一结构，算法将多个短梯度步与一次长距离Polyak步交替进行，从而快速逼近最小值。我们在矩阵感知、矩阵因子化及过参数化单神经元学习问题中验证了该理论与算法的有效性。
原文摘要 · Abstract (English)
A prevalent belief among optimization specialists is that linear convergence of gradient descent is contingent on the function growing quadratically away from its minimizers. In this work, we argue that this belief is inaccurate. We show that gradient descent with an adaptive stepsize converges at a local (nearly) linear rate on any smooth function that merely exhibits fourth-order growth away from its minimizer. The adaptive stepsize we propose arises from an intriguing decomposition theorem: any such function admits a smooth manifold around the optimal solution -- which we call the ravine -- so that the function grows at least quadratically away from the ravine and has constant order growth along it. The ravine allows one to interlace many short gradient steps with a single long Polyak gradient step, which together ensure rapid convergence to the minimizer. We illustrate the theory and algorithm on the problems of matrix sensing and factorization and learning a single neuron in the overparameterized regime.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。