Fractal Chebyshev Gd Stationarity — Restarted Schedule Gradient Descent
Descriptions may be stale. Consult the linked Lean sources.
Restarted Schedule Gradient Descent · Lean proof
Restarted Schedule Gradient Descent
We consider finding a stationary point of a possibly nonconvex
function
The underlying optimization problem is
Our assumptions:
Assumption 1 (Gradient and Hessian regularity). The
function
Assumption 2 (Initial objective gap). The given
starting point satisfies
Our result is algorithm-specific: we analyze restarted schedule
gradient descent. The method chooses thresholds
The method maintains a point
Proved result
OracleTemplate.Convergence LongTails.Setups.HessianLipschitzGradientStationarity.spec
OracleTemplate.RestartedScheduleGD.FractalChebyshevGdStationarity.budgetRelevant previous results
- Huan Li and Zhouchen Lin. Restarted
Nonconvex Accelerated Gradient Descent: No More Polylogarithmic Factor
in the O(ε⁻⁷⁄⁴) Complexity. 2022. Complexity:
exact-gradient calls for restarted AGD to obtain , including the final epoch; comparable in the regime and .