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

Abstract

We study smooth Polyak--Łojasiewicz (PL) optimization with conditionally unbiased stochastic gradients satisfying \[ \mathbb E\!\left[ \|G_t-\nabla f(x_t)\|^α\mid\mathcal F_{t-1} \right]\le σ^α, \qquad 1<α\le2. \] When the dimension may depend on the oracle budget, we prove the noise-adaptive lower bound \[ T_ε= Ω_α\!\left[ κ\log\frac{Δ_0}ε + κ\left( \frac{σ^2}{με} \right)^{\fracα{2(α-1)}} \right], \] 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 \[ \widetildeΘ_α\!\left[ \left( \frac{σ^2}{με} \right)^{\fracα{2(α-1)}} \right]. \] For every fixed $d>3$, the same characterization holds whenever \[ \fracα{α-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.

60 pages