# A Parameter-Free First-Order Algorithm for Non-Convex Optimization with tildemkern1mu O(ε-5/3) Global Rate

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 16 of its 41 references that are in the map.
- First posted on arXiv 4 May 2026.

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

- [Lower Bounds for Finding Stationary Points I](https://mlsanity.com/paper/1710.11606/) (2017)
- [Painless Stochastic Gradient: Interpolation, Line-Search, and Convergence Rates](https://mlsanity.com/paper/1905.09997/) (2019)
- [Accelerated Gradient Methods for Nonconvex Nonlinear and Stochastic Programming](https://mlsanity.com/paper/1310.3787/) (2013)
- [Accelerated Gradient Descent Escapes Saddle Points Faster than Gradient Descent](https://mlsanity.com/paper/1711.10456/) (2017)
- ["Convex Until Proven Guilty": Dimension-Free Acceleration of Gradient Descent on Non-Convex Functions](https://mlsanity.com/paper/1705.02766/) (2017)
- [Neon2: Finding Local Minima via First-Order Oracles](https://mlsanity.com/paper/1711.06673/) (2017)
- [A Newton-CG Algorithm with Complexity Guarantees for Smooth Unconstrained Optimization](https://mlsanity.com/paper/1803.02924/) (2018)
- [Restarted Nonconvex Accelerated Gradient Descent: No More Polylogarithmic Factor in the O(ε-7/4) Complexity](https://mlsanity.com/paper/2201.11411/) (2022)
- [Global Convergence Rate Analysis of a Generic Line Search Algorithm with Noise](https://mlsanity.com/paper/1910.04055/) (2019)
- [Parameter-free accelerated gradient descent for nonconvex minimization](https://mlsanity.com/paper/2212.06410/) (2022)
- [Improved Complexity for Smooth Nonconvex Optimization: A Two-Level Online Learning Approach with Quasi-Newton Methods](https://mlsanity.com/paper/2412.02175/) (2024)
- [First and zeroth-order implementations of the regularized Newton method with lazy approximated Hessians](https://mlsanity.com/paper/2309.02412/) (2023)
- [A nonlinear conjugate gradient method with complexity guarantees and its application to nonconvex regression](https://mlsanity.com/paper/2201.08568/) (2022)
- [Universal heavy-ball method for nonconvex optimization under H"older continuous Hessians](https://mlsanity.com/paper/2303.01073/) (2023)
- [Nonlinear conjugate gradient for smooth convex functions](https://mlsanity.com/paper/2111.11613/) (2021)
- [Parameter-Free Accelerated Quasi-Newton Method for Nonconvex Optimization](https://mlsanity.com/paper/2512.09439/) (2025)

## Abstract (arXiv)

We introduce PF-AGD, the first parameter-free, deterministic, accelerated first-order method to achieve O(ε-5/3log(1/ε)) oracle complexity bound when minimizing sufficiently smooth, non-convex functions; this is the best-known bound for first-order methods on smooth non-convex objectives. Unlike existing methods possessing this rate that require a priori knowledge of smoothness constants, we use an adaptive backtracking scheme and a gradient-based restart mechanism to estimate local curvature. This yields a practical algorithm that matches best-known theoretical rates. Empirically, PF-AGD outperforms the practical variant of AGD-Until-Guilty (Carmon et al., 2017), as well as other parameter-free variants, and is a viable alternative to nonlinear conjugate gradient methods.