← All setups

Convex Minimization with Spiked Noise

Descriptions may be stale. Consult the linked Lean sources.

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.

Results

Convex, globally G-Lipschitz f:Rd→R has a global minimizer ∥x⋆∥≤R; G,R,ε>0. Fresh IID samples from a probability measure p feed a jointly measurable, integrable oracle g, with ∫g(x,ω)dp=v(x)∈∂f(x). For every x,u,t, the exponential moment is integrable and at most exp⁡(t2[vrest∥u∥2+(vtop−vrest)u02]/2) for ⟨g−v,u⟩, where 0≤vrest≤vtop and the spike direction is known. Target: measurable x^ with P{f(x^)−f(x⋆)>ε}≤1/3.

Comparison for SpikedSubGaussianConvex.
Result Oracle complexity Novelty Limitations
(1) SpikedSubGaussianSoftCutConvex (Ours) (⋆⋆) (review) O((d+τR2/ε2)ℓ5)
(2) ESGO cutting planes (Marsden et al. 2025), Cor. 3 O((d+dvtopR2/ε2)ℓO(1)) (1): noise coefficient τ instead of dvtop; gain up to d when anisotropy dominates logarithms. For G=R=1, ε=vtop=d−1, vrest=d−3: O(dlog5⁡d) versus O(d2logO(1)⁡d). (1) needs a known spike and sub-Gaussian MGF; (2) allows directional sub-exponential tails. Isotropic noise gives no polynomial gain.
(3) SGD, derived probability bound (Marsden et al. 2025), §1 O(1+(G2+τ)R2/ε2) (1) removes G2R2/ε2, adding dℓ5; wins if G2R2/ε2≫max{d,τR2/ε2}ℓ5. In (2)’s example: O(dlog5⁡d) versus O(d2). (1) requires known-spike sub-Gaussian noise; (3) needs only finite variance and avoids ℓ5. (3) is cheaper when G2R2/ε2≲d.

Abbr: d=m+1, τ=vtop+(d−1)vrest, ℓ=1+log⁡(d(1+GR/ε)). Costs count individual stochastic subgradient calls, including batches. ℓO(1) denotes the polylogarithmic factors suppressed in the cited bound. ESGO: sub-exponential stochastic gradient oracle, here with scale σE≍dvtop. SGD: stochastic gradient descent; its expected-error bound uses E∥g∥2≤G2+τ, converted by Markov’s inequality.

Marsden, Annie, Liam O’Carroll, Aaron Sidford, and Chenyi Zhang. 2025. Isotropic Noise in Stochastic and Quantum Convex Optimization. https://doi.org/10.48550/arXiv.2510.20745.

Lean setup