Covariance Soft Cut Convex — Covariance-Bounded Convex Minimization
Descriptions may be stale. Consult the linked Lean sources.
Covariance-Bounded Convex Minimization · Lean proof
Covariance-Bounded Convex
Minimization
We consider minimizing a convex, -Lipschitz function , where and . A global minimizer satisfies , where and is the Euclidean norm. The
oracle returns an unbiased stochastic subgradient using independent,
identically distributed samples, with noise variance at most in every unit direction, where
. For , the goal is a
measurable output
satisfying with
probability at least under
, the joint law of the oracle
samples and independent algorithm randomness.
The optimization problem is Write
for the
Euclidean inner product. The algorithm receives , , , , , and the measurable
sample space .
Our assumptions:
Assumption 1 (Convexity and Lipschitz continuity).
For every and
,
Assumption 2 (Bounded minimizer). There exists such that
Assumption 3 (Stochastic subgradients and
covariance). There exist a probability measure on , a map , and a
jointly measurable map .
For every , the map
is Bochner integrable
under , and is integrable under
. For all , At call , a query receives . The sample variables are measurable, mutually
independent, and each has law .
The algorithm’s randomness is independent of the entire sample
sequence.
Queries may be made at any point of . After the allotted oracle
calls, the output must be measurable
and satisfy
Proved result
OracleTemplate.Convergence LongTails.Setups.CovarianceBoundedConvex.spec
LongTails.Theorems.CovarianceSoftCutConvex.budget
Relevant previous results
No qualifying prior reference verified; this is not a proof of novelty.