Heavy-Tailed Polyak–Łojasiewicz Minimization
Descriptions may be stale. Consult the linked Lean sources.
Heavy-Tailed Polyak–Łojasiewicz Minimization
We consider minimizing a possibly nonconvex function
The optimization problem is
Our assumptions:
Assumption 1 (Gradient and Hessian regularity). The
function
Assumption 2 (Polyak–Łojasiewicz inequality and
initialization). There exists
Assumption 3 (Unbiased oracle with heavy-tailed
noise). There is a probability measure
Queries may be made at any point of
Results
Finite-dimensional real inner-product space;
| Result | Oracle complexity | Novelty | Limitations |
|---|---|---|---|
| (1) KappaFreeHeavyTailedPLHessian
(Ours) |
|||
| (2) (Ou and Wang 2026), Thm. 4.3 | (1): statistical |
(1) needs Hessian
regularity and |
|
| (3) (Ou and Wang 2026),
Thm. D.1(i); |
(1):
dimension-independent scope; matches the |
(1) adds Hessian
regularity, a |
|
| (4) (Ou and Wang 2026),
Thm. D.1(ii); fixed |
(1):
dimension-independent constants; removes statistical |
(1) needs Hessian
regularity; adds a |
|
| (5) R-clipped-SSTM (Sadiev et al. 2023), Thm. 3.3; strongly convex restriction | (1): scope extends from strong convexity to PL with non-isolated minimizers. | (1) loses accelerated
initialization and high-probability accuracy; adds Hessian regularity,
|
|
| (6) (LongTails, n.d.);
|
(1) removes fourth-moment
requirement, permits |
(1) worsens the Hessian
term when |
Abbr: Costs count stochastic-gradient calls.