Heavy-Tailed SGD under the PL Condition
Descriptions may be stale. Consult the linked Lean sources.
Heavy-Tailed SGD under the PL Condition
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
initialization). The function
Assumption 3 (Independent sampling and noise
moments). Let
Our result is algorithm-specific: we analyze scheduled stochastic
gradient descent (SGD). Starting from the given
Results
A differentiable, bounded-below
| Result | Oracle complexity | Novelty | Limitations |
|---|---|---|---|
| (1) HeavyTailedPLLastIterate
(Ours) |
|||
(2) Clipped-SGD (Sadiev et al. 2023,
Thm. E.4, Finite-dimensional competitor; finite variance suffices locally. |
(1): for fixed
positive Adaptivity: steps need only |
(1) needs global
assumptions and |
|
(3) SGD (Madden et al. 2024, Thm. 8) Special case: conditionally norm-sub-Gaussian noise in |
Derived bound retaining initialization; here |
(1): scope extends
plain SGD to one finite Noise term: |
(1) requires IID sampling
and uniform-in- |
(4) SGD (Tong et al. 2026, Thm. 3.7) Finite-data empirical risk in |
Requires smooth component losses, bounded initial component
gradients, and |
(1): removes finite-data
and trajectory-cap restrictions; needs one moment instead of all
moments. On the overlap, fixed |
(1) requires
uniform-in- |
Abbr: