Gradient Methods with Online Scaling

摘要

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 stepsize for the iteration trajectory. For smooth strongly convex optimization, our framework provides an (κ^⋆log(1/ε)) asymptotic complexity result, where κ^⋆ is the condition number achievable by the optimal preconditioner, improving on the previous (√(n)κ^⋆log(1/ε)) result. For smooth convex optimization, we obtain the first convergence guarantee for the widely used hypergradient descent heuristic.