Power Geometry with Relative Errors
Descriptions may be stale. Consult the linked Lean sources.
Power Geometry with Relative Errors
We consider minimizing a differentiable convex function
The optimization problem is
Our assumptions:
Assumption 1 (Power geometry). The function
Assumption 2 (Convexity and smoothness). The
function
Assumption 3 (Initial distance). There exists
Assumption 4 (Relative-error oracle). Queries may be
made at any point
After the allotted oracle calls, the output
Results
In a finite-dimensional real normed space,
| Result | Oracle complexity | Novelty | Limitations |
|---|---|---|---|
| (1) PowerGeometryRelativeErrorAcceleration
(Ours) |
|||
| (2) (d’Aspremont et al. 2016), Cor. 4.10, §5.1.2 | (1): extends to biased
relative error; matches the exact-gradient rate for fixed |
(1) has larger |
|
| (3) Derived bound: (Vasin and Gasnikov 2026), Thm. 7.2 | (1): dimension-free; for
fixed |
(1) loses at |
|
| (4) SODA (Pethick 2026), Cor. 3.2 | (1): matches the rate on
the exact-gradient overlap; removes |
(1) does not cover additive heavy-tailed noise allowed by (4); the noisy oracle models are incomparable. |
Abbr: