Sharp Relative-Error Convex Optimization
Descriptions may be stale. Consult the linked Lean sources.
Sharp Relative-Error Convex Optimization
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 error). Queries may
be made at any point of
After the allotted oracle calls, the output must satisfy
Results
- Near Accelerated Polylog Precision Relative Error Convex · Lean proof
- Polylog Precision Relative Error Convex · Lean proof
Convex differentiable
| Result | Oracle complexity | Novelty | Limitations |
|---|---|---|---|
| (1) PolylogPrecisionRelativeErrorConvex
(Ours) |
|||
| (2) Regularized acceleration (Vasin and Gasnikov 2026, Theorem 9.3) | (1): At |
(1) requires |
|
| (3) Damped acceleration (LongTails 2026a) | Every |
(1): At |
(1) requires |
| (4) Recursive envelopes (LongTails 2026c) | Requires |
(1): Scope extends to
|
(1) has exponent |
| (5) NearAcceleratedPolylogPrecisionRelativeErrorConvex
(Ours) |
|||
| (6) Regularized acceleration (Vasin and Gasnikov 2026, Theorem 7.2); Euclidean space | (5): At |
(5) requires |
|
| (7) Damped acceleration (LongTails 2026a) | (5): At |
(5) requires |
|
| (8) Recursive envelopes (LongTails 2026c) | (5): Scope extends to
relative errors between this threshold and |
(5) is asymptotically
worse on the overlap; crossover near |
|
| (9) Same-setup predecessor (LongTails 2026b); guarantee of (1) | (5): Uniformly smaller
explicit budget; exponent |
Abbr: