Tight Heavy-Tailed Complexity Bounds for Optimizing Polyak--Łojasiewicz Objectives

Weiming Ou, Xiao Wang

We study optimizing $L$-smooth and $\mu$-Polyak-Lojasiewicz (PL) objectives with unbiased stochastic gradients under $\alpha$-heavy-tailed noise ($1<\alpha \le 2$). In the unrestricted high-dim…