Covariance Accelerated High Probability — Covariance-Controlled Smooth Convex Minimization
Descriptions may be stale. Consult the linked Lean sources.
Covariance-Controlled Smooth Convex Minimization · Lean proof
Covariance-Controlled
Smooth Convex Minimization
We minimize a differentiable convex function on a finite-dimensional
real Hilbert space . Its gradient
is -Lipschitz, with , and a given point is within distance of a minimizer . At , the oracle returns an unbiased
gradient estimate using
independent samples from a
probability law . The noise has
second moment bounded by
and covariance bounded by times
the identity, where . For and , the goal is a measurable
output with ,
where is the law of all algorithm
and oracle randomness.
The optimization problem is Write for the inner
product on and for its induced norm. The
algorithm receives , the
measurable sample space ,
, , , , , , and .
Our assumptions:
Assumption 1 (Convexity and smoothness). The
function is Fréchet
differentiable everywhere on . For
every and ,
Assumption 2 (Initial distance). There exists such that
Assumption 3 (Stochastic gradient and covariance).
There are a probability measure
on and a jointly measurable
map . For every
, the random vector is Bochner integrable and is integrable
under . For every , At call , a query receives the reply . The sample variables are measurable, mutually
independent, and each has law .
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
Proved result
OracleTemplate.Convergence LongTails.Setups.CovarianceSmoothConvex.spec
LongTails.Theorems.CovarianceAcceleratedHighProbability.budget
Relevant previous results
No qualifying prior reference verified; this is not a proof of novelty.