Descriptions may be stale. Consult the linked Lean sources.
Window SGD
under the PL Condition
We consider minimizing a possibly nonconvex function on a finite-dimensional
real inner product space . The
objective has a Lipschitz gradient, a Lipschitz Hessian, and a global
minimizer , and satisfies
the Polyak–Łojasiewicz condition. A given starting point has bounded
objective gap. At , the
oracle returns , an
unbiased gradient estimate using a fresh independent sample , with uniformly bounded second and
fourth noise moments. Window SGD must produce a measurable output with integrable objective
gap and ,
where and
expectation includes sampling and algorithm randomness.
The optimization problem is Write
for the inner product norm and for the induced
operator norm. Fix a starting point , a measurable sample space , and parameters
The algorithm receives , , , , , , , , , and .
Our assumptions:
Assumption 1 (Gradient and Hessian regularity). The
function is Fréchet
differentiable on , and its
gradient is Fréchet differentiable on . For every , Here is the derivative of the gradient.
Assumption 2 (Polyak–Łojasiewicz condition and
initial gap). There exists such that, for every , and the given starting point satisfies
Assumption 3 (Independent stochastic gradients and
fourth moments). There is a probability measure on and a jointly measurable map . The measurable
samples are
mutually independent, each with law . At its th call, the oracle returns for any query . For every fixed , is Bochner integrable under
, and Writing , both and are integrable, with
Our formulation is algorithm-specific: we analyze Window SGD. The
algorithm chooses a constant step size and integers from its inputs.
Independently of the oracle samples, it draws uniformly from and sets . Starting from the given , its recurrence for a budget of oracle calls is The output is . Calls continue to count
after the iterate is frozen. Thus, when , the output is the SGD
iterate at the uniformly selected index ; a smaller budget truncates the updates
at .
Let be the joint law of and the oracle samples. The output
must be measurable, its objective gap must be integrable under , and the accuracy requirement is