Convex Minimization with Distance-Dependent Subgradient Moments
Descriptions may be stale. Consult the linked Lean sources.
Convex
Minimization with Distance-Dependent Subgradient Moments
We minimize a real-valued function that is convex on a closed convex set
in -dimensional Euclidean space. A given
lies within distance of a minimizer on . The oracle returns either an exact
projection onto or a random
vector drawn using a fresh independent sample. At each , this vector has a subgradient
mean relative to and second
moment at most ,
where . For and , the goal is a
measurable output
satisfying with
probability at least .
The optimization problem is The algorithm receives the dimension , the starting point
, and the parameters . Both query
types accept any point in and share a single call
budget.
Our assumptions:
Assumption 1 (Convexity and initial distance). The
function is Borel
measurable. On the closed convex set , it satisfies
for every and . The point belongs to , and there exists such that .
Assumption 2 (Subgradient mean and second moment).
Let be
independent measurable samples with common law on a measurable space , independent of the algorithm’s
randomness. A subgradient query at on call returns , where
is jointly measurable. For each and , the
vector is Bochner
integrable and is
integrable. Writing ,
we require
A projection query at returns the Euclidean
projection . This map is
measurable, takes values in , and
satisfies After the allotted calls, the output must be measurable and belong to
for every realization. Under the
joint law of the samples and the
algorithm’s randomness, it must satisfy
Results
Lean setup