← All setups

Restarted Schedule Gradient Descent

Descriptions may be stale. Consult the linked Lean sources.

Restarted Schedule Gradient Descent

We consider finding a stationary point of a possibly nonconvex function f:E→R on a finite-dimensional real inner product space E. The function is twice continuously differentiable, with L-Lipschitz gradient and ρ-Lipschitz Hessian, where L,ρ>0. A given starting point x0∈E satisfies f(x0)−infx∈Ef(x)≤Δ for Δ≥0. The oracle returns ∇f(x) at x. For ε>0, restarted schedule gradient descent must return x¯∈E with ∥∇f(x¯)∥≤ε for every realization.

The underlying optimization problem is infx∈Ef(x). The norm ∥⋅∥ is induced by the inner product on E, and ∥⋅∥op denotes the induced operator norm. The algorithm receives E,x0,L,ρ,Δ, and ε.

Our assumptions:

Assumption 1 (Gradient and Hessian regularity). The function f belongs to C2(E;R). Its Hessian ∇2f(x) is a linear operator from E to E, and for all x,y∈E, ∥∇f(x)−∇f(y)∥≤L∥x−y∥,∥∇2f(x)−∇2f(y)∥op≤ρ∥x−y∥.

Assumption 2 (Initial objective gap). The given starting point satisfies f(x0)−f(x)≤Δ,x∈E.

Our result is algorithm-specific: we analyze restarted schedule gradient descent. The method chooses thresholds G1,R∈R and a finite schedule (h0,…,hm−1), with m≥0 and hj>0 for 0≤j<m, using the available inputs. Neither threshold has a sign restriction, and the schedule may be empty. Define h~j=hj for j<m and h~j=0 for j≥m.

The method maintains a point xk, a restart centre ck, and an index jk, initialized by (x0,c0,j0)=(x0,x0,0). At call k, it queries gk=∇f(xk). If ∥gk∥≤ε, it freezes the point, centre, and index for all subsequent calls. Otherwise, while the method has not frozen, it applies the following update. If jk=0 and ∥gk∥>G1, then xk+1=xk−L−1gk,ck+1=ck,jk+1=0. In every other case, it sets yk={xk,jk=0,ck,jk>0,xk+1=xk−h~jkgk,ck+1=yk,jk+1={jk+1,jk+1<m and ∥xk+1−yk∥≤R,0,otherwise. Queries lie in E. After an allotted number N≥0 of oracle calls, the output is the current point x¯=xN. The required accuracy is ∥∇f(x¯)∥≤εfor every realization.

Results

On a finite-dimensional real inner-product space, f∈C2, ∇f is L-Lipschitz, ∇2f is ρ-Lipschitz, and f(x0)−f(x)≤Δ for every x, with L,ρ,ε>0 and Δ≥0. Exact gradient queries must produce ∥∇f(x^)∥≤ε deterministically. The setup restricts our construction to positive-step GD with threshold switching, distance restarts and a stopped-point output.

Gradient stationarity under a Lipschitz Hessian: HessianLipschitzGradientStationarity.
Result Oracle complexity Novelty Limitations
(1) FractalChebyshevGdStationarity (Ours) (⋆⋆) (review) O(Tκ−1/9log⁡(2+κ)+κ1/9+1)
(2) GD, step 1/L (Nesterov 2018, sec. 1.2.3) O(1+LΔ/ε2) (1): Momentum-free leading-term gain κ1/9/log⁡κ; proved constants require κ≳2145, T≳κ1/9. Method-specific advance, not improved problem-class complexity. (1) needs Hessian regularity and ρ knowledge. Larger constants; worse proved budget for 240≤κ<2145.
(3) Restarted AGD (Li and Lin 2023, Theorem 1, §4.1) O(Tκ−1/4+κ1/4+1), ε≲L2/ρ; includes final epoch. (1): At T=κ1/4, κ≳2145, costs O(κ5/36log⁡κ+κ1/9) versus O(κ1/4). Upper-bound saving from final-epoch cost; shortening that epoch is unresolved. (1) has a worse leading term by κ5/36log⁡κ when leading terms dominate; same gradient oracle and tuning knowledge.

Abbr: GD: gradient descent; AGD: accelerated gradient descent; κ=L2/(ρε); T=LΔ/ε2. Costs count exact gradient calls. Δ bounds the initial objective gap; log denotes the natural logarithm.

Li, Huan, and Zhouchen Lin. 2023. “Restarted Nonconvex Accelerated Gradient Descent: No More Polylogarithmic Factor in the O(ϵ−7/4) Complexity.” Journal of Machine Learning Research 24 (157): 1–37. https://www.jmlr.org/papers/v24/22-0522.html.
Nesterov, Yurii. 2018. Lectures on Convex Optimization. 2nd ed. Vol. 137. Springer Optimization and Its Applications. Springer. https://doi.org/10.1007/978-3-319-91578-4.

Lean setup