Descriptions may be stale. Consult the linked Lean sources.
Nonsmooth Hidden Convex
Minimization
We consider minimizing on a finite-dimensional real Hilbert space , where is convex and is a differentiable bi-Lipschitz
homeomorphism with Lipschitz derivative. The objective can be nonsmooth and nonconvex. A
global minimizer exists,
and whenever , for a given radius . The oracle returns
independent-sample estimates of a subgradient of pulled back through the adjoint
derivative of , with unbiased
means and uniformly bounded second moments. For , the goal is a
measurable output with
integrable objective gap satisfying ,
averaging over sampling and algorithm randomness.
The optimization problem is Write for the inner
product on and for its induced norm. Operator
norms are
the induced operator norms. The parameters satisfy The algorithm
receives , a measurable sample
space , and ; the
functions , their derivative
field, and the oracle distribution are accessible only through the
specified oracle replies.
Our assumptions:
Assumption 1 (Hidden convex structure). The function
is convex: for all
and , The map
is a homeomorphism,
Fréchet differentiable at every point, with derivative . For all ,
Assumption 2 (Attainment and boundary condition).
There exists such that
The objective also satisfies
Assumption 3 (Stochastic pulled subgradients). There
is a field such that, for
every , some satisfies where
is the adjoint of .
Let be a probability measure
on . The oracle map is jointly
measurable. For every , is Bochner integrable and
is integrable
under , with At call , a
query receives . The measurable samples are independent with
common law under a joint
probability law on . The algorithm’s
randomness is independent of this sample sequence.
Queries may be made at any point of . After the allotted oracle calls, the
output must be measurable,
its gap must
be integrable, and it must satisfy
where is the joint law of the
algorithm’s randomness and the oracle sample sequence.