Median-of-Means under Structured Heavy-Tailed Noise: High-Probability Bounds for Clipped Stochastic Optimization

Optimization under heavy-tailed stochastic noise remains a major challenge in modern machine learning, where classical moment assumptions often fail to capture realistic gradient distributions. In this work, we revisit robust estimation techniques and provide a systematic analysis of the Median-of-Means (MoM) estimator under a structured noise model that interpolates between a symmetric heavy-tailed distribution with bounded $\beta$-th moment ($\beta \in (0, 1]$) and a mean-zero distribution with bounded $\alpha$-th moment ($\alpha \in (1, 2]$). We derive new upper bounds on the variance and bias of MoM in this setting, thereby extending the applicability of existing results beyond purely symmetric or bounded-moment settings. Building on these properties, we study clipped stochastic optimization methods with MoM gradient estimation and establish high-probability convergence guarantees that hold for general $\beta \in (0, 1]$ and $\alpha \in (1, 2]$. Our bounds match or improve upon prior complexity guarantees while requiring weaker distributional assumptions, and they reveal that bias only affects the final neighborhood of convergence. Overall, this work advances the theoretical foundations for robust stochastic optimization in the presence of extreme gradient noise.