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

Weiming Ou, Xiao Wang

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} \…