← All setups

Convex Interpolation with Distance-Growing Subgradients

Descriptions may be stale. Consult the linked Lean sources.

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.

Results

On Rd, d≥2, the convex C∞ sample losses have mean f, share a minimizer u with ∥x0−u∥≤R, and have identical gradients at x0. With IID samples, the jointly measurable sample gradient g(x) satisfies Eg(x)∈∂f(x) and E∥g(x)∥2≤G2+B2∥x−x0∥2 for every x. Here G,R>0, B≥0, 0<ε≤GR/65536, and 0<δ≤1/8. The target for any randomized adaptive algorithm is Pr[f(x^)−f(u)>ε]≤δ on every instance.

Necessary oracle budgets for interpolating convex losses with distance-growing gradient moments.
Result Oracle complexity Novelty Limitations
(1) DistanceGrowingSubgradientLowerBound (Ours) (⋆⋆⋆) (review)

Lower bound on total calls

Ω(R2(G2+B2R2)ε2log⁡1δ)

(2) (Carmon and Hinder 2024), Prop. 1, §3.3

Lower bound for G-Lipschitz samples (B=0)

Ω(G2R2ε2log⁡1δ)

(1): Distance growth adds a necessary factor 1+(BR/G)2, unbounded for BR≫G. For BR≲G, the order matches (2) even with interpolation and identical initial gradients. (1) requires d≥2, ε≤GR/65536, δ≤1/8. Its hard instances have sample smoothness of order (G2+B2R2)/ε. (2) allows access to entire sample losses.

Abbr: Each sample-gradient or identity-projection query counts as one call in (1). In (2), the budget counts independent samples.

Carmon, Yair, and Oliver Hinder. 2024. “The Price of Adaptivity in Stochastic Convex Optimization.” Proceedings of Thirty Seventh Conference on Learning Theory, Proceedings of machine learning research, vol. 247: 772–74. https://doi.org/10.48550/arXiv.2402.10898.

Lean setup