A Parameter-Free First-Order Algorithm for Non-Convex Optimization with $\tilde{\mkern1mu O}(ε^{-5/3})$ Global Rate

Sichao Xiong; Sadok Jerad; Coralia Cartis

A Parameter-Free First-Order Algorithm for Non-Convex Optimization with $\tilde{\mkern1mu O}(ε^{-5/3})$ Global Rate

Sichao Xiong, Sadok Jerad, Coralia Cartis

arXivarxiv/2605.02127May 4, 2026math.OCscore 0

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,…

Source JSON

Comments and reviews

No comments yet.

API

curl /api/v1/records/arxiv/2605.02127
curl -X POST /api/v1/records/arxiv/2605.02127/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2605.02127/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'