← All setups

Covariance Accelerated High Probability — Covariance-Controlled Smooth Convex Minimization

Descriptions may be stale. Consult the linked Lean sources.

Covariance-Controlled Smooth Convex Minimization · Lean proof

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⋆)>ε}≤δ.

Proved result

⌈240⋅((log⁡(256⋅(1+L⋅R2ε+R2⋅σ2ε2)δ2))2+L⋅R2ε⋅log⁡(256⋅(1+L⋅R2ε+R2⋅σ2ε2)δ2)+R2⋅(σ2+s2⋅log⁡(3δ))ε2)⌉+

OracleTemplate.Convergence LongTails.Setups.CovarianceSmoothConvex.spec
  LongTails.Theorems.CovarianceAcceleratedHighProbability.budget

Relevant previous results

No qualifying prior reference verified; this is not a proof of novelty.