← All setups

Covariance-Controlled Smooth Convex Minimization

Descriptions may be stale. Consult the linked Lean sources.

Covariance-Controlled Smooth Convex Minimization

We minimize a differentiable convex function f:E→R on a finite-dimensional real Hilbert space E. Its gradient is L-Lipschitz, with L>0, and a given point x0∈E is within distance R≥0 of a minimizer x⋆. At x, the oracle returns an unbiased gradient estimate g(x,ξ) using independent samples ξ from a probability law p. The noise has second moment bounded by σ2 and covariance bounded by s2 times the identity, where 0≤s≤σ. For ε>0 and δ∈(0,1), the goal is a measurable output x¯∈E with P{f(x¯)−f(x⋆)>ε}≤δ, where P is the law of all algorithm and oracle randomness.

The optimization problem is minx∈Ef(x). Write ⟨⋅,⋅⟩ for the inner product on E and ∥⋅∥ for its induced norm. The algorithm receives E, the measurable sample space Ω, x0, L, R, σ, s, ε, and δ.

Our assumptions:

Assumption 1 (Convexity and smoothness). The function f is Fréchet differentiable everywhere on E. For every x,y∈E and t∈[0,1], f((1−t)x+ty)≤(1−t)f(x)+tf(y),∥∇f(x)−∇f(y)∥≤L∥x−y∥.

Assumption 2 (Initial distance). There exists x⋆∈E such that f(x⋆)≤f(x)for every x∈E,∥x0−x⋆∥≤R.

Assumption 3 (Stochastic gradient and covariance). There are a probability measure p on Ω and a jointly measurable map g:E×Ω→E. For every x∈E, the random vector g(x,ξ) is Bochner integrable and ∥g(x,ξ)−∇f(x)∥2 is integrable under ξ∼p. For every x,v∈E, Eξ∼p[g(x,ξ)]=∇f(x),Eξ∼p[∥g(x,ξ)−∇f(x)∥2]≤σ2,Eξ∼p[⟨v,g(x,ξ)−∇f(x)⟩2]≤s2∥v∥2. At call k=0,1,…, a query x∈E receives the reply 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 E. After the allotted oracle calls, the output x¯ must be measurable and satisfy P{f(x¯)−f(x⋆)>ε}≤δ.

Results

Convex differentiable f on a finite-dimensional real Hilbert space, with L-Lipschitz gradient and an unconstrained minimizer x⋆ satisfying ∥x0−x⋆∥≤R. Fresh IID samples supply a jointly measurable, integrable unbiased gradient g(x,ξ); its squared centered norm is integrable, with E∥g−∇f∥2≤σ2 and E⟨v,g−∇f⟩2≤s2∥v∥2 for every x,v. Here L,ε>0, R≥0, 0≤s≤σ, 0<δ<1; parameters are supplied. Target: measurable x^ with P{f(x^)−f(x⋆)>ε}≤δ.

Comparison for CovarianceSmoothConvex.
Result Oracle complexity Novelty Limitations
(1) CovarianceAcceleratedHighProbability (Ours) (⋆⋆⋆) (review) O(ℓX2+LR2/εℓX+R2(σ2+s2ℓ)/ε2)
(2) Clipped accelerated SMD (Nguyen et al. 2023), Thm. 4.1, p=2 O(1+ℓ[LR2/ε+R2σ2/ε2]) (1): Statistical cost σ2ℓ→σ2+s2ℓ; up to ℓ gain when noise dominates and s2ℓ≪σ2. For L=R=1, σ=d−1, s=d−3/2, δ=e−d, ε=d−4: O(d6) versus O(d7). (1): Deterministic logarithm ℓX instead of ℓ, plus ℓX2 overhead; needs s additionally. Exponential grid and exact Gaussian integration make implementation impractical.
(3) Derived bound (Zhang et al. 2026), Thm. 2.2, p=2, on B(x0,R) O(1+L2R4/ε2+LR2ℓ/ε+R2(σ2+s2ℓ)/ε2)
0<δ<1/10, 0<s≤σ; Lipschitz bound G=2LR.
(1): Matches statistical term; deterministic (LR2/ε)2→LR2/εℓX+ℓX2. Polynomial total gain is possible when L2R2≳σ2+s2ℓ. For L=R=1, σ=d−1, s=d−3/2, δ=e−d, ε=d−4: O(d6) versus O(d8). (1): Requires smoothness and second moments; does not cover nonsmooth objectives or moment orders 1<p<2.
(4) Clipped SGD (Das et al. 2024), Thm. 3 O(1+LR2/ε+R2[σ2+s(σ+LR)hε]/ε2)
As ε↓0 with other parameters fixed, s>0, 0<δ<1/2; horizon N≥log⁡log⁡d. Requires fixed Σ(x)⪯Σ, trΣ≤σ2, ∥Σ∥≤s2.
(1): Scope: pointwise variance bounds suffice without a common covariance envelope. On the overlap, acceleration and confidence coefficient s2 replace s(σ+LR); removes mixed sLR term. (1): Computationally impractical, versus a streaming clipped-gradient implementation.

Abbr: Costs count all raw stochastic-gradient calls. ℓ=1+log⁡(1/δ), X=1+LR2/ε+R2σ2/ε2, ℓX=1+log⁡(X/δ), hε=1+log⁡((1+log⁡X)/δ); d=dim⁡E. Σ(x) denotes noise covariance. In (4), the asymptotic bound absorbs lower-order terms at fixed remaining parameters; it is not uniform in them.

Das, Aniket, Dheeraj Nagaraj, Soumyabrata Pal, Arun Sai Suggala, and Prateek Varshney. 2024. Near-Optimal Streaming Heavy-Tailed Statistical Estimation with Clipped SGD. https://doi.org/10.48550/arXiv.2410.20135.
Nguyen, Ta Duy, Alina Ene, and Huy L. Nguyen. 2023. Improved Convergence in High Probability of Clipped Gradient Methods with Heavy Tails. https://doi.org/10.48550/arXiv.2304.01119.
Zhang, Haihan, Wendao Wu, Chenheng Zhang, et al. 2026. Sharp High-Probability Statistical Rates for Heavy-Tailed Nonsmooth Convex Optimization. https://doi.org/10.48550/arXiv.2610.00260.

Lean setup