Descriptions may be stale. Consult the linked Lean sources.
Proximal
Linear-Decay SGD
We consider minimizing
over a closed convex set in a
separable real Hilbert space ,
where is a probability law on a
measurable sample space . Each
sample loss is
convex with an -Lipschitz
gradient, , and is lower
semicontinuous and convex on . A
given starting point has bounded distance and objective gap to a
minimizer , where gradient
variance is bounded. The oracle returns independent sampled gradients or
exact proximal minimizers. Proximal SGD with linearly decaying steps
must return a measurable output with integrable gap satisfying
,
where and
expectation is over the samples.
Write The optimization problem is The norm is induced by the inner product
on . The algorithm receives , , the starting point , and the parameters The model consists
of , , its sample gradient , , , and a proximal map ; access to it is through the oracle below.
Our assumptions:
Assumption 1 (Sample losses). The map is jointly
measurable. For every ,
the function is
convex and Fréchet differentiable on , with For every , the function is integrable under
.
Assumption 2 (Composite structure and proximal
access). The set is
closed and convex, and .
The function is
lower semicontinuous on and
convex on . For every and , the oracle’s proximal map
satisfies The map is defined for
all real , but this minimization
property is required only for .
Assumption 3 (Initialization and variance at a
minimizer). There exists such that The random vector is Bochner integrable
under . Define its mean by .
The squared centered norm is integrable and satisfies
Let be
measurable, mutually independent samples, each with law , and let denote their joint law. At call , a gradient query returns , while a proximal query
returns . Both
query types count toward one shared oracle-call budget; proximal replies
do not depend on the sample at that call.
Our formulation is algorithm-specific: we analyze proximal SGD with
linear step-size decay. The algorithm chooses and an integer from its inputs and starts at the
given . It alternates a gradient
query and a proximal query according to When ,
the step-size formula is interpreted as . The parameter specifies the decay schedule;
termination is determined by the allotted number of calls. For a budget
of calls, the output is the
last completed proximal iterate, Thus
each completed update uses two calls, and an additional gradient call
does not change the output.
The output must be measurable under , and its objective gap must be
integrable and satisfy