Heavy-Tailed First-Order Optimization for Polyak-Łojasiewicz Condition: High-Dimensional Minimax Bounds, High-Probability Guarantee, and Fixed-Dimensional Improvements

We study smooth Polyak–Łojasiewicz (PL) optimization with conditionally unbiased stochastic gradients satisfying $$\mathbb{E}\text{\hspace{0.17em}⁣}[\mathrm{\parallel }{G}_t-\mathrm{\nabla }f(x_t){\mathrm{\parallel }}^{\alpha }\mid {\mathcal{F}}_{t-1}]\le {\sigma }^{\alpha },1<\alpha \le 2.$$ When the dimension may depend on the oracle budget, we prove the noise-adaptive lower bound $$T_{\epsilon }={\mathrm{\Omega }}_{\alpha }\text{\hspace{0.17em}⁣}[\kappa \log \frac{{\mathrm{\Delta }}_0}{\epsilon }+\kappa {\left(\frac{{\sigma }^2}{\mu \epsilon }\right)}^{\frac{\alpha }{2(\alpha -1)}}],$$ which recovers the noiseless PL lower bound when $\sigma =0$. Under the appropriate mirror-PL condition, we give a centered-clipped mirror-descent method attaining the matching high-probability upper bound up to logarithmic factors, without bounded-domain, bounded-gradient, or sub-Gaussian assumptions. We further characterize the stochastic complexity in prescribed fixed dimensions. For $d=1,2,3$, the optimal stochastic term is $${\tilde{\mathrm{\Theta }}}_{\alpha }\text{\hspace{0.17em}⁣}\left[{\left(\frac{{\sigma }^2}{\mu \epsilon }\right)}^{\frac{\alpha }{2(\alpha -1)}}\right]\mathrm{.}$$ For every fixed $d>3$, the same characterization holds whenever $$\frac{\alpha }{\alpha -1}\ge d-1.$$ In the complementary regime, we provide an upper bound with an additional surface-entropy factor and explicitly identify the remaining gap.