← All setups

Convex Minimization with Distance-Dependent Subgradient Moments

Descriptions may be stale. Consult the linked Lean sources.

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

Results

Let X⊆Rd be closed and convex, f measurable and convex on X, and x0,x⋆∈X with x⋆ minimizing f on X and ∥x0−x⋆∥≤R. Each call returns an exact projection onto X or a jointly measurable sample g(x,ξ) with fresh IID noise. On X, Eg(x,ξ)∈∂Xf(x) and E∥g(x,ξ)∥2≤G2+B2∥x−x0∥2. Given x0, B,G≥0, R,ε>0, and 0<δ<1, return a feasible x^ with Pr{f(x^)−f(x⋆)>ε}≤δ.

Sufficient oracle budgets for convex minimization with distance-growing subgradient moments.
Result Oracle complexity Novelty Limitations
(1) DistanceGrowingSubgradientUpperBound (Ours) (review) 0 if GR≤ε, otherwise O(R2(G2+B2R2)ℓ/ε2)
(2) Derived bound (Parletta et al. 2024, Thm. 2(iii), Cor. 1) O(R2(G2+B2R2)ℓ/ε2) (1) formalizes the matched rate. On K, the second moment is at most v. Use confidence parameter min{δ,2/e} in (2).
(3) Derived bound (Liu and Zhou 2023, Thm. 3) O(R2vℓ2/ε2) (1) reduces ℓ2 to ℓ against (3) localized to K with known horizon and variance bound v.
(4) Derived bound (Alacaoglu et al. 2026, Cor. 3.4) O(R2v/(ε2δ2)) by Markov’s inequality, tuning with max{B,G/R} (1) gives a direct high-probability guarantee. The confidence factor drops from δ−2 for the expected-gap conversion in (4) to ℓ. (1) uses R for the ball projection. When BR≥G, the updates in (4) need only B.
(5) Last-iterate clipping (LongTails 2026) O(1+(BR2+G2/B)2ℓ2ε2), B,G>0 (1) saves a factor ℓ for the shared objective-gap target and allows B=0 or G=0. For 0<BR≪G, O(R2G2ℓ/ε2) replaces O(G4ℓ2/(B2ε2)). (1) guarantees accuracy for a uniform average. (5) guarantees it for the last iterate.

Abbr: v=G2+B2R2, ℓ=1+log⁡(1/δ), K=X∩{x:∥x−x0∥≤R}. Cost counts sampled subgradients and projections onto X. Rate comparisons use GR>ε.

Alacaoglu, Ahmet, Yura Malitsky, and Stephen J. Wright. 2026. Towards Weaker Variance Assumptions for Stochastic Optimization. https://doi.org/10.48550/arXiv.2504.09951.
Liu, Zijian, and Zhengyuan Zhou. 2023. Stochastic Nonsmooth Convex Optimization with Heavy-Tailed Noises: High-Probability Bound, in-Expectation Rate and Initial Distance Adaptation. https://doi.org/10.48550/arXiv.2303.12277.
LongTails. 2026. ClippedBgLastIterate. Lean theorem and oracle budget. https://github.com/k3nfalt/longtails/blob/32aa9399511f9a11ecffb74ca284d8229bfd80c0/LongTails/Theorems/ClippedBgLastIterate.lean.
Parletta, Daniela Angela, Andrea Paudice, Massimiliano Pontil, and Saverio Salzo. 2024. “High Probability Bounds for Stochastic Subgradient Schemes with Heavy Tailed Noise.” SIAM Journal on Mathematics of Data Science 6 (4): 953–77. https://doi.org/10.1137/22M1536558.

Lean setup