← All setups

Convex Minimization with Relative Errors

Descriptions may be stale. Consult the linked Lean sources.

Convex Minimization with Relative Errors

We consider minimizing a continuously differentiable convex function f:E→R on a real Hilbert space E. The function f is (L0,L1)-smooth, with L0>0 and L1≥0. A given point x0∈E has distance at most R>0 and objective gap at most Δ>0 from a global minimizer x⋆. At x, the oracle returns g∈E with ∥g−∇f(x)∥≤α∥∇f(x)∥, where 0≤α≤1/100; replies may depend on the query history. For ε>0, the goal is 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, L0, L1, R, Δ, x0, α, and ε.

Our assumptions:

Assumption 1 (Convexity and differentiability). The function f is Fréchet differentiable everywhere on E, its gradient ∇f:E→E is continuous, and f((1−t)x+ty)≤(1−t)f(x)+tf(y),x,y∈E,t∈[0,1].

Assumption 2 (Generalized smoothness). For every x,y∈E and M∈R satisfying ∥∇f(x+θ(y−x))∥≤Mfor all θ∈[0,1], we have ∥∇f(x)−∇f(y)∥≤(L0+L1M)∥x−y∥.

Assumption 3 (Initial distance and objective gap). There exists x⋆∈E such that f(x⋆)≤f(x)for every x∈E,∥x0−x⋆∥≤R,f(x0)−f(x⋆)≤Δ.

Assumption 4 (Relative oracle error). Queries may be made at any x∈E. For every finite query–reply history h and every realization z of the oracle randomness used for the reply, the returned vector g(h,x,z)∈E satisfies ∥g(h,x,z)−∇f(x)∥≤α∥∇f(x)∥. The oracle randomness may be dependent across calls and is independent of the algorithm’s randomness.

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

Results

Convex differentiable f on a real Hilbert space has continuous gradient and satisfies ∥∇f(x)−∇f(y)∥≤(L0+L1M)∥x−y∥ whenever ∥∇f∥≤M on [x,y]. A minimizer x⋆ satisfies ∥x0−x⋆∥≤R and f(x0)−f(x⋆)≤Δ; L0,R,Δ,ε>0, L1≥0. Every possibly history-dependent reply obeys ∥v−∇f(x)∥≤α∥∇f(x)∥, 0≤α≤1/100. Target: f(xN)−f(x⋆)≤ε on every oracle path.

Relative-error acceleration under generalized smoothness: RelativeGeneralizedSmoothConvex.
Result Oracle complexity Novelty Limitations
(1) RelativeErrorGeneralizedAcceleration (Ours) (⋆⋆⋆) (review) O(L0R2/ε+α2L0R2/ε+(1+L1R)ℓ+α2(L1R)2ℓ2) relative-gradient replies.
(2) (Tyurin 2026), Thm. 4.3 O(1+L0R2/ε+L1Rlog(1+min{L12ΔL0,Δε})+log(1+ΔL0R2)) exact-gradient calls. Special case: α=0, finite-dimensional Hessian-form class; R=∥x0−x⋆∥. (1): Scope extends exact gradients to adversarial relative errors. Matches the leading L0R2/ε term at α=0. (1): Larger logarithmic transient; at fixed L0,L1,R,Δ, it grows with log⁡(1/ε). Needs ball projection.
(3) (LongTails, n.d.), GeneralizedAcceleratedConvex O(1+L0R2/ε+(1+(L1R)2/3)log⁡(1+Δ/ε)) exact-gradient calls, ε<Δ. Special case: α=0, Hessian-form class. (1): Scope extends exact gradients to relative errors, allowing biased, history-dependent replies. (1): At α=0, worse large-L1R transient: L1R instead of (L1R)2/3, with different logarithms.
(4) (Vasin et al. 2026), Remark 3.1, convex guarantee O(1+L0R2(1−α)ε+α2L0R2(1−α)ε) relative-gradient calls. Special case: L1=0, α<1. (1): Scope permits unbounded curvature with polynomial L1R dependence. At L1=0, matches the polynomial accuracy terms for α≤1/100. (1): Requires α≤1/100; adds ℓ at L1=0 and needs Δ in addition.
(5) Normalized GD (Kovalev and Stonyakin 2026), Thm. 3.1 O(1+L12+L0/ε) direction replies; best-iterate guarantee. Finite-dimensional setting, R=∥x0−x⋆∥, β^=R, with sufficient tolerance δ≤cmin{1RL1,ε/L0R,11+L1+L0/ε}. (1): Fixed relative-error tolerance and last-iterate accuracy. Rates are not comparable: (5) requires direction tolerance shrinking with ε. (1): Needs gradient magnitudes and Δ; (5) uses directions alone.

Abbr: ℓ=1+log⁡(1+L0R2/ε+L1R+Δ/(L0R2)). Hessian-form class: twice differentiable f with ∥∇2f(x)∥≤L0+L1∥∇f(x)∥. In (5), ∥g~∥=1, ∥g~−∇f/∥∇f∥∥≤δ; c>0 is a sufficiently small universal constant, and 1/L1=+∞ when L1=0.

Kovalev, Evgeniy, and Fedor Stonyakin. 2026. Normalized First-Order Methods for (Quasi)-Convex (L0,L1)-Smooth Optimization with Inexact Gradients. https://doi.org/10.48550/arXiv.2607.26969.
LongTails: GeneralizedAcceleratedConvex. n.d. Repository theorem and public oracle budget. https://github.com/k3nfalt/longtails/blob/main/LongTails/Theorems/GeneralizedAcceleratedConvex.lean.
Tyurin, Alexander. 2026. Near-Optimal Convergence of Accelerated Gradient Methods Under Generalized and (L0,L1)-Smoothness. https://doi.org/10.48550/arXiv.2508.06884.
Vasin, Artem, Alexander Tyurin, and Alexander Gasnikov. 2026. Adaptive First-Order Methods with Composite Gradient Error. https://doi.org/10.48550/arXiv.2610.24863.

Lean setup