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

We study optimizing $L$-smooth and $\mu$-Polyak–Łojasiewicz (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 $ϵ$-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.