Strong Quasar Minimization with Relative Errors
Descriptions may be stale. Consult the linked Lean sources.
Strong Quasar Minimization with Relative Errors
We consider minimizing a differentiable function
The optimization problem is
Our assumptions:
Assumption 1 (Smoothness). The function
Assumption 2 (Strong quasar-convexity and initial
gap). There exists
Assumption 3 (Relative gradient error). The oracle
returns
After the allotted oracle calls, the output must have an integrable
objective gap under
Results
On a finite-dimensional real Hilbert space with its Borel measurable
structure,
| Result | Oracle complexity | Novelty | Limitations |
|---|---|---|---|
| (1) AcceleratedRelativeQuasar
(Ours) |
|||
| (2) Continuized
acceleration (Wang and Wibisono 2023), Thm. 2;
|
(1): Scope extends to
fixed relative bias. Retains |
(1): Roughly fourfold larger leading constants in the exact-gradient comparison. | |
| (3) Continuized
acceleration (Wang and Wibisono 2023), Cor. 2;
|
(1): Extends to |
(1): Expected accuracy instead of the stated probability guarantee. | |
| (4) Restarted CG (Kuruzov and
Stonyakin 2026), Thm. 3.3; additionally |
(1): On the common exact-gradient, quadratic-growth restriction, removes subspace solves. For nonzero errors, absolute versus relative models make rates noncomparable. | (1): Expected instead of deterministic accuracy. | |
| (5) Inexact acceleration
(AcceleratedInexactStronglyConvex,
n.d.); |
(1): Scope extends to nonconvex strongly quasar-convex objectives; matches polynomial dependence on the strongly convex overlap. | (1): Requires fixed errors rather than call-dependent errors; expected rather than deterministic accuracy. |
Abbr: