# Nesterov Finds GRAAL: Optimal and Adaptive Gradient Method for Convex Optimization

arXiv: https://arxiv.org/abs/2507.09823 · HTML: https://mlsanity.com/paper/2507.09823/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 25 of its 39 references that are in the map.
- First posted on arXiv 13 Jul 2025.

## Builds on (most cited first, 25 of 25)

- [Training GANs with Optimism](https://mlsanity.com/paper/1711.00141/) (2017)
- [On the Convergence of Stochastic Gradient Descent with Adaptive Stepsizes](https://mlsanity.com/paper/1805.08114/) (2018)
- [Prodigy: An Expeditiously Adaptive Parameter-Free Learner](https://mlsanity.com/paper/2306.06101/) (2023)
- [Black-Box Reductions for Parameter-free Online Learning in Banach Spaces](https://mlsanity.com/paper/1802.06293/) (2018)
- [Learning-Rate-Free Learning by D-Adaptation](https://mlsanity.com/paper/2301.07733/) (2023)
- [DoG is SGD's Best Friend: A Parameter-Free Dynamic Step Size Schedule](https://mlsanity.com/paper/2302.12022/) (2023)
- [Adaptive Gradient Descent without Descent](https://mlsanity.com/paper/1910.09529/) (2019)
- [UniXGrad: A Universal, Adaptive Algorithm with Optimal Guarantees for Constrained Optimization](https://mlsanity.com/paper/1910.13857/) (2019)
- [Online Adaptive Methods, Universality and Acceleration](https://mlsanity.com/paper/1809.02864/) (2018)
- [Golden Ratio Algorithms for Variational Inequalities](https://mlsanity.com/paper/1803.08832/) (2018)
- [A Forward-Backward Splitting Method for Monotone Inclusions Without Cocoercivity](https://mlsanity.com/paper/1808.04162/) (2018)
- [Revisiting Stochastic Extragradient](https://mlsanity.com/paper/1905.11373/) (2019)
- [DoWG Unleashed: An Efficient Universal Parameter-Free Gradient Descent Method](https://mlsanity.com/paper/2305.16284/) (2023)
- [Parameter-free Stochastic Optimization of Variationally Coherent Functions](https://mlsanity.com/paper/2102.00236/) (2021)
- [Normalized Gradients for All](https://mlsanity.com/paper/2308.05621/) (2023)
- [A simple uniformly optimal method without line search for convex optimization](https://mlsanity.com/paper/2310.10082/) (2023)
- [Accelerated Primal-Dual Gradient Method for Smooth and Convex-Concave Saddle-Point Problems with Bilinear Coupling](https://mlsanity.com/paper/2112.15199/) (2021)
- [Accelerated Parameter-Free Stochastic Optimization](https://mlsanity.com/paper/2404.00666/) (2024)
- [Beyond the Golden Ratio for Variational Inequality Algorithms](https://mlsanity.com/paper/2212.13955/) (2022)
- [SGD with Adaptive Preconditioning: Unified Analysis and Momentum Acceleration](https://mlsanity.com/paper/2506.23803/) (2025)
- [Stabilized Barzilai-Borwein method](https://mlsanity.com/paper/1907.06409/) (2019)
- [Grad-GradaGrad? A Non-Monotone Adaptive Stochastic Gradient Method](https://mlsanity.com/paper/2206.06900/) (2022)
- [Universality of AdaGrad Stepsizes for Stochastic Optimization: Inexact Oracle, Acceleration and Variance Reduction](https://mlsanity.com/paper/2406.06398/) (2024)
- [On Linear Convergence in Smooth Convex-Concave Bilinearly-Coupled Saddle-Point Optimization: Lower Bounds and Optimal Algorithms](https://mlsanity.com/paper/2411.14601/) (2024)
- [Universal fast gradient method for stochastic composit optimization problems](https://mlsanity.com/paper/1604.05275/) (2016)

## Built on by (most cited first, 5 of 5)

- [Non-Euclidean SGD for Structured Optimization: Unified Analysis and Improved Rates](https://mlsanity.com/paper/2511.11466/) (2025)
- [Evolution of Optimization Methods: Algorithms, Scenarios, and Evaluations](https://mlsanity.com/paper/2604.12968/) (2026)
- [Near-Optimal Convergence of Accelerated Gradient Methods under Generalized and (L0, L1)-Smoothness](https://mlsanity.com/paper/2508.06884/) (2025)
- [Decentralized Stochastic Nonconvex Optimization under the (L0,L1)-Smoothness](https://mlsanity.com/paper/2509.08726/) (2025)
- [Adaptive Delayed-Update Cyclic Algorithm for Variational Inequalities](https://mlsanity.com/paper/2603.29128/) (2026)

## Abstract (arXiv)

In this paper, we focus on the problem of minimizing a continuously differentiable convex objective function, minx f(x). Recently, Malitsky (2020); Alacaoglu et al.(2023) developed an adaptive first-order method, GRAAL. This algorithm computes stepsizes by estimating the local curvature of the objective function without any line search procedures or hyperparameter tuning, and attains the standard iteration complexity O(LlVert x0-x^*rVert2/ε) of fixed-stepsize gradient descent for L-smooth functions. However, a natural question arises: is it possible to accelerate the convergence of GRAAL to match the optimal complexity O(√LlVert x0-x^*rVert2/ε) of the accelerated gradient descent of Nesterov (1983)? Although some attempts have been made by Li and Lan (2025); Suh and Ma (2025), the ability of existing accelerated algorithms to adapt to the local curvature of the objective function is highly limited. We resolve this issue and develop GRAAL with Nesterov acceleration, which can adapt its stepsize to the local curvature at a geometric, or linear, rate just like non-accelerated GRAAL. We demonstrate the adaptive capabilities of our algorithm by proving that it achieves near-optimal iteration complexities for L-smooth functions, as well as under a more general (L0,L1)-smoothness assumption (Zhang et al., 2019).