# A simple uniformly optimal method without line search for convex optimization

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

## Key facts

- Cited by 18 papers in the map (data through 14 Oct 2026).
- Builds on 30 of its 51 references that are in the map.
- First posted on arXiv 16 Oct 2023.

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

- [On the Convergence of Stochastic Gradient Descent with Adaptive Stepsizes](https://mlsanity.com/paper/1805.08114/) (2018)
- [Coin Betting and Parameter-Free Online Learning](https://mlsanity.com/paper/1602.04128/) (2016)
- [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)
- [Lipschitz and Comparator-Norm Adaptivity in Online Learning](https://mlsanity.com/paper/2002.12242/) (2020)
- [Online Adaptive Methods, Universality and Acceleration](https://mlsanity.com/paper/1809.02864/) (2018)
- [Making SGD Parameter-Free](https://mlsanity.com/paper/2205.02160/) (2022)
- [Online to Offline Conversions, Universality and Adaptive Minibatch Sizes](https://mlsanity.com/paper/1705.10499/) (2017)
- [Golden Ratio Algorithms for Variational Inequalities](https://mlsanity.com/paper/1803.08832/) (2018)
- [Online Learning Without Prior Information](https://mlsanity.com/paper/1703.02629/) (2017)
- [Simple and optimal methods for stochastic variational inequalities, I: operator extrapolation](https://mlsanity.com/paper/2011.02987/) (2020)
- [DoWG Unleashed: An Efficient Universal Parameter-Free Gradient Descent Method](https://mlsanity.com/paper/2305.16284/) (2023)
- [An optimal randomized incremental gradient method](https://mlsanity.com/paper/1507.02000/) (2015)
- [Benchopt: Reproducible, efficient and collaborative optimization benchmarks](https://mlsanity.com/paper/2206.13424/) (2022)
- [Simple and optimal methods for stochastic variational inequalities, II: Markovian noise and policy evaluation in reinforcement learning](https://mlsanity.com/paper/2011.08434/) (2020)
- [Adaptive Proximal Gradient Method for Convex Optimization](https://mlsanity.com/paper/2308.02261/) (2023)
- [Normalized Gradients for All](https://mlsanity.com/paper/2308.05621/) (2023)
- [Adaptive proximal algorithms for convex optimization under local Lipschitz continuity of the gradient](https://mlsanity.com/paper/2301.04431/) (2023)
- [Adaptive Gradient Methods for Constrained Convex Optimization and Variational Inequalities](https://mlsanity.com/paper/2007.08840/) (2020)
- [Bundle-Level Type Methods Uniformly Optimal for Smooth and Nonsmooth Convex Optimization](https://mlsanity.com/paper/1309.5547/) (2013)
- [Random gradient extrapolation for distributed and stochastic optimization](https://mlsanity.com/paper/1711.05762/) (2017)
- [A Simple Nearly-Optimal Restart Scheme For Speeding-Up First Order Methods](https://mlsanity.com/paper/1803.00151/) (2018)
- [Beyond the Golden Ratio for Variational Inequality Algorithms](https://mlsanity.com/paper/2212.13955/) (2022)
- [Accelerated stochastic approximation with state-dependent noise](https://mlsanity.com/paper/2307.01497/) (2023)
- [On Optimal Universal First-Order Methods for Minimizing Heterogeneous Sums](https://mlsanity.com/paper/2208.08549/) (2022)
- [A unified analysis of a class of proximal bundle methods for solving hybrid convex composite optimization problems](https://mlsanity.com/paper/2110.01084/) (2021)
- [Adaptive restart of accelerated gradient methods under local quadratic growth condition](https://mlsanity.com/paper/1709.02300/) (2017)
- [Accelerated first-order methods for convex optimization with locally Lipschitz continuous gradient](https://mlsanity.com/paper/2206.01209/) (2022)

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

- [Projected gradient methods for nonconvex and stochastic smooth optimization: new complexities and auto-conditioned stepsizes](https://mlsanity.com/paper/2412.14291/) (2024)
- [Analysis of an Idealized Stochastic Polyak Method and its Application to Black-Box Model Distillation](https://mlsanity.com/paper/2504.01898/) (2025)
- [Nesterov Finds GRAAL: Optimal and Adaptive Gradient Method for Convex Optimization](https://mlsanity.com/paper/2507.09823/) (2025)
- [Gradient-Variation Online Adaptivity for Accelerated Optimization with H"older Smoothness](https://mlsanity.com/paper/2511.02276/) (2025)
- [Adaptive proximal gradient methods are universal without approximation](https://mlsanity.com/paper/2402.06271/) (2024)
- [Gradient Methods with Online Scaling Part I. Theoretical Foundations](https://mlsanity.com/paper/2505.23081/) (2025)
- [On the convergence of adaptive first order methods: proximal gradient and alternating minimization algorithms](https://mlsanity.com/paper/2311.18431/) (2023)
- [Auto-conditioned primal-dual hybrid gradient method and alternating direction method of multipliers](https://mlsanity.com/paper/2410.01979/) (2024)
- [Glocal Smoothness: Line search and adaptive step sizes can help in theory too!](https://mlsanity.com/paper/2506.12648/) (2025)
- [Optimization on a Finer Scale: Bounded Local Subgradient Variation Perspective](https://mlsanity.com/paper/2403.16317/) (2024)
- [The inexact power augmented Lagrangian method for constrained nonconvex optimization](https://mlsanity.com/paper/2410.20153/) (2024)
- [Online Learning-guided Learning Rate Adaptation via Gradient Alignment](https://mlsanity.com/paper/2506.08419/) (2025)
- [Optimistic Online-to-Batch Conversions for Accelerated Convergence and Universality](https://mlsanity.com/paper/2511.06597/) (2025)
- [Stochastic Adaptive Gradient Descent Without Descent](https://mlsanity.com/paper/2509.14969/) (2025)
- [Adaptive Delayed-Update Cyclic Algorithm for Variational Inequalities](https://mlsanity.com/paper/2603.29128/) (2026)
- [Stochastic Auto-conditioned Fast Gradient Methods with Optimal Rates](https://mlsanity.com/paper/2604.06525/) (2026)
- [Provable Parameter-Free Fixed-Point Algorithms with Linear Convergence Rates](https://mlsanity.com/paper/2608.09022/) (2026)
- [Local LMO is Secretly a Projection Method!](https://mlsanity.com/paper/2609.33383/) (2026)

## Abstract (arXiv)

Line search (or backtracking) procedures have been widely employed into first-order methods for solving convex optimization problems, especially those with unknown problem parameters (e.g., Lipschitz constant). In this paper, we show that line search is superfluous in attaining the optimal rate of convergence for solving a convex optimization problem whose parameters are not given a priori. In particular, we present a novel accelerated gradient descent type algorithm called auto-conditioned fast gradient method (AC-FGM) that can achieve an optimal O(1/k2) rate of convergence for smooth convex optimization without requiring the estimate of a global Lipschitz constant or the employment of line search procedures. We then extend AC-FGM to solve convex optimization problems with H"older continuous gradients and show that it automatically achieves the optimal rates of convergence uniformly for all problem classes with the desired accuracy of the solution as the only input. Finally, we report some encouraging numerical results that demonstrate the advantages of AC-FGM over the previously developed parameter-free methods for convex optimization.