Descriptions may be stale. Consult the linked Lean sources.
Restarted Schedule Gradient
Descent
We consider finding a stationary point of a possibly nonconvex
function on a
finite-dimensional real inner product space . The function is twice continuously
differentiable, with -Lipschitz
gradient and -Lipschitz
Hessian, where . A given
starting point satisfies
for . The oracle returns
at . For , restarted schedule
gradient descent must return with for every realization.
The underlying optimization problem is The norm is induced by the inner product
on , and denotes the
induced operator norm. The algorithm receives , and .
Our assumptions:
Assumption 1 (Gradient and Hessian regularity). The
function belongs to . Its Hessian is a linear operator from
to , and for all ,
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 and a finite schedule
, with and for , using the available inputs.
Neither threshold has a sign restriction, and the schedule may be empty.
Define for and for .
The method maintains a point , a restart centre , and an index , initialized by At call , it queries . If , it freezes the
point, centre, and index for all subsequent calls. Otherwise, while the
method has not frozen, it applies the following update. If and , then In every other case, it sets Queries lie in . After an allotted number of oracle calls, the output is the
current point . The
required accuracy is