Descriptions may be stale. Consult the linked Lean sources.
Gap-Smooth
Convex Minimization
We consider minimizing a differentiable convex function on a separable real
Hilbert space . A local quadratic
upper model has curvature controlled by the gap to a global minimizer
, and a given starting point
has bounded distance and objective gap to that minimizer. The oracle
returns independent-sample, unbiased stochastic gradients whose variance
is bounded proportionally to the squared gradient norm. For tolerance
and failure
probability , the
goal is a measurable output satisfying ,
where is the joint law of
sampling and independent algorithm randomness.
The optimization problem is Equip with its
Borel sigma-algebra, and write for the norm induced by its
inner product. Let be a
measurable sample space and the given starting point. The parameters satisfy The algorithm receives , , , and all seven parameters .
Our assumptions:
Assumption 1 (Convexity and initialization). The
function is Fréchet
differentiable everywhere on and
satisfies There exists such that
Assumption 2 (Gap-dependent upper model). For every
satisfying
the objective obeys
Assumption 3 (Strong-growth stochastic oracle).
There exist a probability measure on and a jointly measurable map . For every , the map is Bochner integrable and
is
integrable under , with At call , a query receives , where the measurable samples
are mutually
independent with common law .
Algorithm randomness is independent of the entire sample sequence.
After the allotted oracle calls, the algorithm must return a
measurable output with