动态调整梯度缩放，让优化算法跑得更快更稳。
Gradient Methods with Online Scaling
- 用在线学习自动调节每步梯度大小
- 光滑凸函数下收敛速度达最优条件数级别
- 适合需要快速收敛的优化任务
我们提出一种加速基于梯度方法收敛的框架，通过在线学习算法在每一步迭代中学习梯度缩放。该框架在渐近意义上可证明加速梯度方法的收敛性。与以往基于最坏情况分析的文献不同，本框架提供了针对迭代轨迹最优缩放矩阵的强收敛保证。对于光滑强凸优化，结果达到 $O(κ^/star \log(1/\varepsilon))$ 的复杂度，其中 $κ^/star$ 是最优预处理矩阵可实现的条件数，优于先前的 $O(\sqrt{n}κ^/star \log(1/\varepsilon))$。特别地，该方法的一个变体在凸二次函数上实现超线性收敛。对于光滑凸优化，首次证明广泛使用的超梯度下降启发式能改善梯度下降的收敛性。
原文摘要 · Abstract (English)
We introduce a framework to accelerate the convergence of gradient-based methods with online learning. The framework learns to scale the gradient at each iteration through an online learning algorithm and provably accelerates gradient-based methods asymptotically. In contrast with previous literature, where convergence is established based on worst-case analysis, our framework provides a strong convergence guarantee with respect to the optimal scaling matrix for the iteration trajectory. For smooth strongly convex optimization, our results provide an $O(κ^\star \log(1/\varepsilon)$) complexity result, where $κ^\star$ is the condition number achievable by the optimal preconditioner, improving on the previous $O(\sqrt{n}κ^\star \log(1/\varepsilon))$ result. In particular, a variant of our method achieves superlinear convergence on convex quadratics. For smooth convex optimization, we show for the first time that the widely-used hypergradient descent heuristic improves on the convergence of gradient descent.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。