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
The optimization problem is
Our assumptions:
Assumption 1 (Convexity and differentiability). The
function
Assumption 2 (Generalized smoothness). For every
Assumption 3 (Initial distance and objective gap).
There exists
Assumption 4 (Relative oracle error). Queries may be
made at any
After the allotted oracle calls, the output
Results
Convex differentiable
| Result | Oracle complexity | Novelty | Limitations |
|---|---|---|---|
| (1) RelativeErrorGeneralizedAcceleration
(Ours) |
|||
| (2) (Tyurin 2026), Thm. 4.3 | (1): Scope extends exact
gradients to adversarial relative errors. Matches the leading |
(1): Larger logarithmic
transient; at fixed |
|
| (3) (LongTails, n.d.), GeneralizedAcceleratedConvex | (1): Scope extends exact gradients to relative errors, allowing biased, history-dependent replies. | (1): At |
|
| (4) (Vasin et al. 2026), Remark 3.1, convex guarantee | (1): Scope permits
unbounded curvature with polynomial |
(1): Requires |
|
| (5) Normalized GD (Kovalev and Stonyakin 2026), Thm. 3.1 | (1): Fixed relative-error
tolerance and last-iterate accuracy. Rates are not comparable:
(5) requires direction tolerance shrinking with |
(1): Needs gradient
magnitudes and |
Abbr: