A Parameter-Free First-Order Algorithm for Non-Convex Optimization with $\tilde{\mkern1mu O}(ε^{-5/3})$ Global Rate
Provides a practical, parameter-free algorithm for non-convex optimization that matches the best theoretical rate, benefiting practitioners who lack knowledge of smoothness constants.
PF-AGD is the first parameter-free accelerated first-order method achieving the best-known oracle complexity of O(ε^{-5/3} log(1/ε)) for smooth non-convex optimization, and empirically outperforms existing parameter-free methods and nonlinear conjugate gradient methods.
We introduce PF-AGD, the first parameter-free, deterministic, accelerated first-order method to achieve $O(ε^{-5/3}\log(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.