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(\kappa^\star \log(1/\varepsilon)$) complexity result, where $\kappa^\star$ is the condition number achievable by the optimal preconditioner, improving on the previous $O(\sqrt{n}\kappa^\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.

本研究解决了梯度方法在在线学习中的收敛速度问题。提出了一种通过在线学习算法在每次迭代中学习缩放梯度的新框架，并为其收敛性提供了强保证。研究结果表明，该框架在平滑强凸优化中的复杂度为$O(\kappa^\star \log(1/\varepsilon))$，显著优于以往的结果，潜在影响可提高梯度方法的效率。

在线缩放的梯度方法