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
The optimization problem is
Our assumptions:
Assumption 1 (Convexity and smoothness). The
function
Assumption 2 (Initial distance). There exists
Assumption 3 (Uniform relative oracle error).
Queries may be made at any point of
After the allotted oracle calls, the output must satisfy
Results
On a real Hilbert space,
| Result | Oracle complexity | Novelty | Limitations |
|---|---|---|---|
| (1) RecursiveRelativeErrorConvex
(Ours) |
|||
| (2) Damped acceleration (Accelerated Convex Minimization Under Relative Gradient Error, Without Logarithms 2026) | (1): For |
(1) requires vanishing
|
|
(3) Regularized RE-AGM (Vasin and Gasnikov 2026, Thm. 9.3) Finite-dimensional restriction. |
(1): At the setup’s error
cap, |
(1) needs the smaller
error cap; much larger constants. At that cap, the crossover requires
|
|
(4) ISTM (Kornilov et al. 2023,
Thm. 3.1, Finite-dimensional, small-error restriction. |
Requires |
(1): Scope: certifies
accuracy for |
On the overlap, (4) costs
|
| (5) Derived bound: two-level scheme (Accelerated Convex Minimization Under Relative Gradient Error, Without Logarithms 2026, “Tightness,” proposition) | (1): For |
(1) requires vanishing
|
Abbr: