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

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.