Descriptions may be stale. Consult the linked Lean sources.
Stochastic Constrained
Quasar Minimization
We consider minimizing over a compact convex
set in a finite-dimensional real
Hilbert space . On , the function has an -Lipschitz gradient, where , and is -quasar-convex relative to a
minimizer , where . The oracles return
unbiased stochastic gradients with bounded variance using independent,
identically distributed samples, and exact Euclidean projections onto
. Given and , the goal is a measurable
output satisfying both
and with
probability at least over
sampling and algorithm randomness.
The optimization problem is Write for the inner
product on and for its induced norm. The
algorithm receives , the
measurable sample space , a
starting point , and the
parameters , , , , and ; the objective, feasible
set, minimizer, and sampling distribution are accessed through the
oracles.
Our assumptions:
Assumption 1 (Feasible geometry). The set is compact and convex,
contains and , and satisfies
Assumption 2 (Smoothness and quasar convexity). The
function is Fréchet
differentiable at every point of ,
and, for every ,
Assumption 3 (Stochastic gradient oracle). There are
a probability measure on and a jointly measurable map . For every , the random vector is Bochner integrable and is integrable
under , with The oracle uses a sequence of measurable, mutually
independent sample variables, each with law , independent of the algorithm’s
randomness. At a stochastic gradient call with query , it returns using the sample at that
call’s index.
Assumption 4 (Exact projection oracle). The
projection oracle returns
at , where
Both oracles accept queries throughout ; the gradient and moment conditions
above apply on . Stochastic
gradient calls and projection calls have separate budgets. After these
calls, the output must
be measurable and satisfy where
is the joint law of the samples
and the independent algorithm randomness.