Convex Minimization with Spiked Noise
Descriptions may be stale. Consult the linked Lean sources.
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.
Results
Lean setup