From Optimization to Generalization under Heavy-Tailed Data: The Role of Gradient Clipping

Gradient clipping is widely used to stabilize stochastic gradient methods and is often theoretically motivated by heavy-tailed gradient noise, where even second moments may be infinite, seemingly contradicting the finite-sum ERM setting, where all empirical moments are finite once the dataset is fixed. We resolve this paradox by explicitly separating data sampling from optimization randomness: although moments are finite conditional on the dataset, heavy-tailed data induce dataset-dependent noise whose second moment typically grows with the dataset size $N$. In particular, when $\|\nabla f(x_\star,\xi)\|$ has tail index $\alpha \in (1,2)$, the quantity $\frac{1}{N}\sum_{i=1}^N\|\nabla f(x_\star,\xi_i)\|^2$ scales as $N^{\frac{2}{\alpha}-1}$, leading to deteriorating convergence guarantees for standard SGD as $N$ increases. In contrast, we show that SGD with clipping avoids this growth and admits finite-sum convergence guarantees under heavy-tailed data for broad step-size and clipping schedules. We further derive generalization bounds for strongly convex smooth objectives and show that the tail behavior of gradients at the population minimizer is the key quantity linking optimization and generalization under heavy-tailed data.

Machine learning models are often trained using stochastic gradient descent (SGD), where updates are computed from randomly selected data samples. In many real-world applications, some samples produce unusually large gradients, creating so-called heavy-tailed noise that can destabilize training. A widely used practical solution is gradient clipping, which limits the size of updates, but its benefits in finite-dataset settings have remained poorly understood. This paper shows that heavy-tailed data can make optimization increasingly difficult as datasets grow larger, because larger datasets are more likely to contain extreme samples that dominate the training dynamics. We prove that standard SGD can suffer from this effect, while gradient clipping prevents such deterioration and maintains favorable convergence guarantees. We also derive new generalization bounds and show that the behavior of gradients near the optimal solution plays a central role in both optimization and generalization. These results provide a theoretical explanation for the effectiveness of gradient clipping in modern large-scale machine learning.