An Adaptive and Parameter-Free Nesterov's Accelerated Gradient Method for Convex Optimization

2025/05/16 by Jaewook J. Suh, Suh, Jaewook J., Shiqian Ma +1 · 5 citations
Computer Science · Engineering · Mathematics · #Advanced Optimization Algorithms Research #FOS: Mathematics #Optimization and Control (math.OC) #Sparse and Compressive Sensing Techniques #Stochastic Gradient Optimization Techniques

paper · pdf · doi:10.48550/arxiv.2505.11670

openalex publication_date 2025/05/16 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We propose AdaNAG, an adaptive accelerated gradient method based on Nesterov's accelerated gradient method. AdaNAG is line-search-free, parameter-free, and achieves the accelerated convergence rates f(x_k) - f_⋆ = O(1/k²) and min_i∈\1,…, k\ ‖∇ f(x_i)‖² = O(1/k³) for L-smooth convex function f. We provide a Lyapunov analysis for the convergence proof of AdaNAG, which additionally enables us to propose a novel adaptive gradient descent (GD) method, AdaGD. AdaGD achieves the non-ergodic convergence rate f(x_k) - f_⋆ = O(1/k), like the original GD. The analysis of AdaGD also motivated us to propose a generalized AdaNAG that includes practically useful variants of AdaNAG. Numerical results demonstrate that our methods outperform some other recent adaptive methods for representative applications.

Cited by

• Adaptive Accelerated Gradient Method for Smooth Convex Optimization
• History-Aware Adaptive High-Order Tensor Regularization
• A Practical Adaptive Subgame Perfect Gradient Method
• A Simple Adaptive Proximal Gradient Method for Nonconvex Optimization
• Linesearch-free adaptive Bregman proximal gradient for convex minimization without relative smoothness

Related

• Adaptive Gradient Methods for Constrained Convex Optimization and Variational Inequalities
• Adaptive Accelerated Gradient Method for Smooth Convex Optimization
• Adaptive Acceleration Without Strong Convexity Priors Or Restarts
• A geometric alternative to Nesterov's accelerated gradient descent
• The Global R-linear Convergence of Nesterov's Accelerated Gradient Method with Unknown Strongly Convex Parameter