← All setups

Convex Minimization with Relative Error

Descriptions may be stale. Consult the linked Lean sources.

Convex Minimization with Relative Error

We consider minimizing a differentiable convex function f:E→R on a real Hilbert space E. The function admits a quadratic upper model with curvature L>0, and a given starting 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. 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). Write ⟨⋅,⋅⟩ for the inner product on E and ∥⋅∥ for its induced norm. 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(x)+⟨∇f(x),y−x⟩≤f(y),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 (Relative oracle error). Queries may be made at any point of E. For every finite query–reply history h, every query x∈E, and every realization s of the oracle randomness used for that reply, the returned vector g(h,x,s)∈E satisfies ∥g(h,x,s)−∇f(x)∥≤α∥∇f(x)∥. Oracle randomness may be dependent across calls, and replies may depend on the history. The algorithm’s randomness is independent of the oracle randomness.

After the allotted oracle calls, the output must satisfy f(x¯)−f(x⋆)≤εP-a.s.

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, a minimizer x⋆, and ∥x0−x⋆∥≤R, R≥0. Every oracle reply satisfies ∥g−∇f(x)∥≤α∥∇f(x)∥, 0≤α<1, for every call and seed. Target: f(xN)−f(x⋆)≤ε, ε>0, almost surely under the execution measure (indeed, for every seed). Parameters L,α,R,ε are supplied.

Relative gradient error: RelativeErrorSmoothConvex.
Result Oracle complexity Novelty Limitations
(1) AcceleratedRelativeErrorConvex (Ours) (⋆⋆⋆) (review) O(1+T1−α+α2T1−α)
(2) Regularized RE-AGM (Vasin and Gasnikov 2026, Thm. 7.2) O((T+αT)(1+log⁡T)). T>1, α≤1/3; Euclidean space. (1): α2T instead of αT; removes logarithm on T>1, α≤1/3. At α=T−1/4, T≥81: O(T3/4(1+log⁡T))→O(T). Scope: every α<1.
(3) Regularized GD (Vasin and Gasnikov 2026, Thm. 7.1) O((1+α)2(1−α)6T(1+log⁡T)). T>1, α<1/2; Euclidean space. (1): O(T+α2T) on T>1, α<1/2; logarithmic saving throughout. For α≤T−1/4: O(T(1+log⁡T))→O(T). Scope: every α<1.
(4) ISTM, p=2 (Kornilov et al. 2023, Thm. 3.1) O(1+T) when α≤cmin{1,T−1/2}; Euclidean space. Certified accuracy floor of order α2LR2. (1): matches O(T) for T>1, α≲T−1/2; extends acceleration to α≲T−1/4 with α≤1/3. Arbitrary accuracy for every α<1.

Abbr: T=LR2/ε; complexity counts relative-error gradient calls; c>0 is a sufficiently small universal constant; ≲ suppresses a universal constant. GD: gradient descent; RE-AGM: relative-error accelerated gradient method; ISTM: intermediate similar triangle method.

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