← All setups

Distance Growing Subgradient Upper Bound — Convex Minimization with Distance-Dependent Subgradient Moments

Descriptions may be stale. Consult the linked Lean sources.

Convex Minimization with Distance-Dependent Subgradient Moments · Lean proof

Convex Minimization with Distance-Dependent Subgradient Moments

We minimize a real-valued function f that is convex on a closed convex set C in d-dimensional Euclidean space. A given x0∈C lies within distance R>0 of a minimizer x⋆ on C. The oracle returns either an exact projection onto C or a random vector drawn using a fresh independent sample. At each x∈C, this vector has a subgradient mean relative to C and second moment at most B2∥x−x0∥2+G2, where B,G≥0. For ε>0 and 0<δ<1, the goal is a measurable output x¯∈C satisfying f(x¯)−f(x⋆)≤ε with probability at least 1−δ.

The optimization problem is minx∈Cf(x). The algorithm receives the dimension d∈{0,1,2,…}, the starting point x0, and the parameters B,G,R,ε,δ. Both query types accept any point in Rd and share a single call budget.

Our assumptions:

Assumption 1 (Convexity and initial distance). The function f:Rd→R is Borel measurable. On the closed convex set C⊆Rd, it satisfies f((1−t)x+ty)≤(1−t)f(x)+tf(y) for every x,y∈C and t∈[0,1]. The point x0 belongs to C, and there exists x⋆∈argminx∈Cf(x) such that ∥x0−x⋆∥≤R.

Assumption 2 (Subgradient mean and second moment). Let (ξk)k≥0 be independent measurable samples with common law ν on a measurable space Ω, independent of the algorithm’s randomness. A subgradient query at x on call k returns g(x,ξk), where g:Rd×Ω→Rd is jointly measurable. For each x∈C and ξ∼ν, the vector g(x,ξ) is Bochner integrable and ∥g(x,ξ)∥2 is integrable. Writing m(x)=Eξ∼ν[g(x,ξ)], we require f(y)≥f(x)+⟨m(x),y−x⟩(y∈C),Eξ∼ν[∥g(x,ξ)∥2]≤B2∥x−x0∥2+G2.

A projection query at z∈Rd returns the Euclidean projection ΠC(z). This map is measurable, takes values in C, and satisfies ⟨z−ΠC(z),u−ΠC(z)⟩≤0(u∈C). After the allotted calls, the output x¯ must be measurable and belong to C for every realization. Under the joint law P of the samples and the algorithm’s randomness, it must satisfy P(f(x¯)−f(x⋆)>ε)≤δ.

Proved result

{0G⋅R≤ε2⋅⌈1024⋅R2⋅(G2+B2⋅R2)⋅log⁡(8δ)ε2⌉+otherwise

OracleTemplate.Convergence LongTails.Setups.DistanceGrowingSubgradient.spec
  LongTails.Theorems.DistanceGrowingSubgradientUpperBound.budget

Relevant previous results

  • Yair Carmon and Oliver Hinder. The Price of Adaptivity in Stochastic Convex Optimization. 2024 (COLT, full proof in arXiv v1). Complexity: O(R2MR2log⁡(2/δ)/ε2) total oracle calls for averaged clipped SGD when 0<ε<GR, with one stochastic subgradient and one projection onto KR=domain∩B―(x0,R) per step. Here MR=G2+B2R2 bounds the root second moment at every query in KR.
  • Daniela Angela Parletta, Andrea Paudice, Massimiliano Pontil, and Saverio Salzo. High Probability Bounds for Stochastic Subgradient Schemes with Heavy Tailed Noise. 2024 (journal version, first preprint 2022). Complexity: O(R2MR2log⁡(2/δ)/ε2) total oracle calls for the averaged clipped projected subgradient method on KR when 0<ε<GR, with one stochastic subgradient and one projection onto KR per step. The diameter is at most 2R, and MR bounds both the Lipschitz constant on KR and the oracle standard deviation there.