Descriptions may be stale. Consult the linked Lean sources.
Local Hidden Convex
Stochastic Minimization
We minimize a differentiable, possibly nonconvex function on a finite-dimensional
real Hilbert space . Its gradient
is -Lipschitz, with , and a given point is within distance of a global minimizer . Locally, is a convex function composed with a
differentiable change of coordinates whose derivative is uniformly
nonsingular and varies slowly. The oracle returns unbiased stochastic
gradients with variance at most , where , using independent samples.
For , the goal is a
measurable output with
integrable gap and ,
averaging over oracle and independent algorithm randomness.
The optimization problem is The norm is induced by the inner product
on , and denotes the
induced operator norm. Write
and for the open
and closed balls. The algorithm receives only , the measurable sample space , , , , and ; the parameters , , and may enter the
oracle-call budget but are not algorithm inputs.
Our assumptions:
Assumption 1 (Local hidden convexity). There exist
functions and
, an open convex set , and a map assigning a linear operator to each , such that The
function is differentiable on
and satisfies For every , we have , the map is Fréchet differentiable at with derivative , and The
derivative satisfies
Assumption 2 (Global smoothness). The function is Fréchet differentiable everywhere on
, and
Assumption 3 (Initial distance). There exists such that
Assumption 4 (Stochastic gradient oracle). Let be a probability measure on . The oracle is a jointly
measurable map . For every , the
random vector is Bochner
integrable and is integrable for , with At the th
query , the oracle returns , where are independent with
common law and are independent
of the algorithm’s randomness.
Queries may be made at any point of . Let be the joint law of the oracle samples
and the algorithm’s randomness. After the allotted oracle calls, the
output must be measurable,
its objective gap must be integrable under , and it must satisfy