← All setups

Covariance-Bounded Convex Minimization

Descriptions may be stale. Consult the linked Lean sources.

Covariance-Bounded Convex Minimization

We consider minimizing a convex, L-Lipschitz function f:Rd→R, where d≥1 and L>0. A global minimizer x⋆ satisfies ∥x⋆∥≤R, where R>0 and ∥⋅∥ is the Euclidean norm. The oracle returns an unbiased stochastic subgradient using independent, identically distributed samples, with noise variance at most σ2/d in every unit direction, where σ≥0. For ε>0, the goal is a measurable output x¯ satisfying f(x¯)−f(x⋆)≤ε with probability at least 2/3 under P, the joint law of the oracle samples and independent algorithm randomness.

The optimization problem is minx∈Rdf(x). Write ⟨⋅,⋅⟩ for the Euclidean inner product. The algorithm receives d∈N≥1, L>0, R>0, σ≥0, ε>0, and the measurable sample space Ω.

Our assumptions:

Assumption 1 (Convexity and Lipschitz continuity). For every x,y∈Rd and t∈[0,1], f((1−t)x+ty)≤(1−t)f(x)+tf(y),|f(x)−f(y)|≤L∥x−y∥.

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

Assumption 3 (Stochastic subgradients and covariance). There exist a probability measure p on Ω, a map v:Rd→Rd, and a jointly measurable map g:Rd×Ω→Rd. For every x∈Rd, the map g(x,⋅) is Bochner integrable under p, and ∥g(x,⋅)−v(x)∥2 is integrable under p. For all x,y,u∈Rd, Eξ∼p[g(x,ξ)]=v(x),⟨v(x),y−x⟩≤f(y)−f(x),Eξ∼p[⟨g(x,ξ)−v(x),u⟩2]≤σ2d∥u∥2. At call k≥0, a query x∈Rd receives g(x,ξk). The sample variables (ξk)k≥0 are measurable, mutually independent, and each has law p. The algorithm’s randomness is independent of the entire sample sequence.

Queries may be made at any point of Rd. After the allotted oracle calls, the output x¯∈Rd must be measurable and satisfy P(f(x¯)−f(x⋆)>ε)≤13.

Results

Convex, globally L-Lipschitz f:Rd→R has a minimizer x⋆ with ∥x⋆∥≤R; d≥1, L,R,ε>0, σ≥0. IID samples have law p under probability measure P. The jointly measurable oracle is integrable, with ∫g(x,ω)dp=v(x)∈∂f(x), integrable squared noise, and ∫⟨g(x,ω)−v(x),u⟩2dp≤σ2∥u∥2/d. Target: measurable x^ with P{f(x^)−f(x⋆)>ε}≤1/3.

Comparison for CovarianceBoundedConvex.
Result Oracle complexity Novelty Limitations
(1) CovarianceSoftCutConvex (Ours) (⋆⋆⋆) (review) O((d+σ2R2/ε2)ℓ5)
(2) (Marsden et al. 2025, Cor. 3, v1); special case: directional exponential tails O((d+σ2R2/ε2)polylog(d,1+LR/ε)) (1): directional second moments replace exponential tails; includes finite-variance noise without third moments. Matches polynomial rate on the exponential-tail subclass. (1): explicit ℓ5 overhead may be larger.
(3) (Marsden et al. 2025, Cor. 4, v1); trace-bounded noise O((d+dσ2R2/ε2)polylog(d,1+LR/ε)) (1): noise term σ2R2/ε2 instead of dσ2R2/ε2, up to logarithms; material when σ2R2/ε2≳1 and d≫ℓ5. (1) needs directional covariance bound; trace bound alone is insufficient. Anisotropic covariance C requires σ2≥d∥C∥op.
(4) SGD (Marsden et al. 2025, secs. 1, v1); expected-gap bound plus Markov O(1+(L2+σ2)R2/ε2) (1): deterministic term dℓ5 instead of L2R2/ε2; total gain when (d+σ2R2/ε2)ℓ5≪L2R2/ε2. (1): noise logarithms, directional covariance restriction, exact centroids; worse when d≳L2R2/ε2.

Abbr: ℓ=1+log⁡(d(1+LR/ε)); costs count all stochastic subgradient calls. polylog denotes the unspecified logarithmic factors in the cited corollaries, at fixed success probability. In (2), for unit u, p{|⟨g−v,u⟩|≥t}≤2e−td/σ (covariance scale at most 2σ). C denotes noise covariance. Exact centroid arithmetic in (1) is uncharged.

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

Lean setup