← All setups

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 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.

Proved result

⌈1000⋅log2⁡(2+L2ρ⋅ε)⋅(ρ⋅εL2)19⋅L⋅Δε2+(L2ρ⋅ε)19+2⌉+

OracleTemplate.Convergence LongTails.Setups.HessianLipschitzGradientStationarity.spec
  OracleTemplate.RestartedScheduleGD.FractalChebyshevGdStationarity.budget

Relevant previous results