Descriptions may be stale. Consult the linked Lean sources.
Step-Decay
SGD in River Valleys
We consider minimizing a possibly nonconvex function on a finite-dimensional
real inner product space . The
objective combines a smooth function along a subspace with a positive
quadratic penalty around a curved valley. Derivative bounds, curvature
separation conditions, and a bound on the initial objective gap control
this geometry. The oracle returns unbiased stochastic gradients with
independent, identically distributed samples and separately bounded
noise variances along and across the valley. Starting from a given , step-decay SGD must return
with , where and is the joint law of sampling and
algorithm randomness.
The optimization problem is The norm on is
induced by its inner product. All operator and multilinear norms below
are induced operator norms. The algorithm receives , the measurable sample space , the starting point , and the parameters The objective, its geometric decomposition, and
the sampling distribution are accessed only through the oracle.
Our assumptions:
Assumption 1 (Valley geometry and regularity). There
exist a linear subspace , twice Fréchet differentiable maps and , and a self-adjoint linear
operator . Write and for the orthogonal projections onto
and , respectively. Then For every , the hill component satisfies Let , with derivative
viewed as a bilinear operator
on . For every , The quadratic operator preserves and satisfies, for every ,
Assumption 2 (Initial objective gap). The given
starting point satisfies
Assumption 3 (Stochastic gradient oracle). There
exist a probability measure on
and a jointly measurable map
. At its th query , the oracle returns , where the measurable random
variables are
independent with common law .
Their joint law is independent of the algorithm’s randomness. Queries
may be made anywhere in .
For every fixed , the map
is Bochner integrable
and Writing , both
projected squared norms below are integrable and satisfy
Assumption 4 (Parameter separation). Define the
following combinations of the given parameters: They obey
Our result is algorithm-specific: we analyze step-decay SGD with a
uniformly randomized switching time. The algorithm chooses two step
sizes and
integers from its inputs.
It draws uniformly from , independently of the
oracle samples, and starts at the given . At call , it queries and uses the recurrence After a budget of oracle calls, the output is . Calls after still count toward , although they leave the iterate
unchanged.
The output must be measurable, its gradient norm must be integrable
under , and the required
stationarity criterion is