← All setups

Small Relative Error Convex Minimization

Descriptions may be stale. Consult the linked Lean sources.

Small Relative Error Convex Minimization

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 lies within distance R≥0 of a global minimizer x⋆. At x, the oracle returns a vector g satisfying ∥g−∇f(x)∥≤α∥∇f(x)∥, where 0≤α<1 and α≤exp⁡(−8(1+log⁡(2+LR2/ε)))/100. For ε>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 ε.

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 oracle error). Queries may be made at any point of E. The relative error bound stated above holds for every query, every finite query–reply history, and every realization of the oracle randomness. The reply may depend on that history, and 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. The minimizer x⋆ is fixed independently of the randomness.

Results

On a real Hilbert space, f is differentiable and satisfies 0≤f(y)−f(x)−⟨∇f(x),y−x⟩≤L∥y−x∥2/2. A minimizer x⋆ satisfies ∥x0−x⋆∥≤R, with L>0, R≥0, ε>0. Every oracle reply obeys ∥g−∇f(x)∥≤α∥∇f(x)∥, where 0≤α≤e−8(1+log⁡(2+LR2/ε))/100. The target is f(xout)−f(x⋆)≤ε for every admissible reply sequence. The setup supplies L,α,R,ε,x0 and imposes no algorithm restriction.

Relative-error convex optimization: RecursiveRelativeErrorSmoothConvex.
Result Oracle complexity Novelty Limitations
(1) RecursiveRelativeErrorConvex (Ours) (⋆⋆) (review) O(2+TH(T))
(2) Damped acceleration (Accelerated Convex Minimization Under Relative Gradient Error, Without Logarithms 2026)

O(1+T1−α+α2T1−α)

0≤α<1.

(1): For α=T−c, 0<c<1/4, eventually O(T1/2+o(1)) instead of O(T1−2c); near-accelerated tolerance becomes subpolynomial. (1) requires vanishing α; enormous overhead. At the setup cap, the crossover needs log⁡(2+T)≳8.2⋅105.

(3) Regularized RE-AGM (Vasin and Gasnikov 2026, Thm. 9.3)

Finite-dimensional restriction.

O((T+αT)(1+log⁡T))

T≥1, 0<α≤1/9; largest admissible τ.

(1): At the setup’s error cap, O(T1/2+o(1)) instead of O(T1−o(1)), as T→∞. (1) needs the smaller error cap; much larger constants. At that cap, the crossover requires log⁡(2+T)≳7.8⋅105.

(4) ISTM (Kornilov et al. 2023, Thm. 3.1, p=2)

Finite-dimensional, small-error restriction.

O(1+T+α1/3T2/3+αT)

Requires α2T≲1 with a sufficiently small constant.

(1): Scope: certifies accuracy for T−1/2≪α≤e−8(1+log⁡(2+T))/100, beyond (4)’s certified α2LR2 accuracy floor. On the overlap, (4) costs O(1+T); (1) loses H(T)=To(1) and has enormous constants.
(5) Derived bound: two-level scheme (Accelerated Convex Minimization Under Relative Gradient Error, Without Logarithms 2026, “Tightness,” proposition)

O((α−2+T+α4T)⋅log⁡(2+T/α2))

T≥1, 0<α≤1/27; counts all inner calls.

(1): For α=T−c, 0<c<1/8, eventually O(T1/2+o(1)) instead of O(T1−4clog⁡T); recursively preserves relative envelope error. (1) requires vanishing α and incurs enormous overhead; (5) allows every fixed 0<α≤1/27.

Abbr: T=LR2/ε; H(T)=(32+log⁡(2+T))32(1+log⁡(2+T)); g is a relative-error gradient reply. Costs count primitive gradient-oracle calls, including all recursive inner calls. Logs are natural; o(1) is as T→∞; ≲ suppresses a universal factor.

Accelerated Convex Minimization Under Relative Gradient Error, Without Logarithms. 2026. LongTails repository mathematical note. https://github.com/k3nfalt/longtails/blob/main/LongTails/Theorems/AcceleratedRelativeErrorConvex.md.
Kornilov, Nikita, Eduard Gorbunov, Mohammad Alkousa, Fedor Stonyakin, Pavel Dvurechensky, and Alexander Gasnikov. 2023. Intermediate Gradient Methods with Relative Inexactness. arXiv:2310.00506v1. https://doi.org/10.48550/arXiv.2310.00506.
Vasin, Artem, and Alexander Gasnikov. 2026. Lower and Upper Bounds of the Convergence Rate of Gradient Methods with Composite Noise in Gradient. arXiv:2603.12376v1. https://doi.org/10.48550/arXiv.2603.12376.

Lean setup