Stochastic Generalized Lipschitz Convex — Stochastic Generalized Lipschitz Convex Minimization
Descriptions may be stale. Consult the linked Lean sources.
Stochastic Generalized Lipschitz Convex Minimization · Lean proof
Stochastic
Generalized Lipschitz Convex Minimization
We consider minimizing a continuous convex function on a separable real
Hilbert space . A given point
satisfies , where and is a global minimizer. At , the oracle returns a random
vector whose mean is a subgradient of . Each reply decomposes into a component
with second moment at most
and a component bounded almost surely in norm by , where and . Samples are independent and
identically distributed. For , the goal is a
measurable output
satisfying with
probability at least .
The optimization problem is Write for the inner
product and for its
induced norm. The algorithm receives , , , , , and ; the objective and sampling
distribution are accessed through the oracle.
Our assumptions:
Assumption 1 (Convexity and initial distance). The
function is continuous, and for
every and , There
exists a fixed such
that
Assumption 2 (Stochastic subgradient oracle). Let
be a measurable space, let
be a probability measure on
, and let be jointly
measurable. For every , the
map is Bochner
integrable under , and At call , a query receives . The random variables are measurable, mutually
independent, and each has law .
Algorithm randomness is independent of this sample sequence.
Assumption 3 (Generalized moment bound). For every
, there exist measurable maps
such that is integrable under
and
After the allotted oracle calls, the algorithm must return a
measurable output
satisfying
where is the joint law of the
algorithm’s randomness and the oracle sample sequence.
Proved result
OracleTemplate.Convergence LongTails.Setups.StochasticGeneralizedLipschitzConvex.spec
LongTails.Theorems.StochasticGeneralizedLipschitzConvex.budget
Relevant previous results
No qualifying prior reference verified; this is not a proof of novelty.