Smooth Polyak–Łojasiewicz Minimization
Descriptions may be stale. Consult the linked Lean sources.
Smooth Polyak–Łojasiewicz Minimization
We consider minimizing a differentiable, possibly nonconvex function
The optimization problem is
Our assumptions:
Assumption 1 (Smoothness). The function
Assumption 2 (Polyak–Łojasiewicz inequality and
initial gap). There exists
Queries may be made at any point of
Results
On a real Hilbert space,
| Result | Oracle complexity | Novelty | Limitations |
|---|---|---|---|
| (1) GdPL (Ours) (review) | |||
| (2) GD (Karimi et al. 2016, Theorem 1, arXiv v4) | (1): Matches known rate
for |
(1): Explicit stopping
budget needs a known |
|
| (3) Lower bound (Yue et al. 2023, Theorems 2–3, arXiv v2) | (1): Matches (3) up to constants in this regime. A problem-class lower bound, not a competing algorithm; randomized methods are not covered. |
Abbr: GD: gradient descent; PL: Polyak–Łojasiewicz;