Spiked Sub Gaussian Soft Cut Convex — Convex Minimization with Spiked Noise
Descriptions may be stale. Consult the linked Lean sources.
Convex Minimization with Spiked Noise · Lean proof
Convex
Minimization with Spiked Noise
We consider minimizing a convex, -Lipschitz function on , where is an integer and . A global minimizer satisfies , where . The oracle returns an unbiased
subgradient estimate with independent, identically distributed samples
and centered sub-Gaussian noise: its variance proxy is along the first
coordinate and in
orthogonal directions, where . For , the goal is a
measurable output
satisfying with
probability at least over the
algorithm and oracle randomness.
The optimization problem is We use the Euclidean inner product and norm, and index
coordinates by . The
algorithm receives , the
measurable sample space , and
;
the objective and oracle distribution are accessible only through oracle
replies.
Our assumptions:
Assumption 1 (Convexity and Lipschitz continuity).
For every and ,
Assumption 2 (Bounded minimizer). There exists such that
Assumption 3 (Spiked sub-Gaussian subgradient
oracle). There are a probability measure on , a map , and a jointly measurable map
. For every
, the map is Bochner integrable under
, and Define the directional variance proxy by For every and , the
random variable is integrable under and satisfies The sample sequence
has a probability
law on under which its
coordinate maps are measurable, mutually independent, and each has
distribution . At call , a query receives . The algorithm’s randomness is
independent of this sample sequence.
Queries may be made anywhere in . After the allotted oracle calls, the
output must be measurable
and satisfy
where is the joint law of the
algorithm’s randomness and the oracle sample sequence.
Proved result
OracleTemplate.Convergence LongTails.Setups.SpikedSubGaussianConvex.spec
LongTails.Theorems.SpikedSubGaussianSoftCutConvex.budget
Relevant previous results
No qualifying prior reference verified; this is not a proof of novelty.