← All setups

Covariance Soft Cut Convex — Covariance-Bounded Convex Minimization

Descriptions may be stale. Consult the linked Lean sources.

Covariance-Bounded Convex Minimization · Lean proof

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.

Proved result

⌈232⋅(d+σ2⋅R2ε2)⋅(1+log⁡(16⋅d⋅(1+L⋅Rε)))5⌉+

OracleTemplate.Convergence LongTails.Setups.CovarianceBoundedConvex.spec
  LongTails.Theorems.CovarianceSoftCutConvex.budget

Relevant previous results

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