Finite Variance Generalized Accelerated Convex — Finite-Variance Generalized Smooth Convex Minimization
Descriptions may be stale. Consult the linked Lean sources.
Finite-Variance Generalized Smooth Convex Minimization · Lean proof
Finite-Variance
Generalized Smooth Convex Minimization
We consider minimizing a 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 an unbiased
stochastic gradient with variance at most , where , using independent,
identically distributed samples. For and , the goal is a measurable
output satisfying
,
where is the joint law of the
samples and independent 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 on , and its
gradient is Fréchet
differentiable. For every
and ,
Generalized smoothness means that where is a bounded linear operator from to .
Assumption 2 (Initial distance and objective gap).
There exists such that
Assumption 3 (Finite-variance stochastic gradients).
There exist a probability measure on and a jointly measurable map . For every , the map is Bochner integrable under
, the squared error is
integrable, and At call , a query receives . The sample variables are measurable and
mutually independent, each with law , and their joint law is independent
of the algorithm’s randomness.
Queries may be made at any point of . After the allotted oracle calls, the
algorithm must return a measurable output satisfying
Proved result
OracleTemplate.Convergence LongTails.Setups.FiniteVarianceGeneralizedSmoothAndConvex.spec
OracleTemplate.RobustGeneralized.FiniteVarianceGeneralizedAcceleratedConvex.budget
Relevant previous results
No qualifying prior reference verified; this is not a proof of novelty.