← All setups

Sharp Relative-Error Convex Optimization

Descriptions may be stale. Consult the linked Lean sources.

Sharp Relative-Error Convex Optimization

We consider minimizing a differentiable convex function f:E→R on a real Hilbert space E. The function is L-smooth, with L>0, and a given point x0∈E is within distance R≥0 of a global minimizer x⋆. At x∈E, the oracle returns a vector g∈E satisfying ∥g−∇f(x)∥≤α∥∇f(x)∥, where α≥0 obeys a stringent accuracy-dependent bound. For tolerance ε>0, the goal is an output x¯∈E satisfying f(x¯)−f(x⋆)≤ε almost surely under P, the joint law of algorithm and oracle randomness.

The optimization problem is minx∈Ef(x). The norm ∥⋅∥ is induced by the inner product on E. The algorithm receives E, L, x0, α, R, and ε. The parameters satisfy L>0,R≥0,ε>0,0≤α<1,α≤1100[33(1+log⁡(2+LR2/ε))]12, where log denotes the natural logarithm.

Our assumptions:

Assumption 1 (Convexity and smoothness). The function f is Fréchet differentiable everywhere on E. For every x,y∈E, f(y)≥f(x)+⟨∇f(x),y−x⟩,f(y)≤f(x)+⟨∇f(x),y−x⟩+L2∥y−x∥2.

Assumption 2 (Initial distance). There exists x⋆∈E such that f(x⋆)≤f(x)for every x∈E,∥x0−x⋆∥≤R.

Assumption 3 (Uniform relative error). Queries may be made at any point of E. The relative-error inequality stated above holds for every query history, every query point, and every realization of the oracle randomness. Oracle replies may depend on the preceding queries and replies, and the oracle randomness may be dependent across calls. Algorithm randomness is independent of oracle randomness.

After the allotted oracle calls, the output must satisfy f(x¯)−f(x⋆)≤εP-a.s. Here x⋆ is a fixed global minimizer, independent of the randomness.

Results

Convex differentiable f on a real Hilbert space satisfies f(y)≤f(x)+⟨∇f(x),y−x⟩+L2∥y−x∥2, with L>0 and a minimizer x⋆ satisfying ∥x0−x⋆∥≤R, R≥0. Every oracle reply obeys ∥g−∇f(x)∥≤α∥∇f(x)∥, with 0≤α≤α⋆=[100(33(1+log⁡(2+LR2/ε)))12]−1. Target: f(xout)−f(x⋆)≤ε, ε>0, for every admissible reply sequence. The setup imposes no algorithm restriction.

Comparison for SharpRelativeErrorSmoothConvex.
Result Oracle complexity Novelty Limitations
(1) PolylogPrecisionRelativeErrorConvex (Ours) (⋆⋆) (review) O((2+T)5/8(1+ℓ)20)
(2) Regularized acceleration (Vasin and Gasnikov 2026, Theorem 9.3) O((T+αT)(1+log⁡T))
T≥1, 0<α≤1/9; Euclidean space.
(1): At α=α⋆, exponent 1−o(1)→5/8; smaller stated budget only for log⁡T≳837. Adaptivity: no knowledge of α. (1) requires α≤α⋆; much larger constant. At α=α⋆, larger budget below the crossover; smaller α delays it.
(3) Damped acceleration (LongTails 2026a) O(1+T1−α+α2T1−α)
Every 0≤α<1.
(1): At α=α⋆, O(T/log24⁡T)→O(T5/8log20⁡T), with stated-budget crossover log⁡T≳1273. No knowledge of α. (1) requires α≤α⋆; much larger constant. Worse roughly when α≲1016T−3/16(log⁡T)10 for large T.
(4) Recursive envelopes (LongTails 2026c) O(2+T⋅(32+ℓ)32(1+ℓ))
Requires α≤e−8(1+ℓ)/100.
(1): Scope extends to e−8(1+ℓ)/100<α≤α⋆ when nonempty. On overlap, smaller stated budget for log⁡T≲1.8⋅107. (1) has exponent 5/8 instead of 1/2+o(1); larger budget on overlap for log⁡T≳1.8⋅107.
(5) NearAcceleratedPolylogPrecisionRelativeErrorConvex (Ours) (⋆⋆) (review) O(s16(1+log⁡(33s))(2+T)1/2+q)
s=1+ℓ, q=log⁡(16384(1+log⁡(33s)))32log⁡(32s).
N denotes its explicit public budget; q<0.089, q→0.
(6) Regularized acceleration (Vasin and Gasnikov 2026, Theorem 7.2); Euclidean space O((T+αT)(1+log⁡T)); T>1, 0≤α≤1/3, optimally tuned exponent. (5): At α=α⋆, T1−o(1)→T1/2+o(1); smaller explicit budget for log⁡T≳606. Updates need no α. (5) requires α≤α⋆; much larger constant (about 7⋅1028). Larger budget below that crossover; smaller α delays it.
(7) Damped acceleration (LongTails 2026a) O(1+T1−α+α2T1−α); 0≤α<1. (5): At α=α⋆, T/log24⁡T→T1/2+o(1); smaller explicit budget for log⁡T≳935. Updates need no α. (5) requires α≤α⋆; larger constants and worse cost when α≲N/T.
(8) Recursive envelopes (LongTails 2026c) O(2+T(32+ℓ)32(1+ℓ)); requires α≤e−8(1+ℓ)/100. (5): Scope extends to relative errors between this threshold and α⋆, when nonempty. On overlap, smaller explicit budget for log⁡T≲1.7⋅109. (5) is asymptotically worse on the overlap; crossover near log⁡T=1.7⋅109.
(9) Same-setup predecessor (LongTails 2026b); guarantee of (1) O((2+T)5/8(1+ℓ)20). (5): Uniformly smaller explicit budget; exponent 5/8→1/2+q<0.589. At log⁡T=100, log10⁡N falls from 98.5 to 85.6.

Abbr: T=LR2/ε; ℓ=log⁡(2+T); log is natural. Costs count physical inexact-gradient calls, including all inner solves. α⋆ is the threshold above. Crossovers compare explicit budgets before suppressing universal constants.

LongTails: AcceleratedRelativeErrorConvex. 2026a. Repository convergence theorem and oracle budget. https://github.com/k3nfalt/longtails/blob/main/LongTails/Theorems/AcceleratedRelativeErrorConvex.lean.
LongTails: PolylogPrecisionRelativeErrorConvex. 2026b. Repository convergence theorem and oracle budget. https://github.com/k3nfalt/longtails/blob/main/LongTails/Theorems/PolylogPrecisionRelativeErrorConvex.lean.
LongTails: RecursiveRelativeErrorConvex. 2026c. Repository convergence theorem and oracle budget. https://github.com/k3nfalt/longtails/blob/main/LongTails/Theorems/RecursiveRelativeErrorConvex.lean.
Vasin, Artem, and Alexander Gasnikov. 2026. Lower and Upper Bounds of the Convergence Rate of Gradient Methods with Composite Noise in Gradient. https://doi.org/10.48550/arXiv.2603.12376.

Lean setup