Gradient Methods with Online Scaling Part I. Theoretical Foundations
This provides a theoretical framework for improving optimization in machine learning, explaining empirical successes like hypergradient-descent, but it is incremental as it builds on existing first-order methods.
The paper tackles the problem of accelerating first-order optimization methods by introducing online scaled gradient methods (OSGM), which adapt stepsizes using online learning to achieve convergence rates asymptotically no worse than optimal, including non-asymptotic superlinear convergence in some cases.
This paper establishes the theoretical foundations of the online scaled gradient methods (OSGM), a framework that utilizes online learning to adapt stepsizes and provably accelerate first-order methods. OSGM quantifies the effectiveness of a stepsize by a feedback function motivated from a convergence measure and uses the feedback to adjust the stepsize through an online learning algorithm. Consequently, instantiations of OSGM achieve convergence rates that are asymptotically no worse than the optimal stepsize. OSGM yields desirable convergence guarantees on smooth convex problems, including 1) trajectory-dependent global convergence on smooth convex objectives; 2) an improved complexity result on smooth strongly convex problems, and 3) local superlinear convergence. Notably, OSGM constitutes a new family of first-order methods with non-asymptotic superlinear convergence, joining the celebrated quasi-Newton methods. Finally, OSGM explains the empirical success of the popular hypergradient-descent heuristic in optimization for machine learning.