Adaptive and Tuning-free First-Order Methods via Lyapunov Analysis

Abstract

Choosing effective step sizes is a central challenge in first-order optimization methods, particularly for large-scale problems. In this talk, we present a Lyapunov-analysis-based framework for designing adaptive, parameter-free, and line-search-free gradient methods, in which update rules for the step sizes are derived from the convergence proof. In particular, we introduce an adaptive Nesterov’s accelerated gradient method, which retains the structure and optimal accelerated rates of Nesterov’s method while being parameter-free and line-search-free. The method achieves an O(1/k^2) convergence rate in function values together with an O(1/k^3) convergence rate for the best-iterate squared gradient norm. Beyond acceleration, we also show that the same design principle yields other novel adaptive methods, including an adaptive gradient descent method and its extension to Riemannian optimization. Numerical experiments illustrate the practical competitiveness of these methods. Additionally, we briefly discuss an AI-assisted approach that may further enhance the design framework.

For more info, please follow this link.