← All setups

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, G-Lipschitz function f:E→R on E=Rm+1, where m≥0 is an integer and G>0. A global minimizer x⋆ satisfies ∥x⋆∥≤R, where R>0. The oracle returns an unbiased subgradient estimate with independent, identically distributed samples and centered sub-Gaussian noise: its variance proxy is vtop along the first coordinate and vrest in orthogonal directions, where 0≤vrest≤vtop. For ε>0, the goal is a measurable output x¯∈E satisfying f(x¯)−f(x⋆)≤ε with probability at least 2/3 over the algorithm and oracle randomness.

The optimization problem is minx∈Ef(x). We use the Euclidean inner product and norm, and index coordinates by 0,…,m. The algorithm receives m, the measurable sample space Ω, and G,R,vtop,vrest,ε; the objective and oracle distribution are accessible only through oracle replies.

Our assumptions:

Assumption 1 (Convexity and Lipschitz continuity). For every x,y∈E and s∈[0,1], f((1−s)x+sy)≤(1−s)f(x)+sf(y),|f(x)−f(y)|≤G∥x−y∥.

Assumption 2 (Bounded minimizer). There exists x⋆∈E such that f(x⋆)≤f(x)for every x∈E,∥x⋆∥≤R.

Assumption 3 (Spiked sub-Gaussian subgradient oracle). There are a probability measure p on Ω, a map v:E→E, and a jointly measurable map g:E×Ω→E. For every x∈E, the map g(x,⋅) is Bochner integrable under p, and Eξ∼p[g(x,ξ)]=v(x),⟨v(x),y−x⟩≤f(y)−f(x)(y∈E). Define the directional variance proxy by V(u)=vrest∥u∥2+(vtop−vrest)u02,u∈E. For every x,u∈E and t∈R, the random variable exp⁡(t⟨g(x,ξ)−v(x),u⟩) is integrable under ξ∼p and satisfies Eξ∼p[exp⁡(t⟨g(x,ξ)−v(x),u⟩)]≤exp⁡(t2V(u)2). The sample sequence (ξk)k≥0 has a probability law Q on ΩN under which its coordinate maps are measurable, mutually independent, and each has distribution p. At call k, a query x∈E receives g(x,ξk). The algorithm’s randomness is independent of this sample sequence.

Queries may be made anywhere in E. After the allotted oracle calls, the output x¯ must be measurable and satisfy P(f(x¯)−f(x⋆)>ε)≤13, where P is the joint law of the algorithm’s randomness and the oracle sample sequence.

Proved result

⌈251⋅(m+1+(vTop+m⋅vRest)⋅R2ε2)⋅(1+log⁡(16⋅(m+1)⋅(1+G⋅Rε)))5⌉+

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.