← All setups

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 f:E→R on a separable real Hilbert space E. A given point x0∈E satisfies ∥x0−x⋆∥≤R, where R>0 and x⋆ is a global minimizer. At x∈E, the oracle returns a random vector whose mean is a subgradient of f. Each reply decomposes into a component with second moment at most G02 and a component bounded almost surely in norm by G1(f(x)−f(x⋆)), where G0>0 and G1≥0. Samples are independent and identically distributed. For ε>0, the goal is a measurable output x¯∈E satisfying f(x¯)−f(x⋆)≤ε with probability at least 9/10.

The optimization problem is minx∈Ef(x). Write ⟨⋅,⋅⟩ for the inner product and ∥⋅∥ for its induced norm. The algorithm receives E, x0, R, G0, G1, and ε; the objective and sampling distribution are accessed through the oracle.

Our assumptions:

Assumption 1 (Convexity and initial distance). The function f is continuous, and for every x,y∈E and t∈[0,1], f((1−t)x+ty)≤(1−t)f(x)+tf(y). There exists a fixed x⋆∈E such that f(x⋆)≤f(x)for every x∈E,∥x0−x⋆∥≤R.

Assumption 2 (Stochastic subgradient oracle). Let Ω be a measurable space, let ν be a probability measure on Ω, and let g:E×Ω→E be jointly measurable. For every x∈E, the map g(x,⋅) is Bochner integrable under ν, and f(x)−f(y)≤⟨Eξ∼ν[g(x,ξ)],x−y⟩,x,y∈E. At call k=0,1,…, a query x∈E receives g(x,ξk). The random variables (ξk)k≥0 are measurable, mutually independent, and each has law ν. Algorithm randomness is independent of this sample sequence.

Assumption 3 (Generalized moment bound). For every x∈E, there exist measurable maps ux,vx:Ω→E such that ∥ux(⋅)∥2 is integrable under ν and g(x,ξ)=ux(ξ)+vx(ξ)ν-a.s.,Eξ∼ν[∥ux(ξ)∥2]≤G02,∥vx(ξ)∥≤G1(f(x)−f(x⋆))ν-a.s.

After the allotted oracle calls, the algorithm must return a measurable output x¯∈E satisfying P(f(x¯)−f(x⋆)>ε)≤110, where P is the joint law of the algorithm’s randomness and the oracle sample sequence.

Proved result

⌈266⋅((1+R⋅G1)3+(1+R⋅G1)2⋅R⋅G0ε+(R⋅G0ε)2)⋅(1+log⁡(2+R⋅G1+R⋅G0ε))3⌉+

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.