Descriptions may be stale. Consult the linked Lean sources.
Stochastic
Generalized Smooth Convex Minimization
We consider minimizing a differentiable convex function on a separable real
Hilbert space . The function is -smooth, with and . A given point has distance at most and objective gap at most from a global minimizer . The oracle returns unbiased
stochastic gradients with variance at most and an exponential squared-error
bound, where , using
independent identically distributed samples. Given and , the goal is a measurable
output satisfying with
probability at least over
oracle and algorithm randomness.
The optimization problem is The norm is induced by the inner product
on , and denotes the
induced operator norm. Let
be the measurable sample space. The algorithm receives , , , , , , , , , and ; the objective and sampling
distribution are accessed through the oracle.
Our assumptions:
Assumption 1 (Convexity and generalized smoothness).
The function is Fréchet
differentiable everywhere, its gradient is Fréchet differentiable, and
for every and , Here is the derivative of the gradient.
Assumption 2 (Initial distance and objective gap).
There exists such that
Assumption 3 (Light-tailed stochastic gradients).
There are a probability measure
on and a jointly measurable
map . For every
, the map is Bochner integrable, its
squared error is integrable, and When , the exponential below is
integrable and satisfies, for every , When , the variance condition gives
for -almost every , for each fixed .
The samples are
measurable, mutually independent random variables with common law under a joint probability law . At call , a query receives . The algorithm’s randomness is
independent of the entire sample sequence.
Queries may be made at any point of . After the allotted oracle calls, the
output must be
measurable and satisfy
where is the joint law of the
algorithm’s randomness and the oracle samples with law .