Inexact Gradient Strongly Convex Minimization
Descriptions may be stale. Consult the linked Lean sources.
Inexact Gradient Strongly Convex Minimization
We consider minimizing a differentiable,
The optimization problem is
Our assumptions:
Assumption 1 (Smoothness and strong convexity). The
function
Assumption 2 (Inexact gradient oracle). Queries may
be made at any point
Assumption 3 (Initial distance). There exists
After the allotted oracle calls, the output must satisfy
Results
On a real Hilbert space,
| Result | Oracle complexity | Novelty | Limitations |
|---|---|---|---|
| (1) AcceleratedInexactStronglyConvex
(Ours) |
|||
| (2) RE-AGM (Vasin and Gasnikov 2026, Thm. 6.1) | (1): for |
||
| (3) RE-AGM (Vasin et al. 2025, Thm. 4) | (1): matches this rate;
retains it up to |
||
| (4) RE-AGM (Vasin et al. 2025, Thm. 5) | (1): gain |
||
| (5) GD (Vasin and Gasnikov 2026, Thm. 5.2) | (1): for large |
(1) requires strong convexity instead of the PL inequality. | |
| (6) Fast gradient method (Gaucher et al. 2026, Thm. 3.3) | (1): at |
Abbr: