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

Abstract

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-dimensional setting, we establish the noise-adaptive lower bound for attaining $\epsilon$-suboptimal function value. Under the generalized mirror-PL condition, we propose a centered-clipped mirror-descent method that achieves a high-probability upper bound matching the lower bound up to logarithmic factors. We further provide the improved tight stochastic complexity in fixed dimensions.

arXiv commentUnder review