PL Minimization with Relative Discrepancy
Descriptions may be stale. Consult the linked Lean sources.
PL Minimization with Relative Discrepancy
We consider minimizing a differentiable, possibly nonconvex function
The optimization problem is
Our assumptions:
Assumption 1 (Smoothness). The function
Assumption 2 (Polyak–Łojasiewicz condition and
initial gap). There exists
Assumption 3 (Relative discrepancy). The oracle is
specified by a fixed sequence of maps
Queries may be made at any point of
Results
On a real Hilbert space,
| Result | Oracle complexity | Novelty | Limitations |
|---|---|---|---|
| (1) DiscrepancyBatchedGD (Ours) (review) | |||
| (2) Derived bound: fixed-step GD (Puchinin and Stonyakin 2023), §3, (9)–(11) | (1): Matches known rate;
Lean formalization on Hilbert spaces. The inner-product argument of
(2) extends from |
||
| (3) Exact GD (Karimi et al.
2020), Thm. 2.1; |
(1): Matches known rate
at |
(1): Larger leading
iteration constant at |
|
| (4) Derived bound: RE-AGM
(Vasin et al.
2025), Thm. 4; strongly convex, |
(1): Scope: PL without
strong convexity. On (4)'s restriction, |
On (4)'s restriction,
|
Abbr: