Descriptions may be stale. Consult the linked Lean sources.
High-Dimensional
Constrained Quasar Minimization
We minimize a possibly nonconvex function over a
compact convex set of diameter at
most . On , its gradient is -Lipschitz, with , and is -quasar-convex relative to a
minimizer , with . Two oracles return
unbiased stochastic gradients with variance at most , where , using independent binary
samples, and exact projections onto . For and , the goal is a
measurable output
satisfying and with
probability at least .
The optimization problem is We use the Euclidean inner product and norm on . A starting point is given. The algorithm receives
and accesses the objective and feasible set through the two oracles.
The parameters satisfy To state the dimension requirement, define The required regime is
Our assumptions:
Assumption 1 (Feasible set and minimizer). The set
is compact
and convex, contains and a
fixed point , and satisfies
Assumption 2 (Smoothness and quasar convexity). The
function is Fréchet
differentiable at every point of .
For all , Its quasar-convexity condition is
Assumption 3 (Stochastic gradient oracle). There is
a probability distribution on
and a jointly measurable
map .
For each , the vector is Bochner integrable and its
squared error is integrable under , with The samples are measurable,
mutually independent, have common law , and are independent of the
algorithm’s randomness. At the th
oracle call, a stochastic gradient query at returns .
Assumption 4 (Projection oracle). The projection
oracle returns at , where
Both oracles accept queries anywhere in ; the gradient and moment
conditions above apply on .
Stochastic gradient calls and projection calls are counted separately.
After the allotted calls, the output must be measurable
and satisfy where is the joint law of the algorithm’s
randomness and the independent oracle samples.