← All setups

Accelerated Relative Error Convex — Convex Minimization with Relative Error

Descriptions may be stale. Consult the linked Lean sources.

Convex Minimization with Relative Error · Lean proof

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.

Proved result

⌈7⋅L⋅R2(1−α)⋅ε+11⋅α2⋅L⋅R2(1−α)⋅ε⌉+

OracleTemplate.Convergence LongTails.Setups.RelativeErrorSmoothConvex.spec OracleTemplate.RelativeErrorConvex.budget

Relevant previous results

  • Nikita Kornilov, Eduard Gorbunov, Mohammad Alkousa, Fedor Stonyakin, Pavel Dvurechensky, Alexander Gasnikov. Intermediate Gradient Methods with Relative Inexactness. 2023 (preprint v1; published 2025). Complexity: O(1+max{LR2/ε,α1/3(LR2/ε)2/3,αLR2/ε}) fixed relative-error gradient oracle calls for f(yN)−f∗≤ε, provided ε≥Cα2LR2, with sufficiently large universal C; Intermediate Similar Triangle Method with p=2.