← All setups

Distance Growing Subgradient Lower Bound — Convex Interpolation with Distance-Growing Subgradients

Descriptions may be stale. Consult the linked Lean sources.

Convex Interpolation with Distance-Growing Subgradients · Lean proof

Convex Interpolation with Distance-Growing Subgradients

We minimize an expected loss f on Euclidean space Rd of dimension d≥2. The smooth convex sample losses share a minimizer x⋆ and have the same gradient at the given starting point x0. The oracle returns a sample gradient using a fresh independent draw, or the query point itself for a projection query. The gradient’s second moment is bounded by an affine function of squared distance from x0. For tolerance ε>0 and failure probability δ∈(0,1/8], the goal is a measurable output x¯ satisfying f(x¯)−f(x⋆)≤ε with probability at least 1−δ.

The optimization problem is minx∈Rdf(x). The algorithm receives d,x0,B,G,R,ε,δ, where B≥0 and G>0 control the second moment, R>0 bounds the initial distance to a common minimizer, and 65536ε≤GR. At call k=0,1,…, the oracle uses a sample Zk from a sequence of independent, identically distributed random variables with law ν on a measurable space Z. The sequence is independent of the algorithm’s randomness.

Our assumptions:

Assumption 1 (Interpolating sample losses). For each k and z∈Z, the loss ℓk,z:Rd→R is convex and C∞. There exist x⋆,g0∈Rd with ∥x0−x⋆∥≤R such that, for every k and z, ℓk,z(x⋆)=minx∈Rdℓk,z(x),∇ℓk,z(x0)=g0. For every k and x, ℓk,Zk(x) is integrable and the measurable convex objective satisfies f(x)=E[ℓk,Zk(x)]. In particular, x⋆ minimizes f.

Assumption 2 (Distance-dependent second moment). The subgradient reply at x on call k is g(x,Zk), where g:Rd×Z→Rd is jointly measurable and g(x,z)=∇ℓk,z(x) for every k,x,z. For each x and Z∼ν, the vector g(x,Z) is Bochner integrable and ∥g(x,Z)∥2 is integrable. For all x,y∈Rd, f(x)−f(y)≤⟨E[g(x,Z)],x−y⟩,E[∥g(x,Z)∥2]≤B2∥x−x0∥2+G2.

Both query types accept any x∈Rd and count toward the same call budget. After the allotted calls, the output x¯ must be a measurable Rd-valued random variable satisfying P(f(x¯)−f(x⋆)≤ε)≥1−δ, where P is the joint law of the algorithm’s randomness and the oracle samples.

Proved result

⌊−(R2⋅(G2+B2⋅R2)⋅log⁡(δ))228⋅ε2⌋+

OracleTemplate.NonConvergence LongTails.Setups.InterpolatedDistanceGrowingSubgradient.spec
  LongTails.Theorems.DistanceGrowingSubgradientLowerBound.budget

Relevant previous results

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