Algorithmic Stability of Stochastic Gradient Descent with Momentum under Heavy-Tailed Noise
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866916594832113664 |
|---|---|
| author | Dang, Thanh Barsbey, Melih Sonet, A K M Rokonuzzaman Gurbuzbalaban, Mert Simsekli, Umut Zhu, Lingjiong |
| author_facet | Dang, Thanh Barsbey, Melih Sonet, A K M Rokonuzzaman Gurbuzbalaban, Mert Simsekli, Umut Zhu, Lingjiong |
| contents | Understanding the generalization properties of optimization algorithms under heavy-tailed noise has gained growing attention. However, the existing theoretical results mainly focus on stochastic gradient descent (SGD) and the analysis of heavy-tailed optimizers beyond SGD is still missing. In this work, we establish generalization bounds for SGD with momentum (SGDm) under heavy-tailed gradient noise. We first consider the continuous-time limit of SGDm, i.e., a Levy-driven stochastic differential equation (SDE), and establish quantitative Wasserstein algorithmic stability bounds for a class of potentially non-convex loss functions. Our bounds reveal a remarkable observation: For quadratic loss functions, we show that SGDm admits a worse generalization bound in the presence of heavy-tailed noise, indicating that the interaction of momentum and heavy tails can be harmful for generalization. We then extend our analysis to discrete-time and develop a uniform-in-time discretization error bound, which, to our knowledge, is the first result of its kind for SDEs with degenerate noise. This result shows that, with appropriately chosen step-sizes, the discrete dynamics retain the generalization properties of the limiting SDE. We illustrate our theory on both synthetic quadratic problems and neural networks. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2502_00885 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Algorithmic Stability of Stochastic Gradient Descent with Momentum under Heavy-Tailed Noise Dang, Thanh Barsbey, Melih Sonet, A K M Rokonuzzaman Gurbuzbalaban, Mert Simsekli, Umut Zhu, Lingjiong Machine Learning Optimization and Control Probability Understanding the generalization properties of optimization algorithms under heavy-tailed noise has gained growing attention. However, the existing theoretical results mainly focus on stochastic gradient descent (SGD) and the analysis of heavy-tailed optimizers beyond SGD is still missing. In this work, we establish generalization bounds for SGD with momentum (SGDm) under heavy-tailed gradient noise. We first consider the continuous-time limit of SGDm, i.e., a Levy-driven stochastic differential equation (SDE), and establish quantitative Wasserstein algorithmic stability bounds for a class of potentially non-convex loss functions. Our bounds reveal a remarkable observation: For quadratic loss functions, we show that SGDm admits a worse generalization bound in the presence of heavy-tailed noise, indicating that the interaction of momentum and heavy tails can be harmful for generalization. We then extend our analysis to discrete-time and develop a uniform-in-time discretization error bound, which, to our knowledge, is the first result of its kind for SDEs with degenerate noise. This result shows that, with appropriately chosen step-sizes, the discrete dynamics retain the generalization properties of the limiting SDE. We illustrate our theory on both synthetic quadratic problems and neural networks. |
| title | Algorithmic Stability of Stochastic Gradient Descent with Momentum under Heavy-Tailed Noise |
| topic | Machine Learning Optimization and Control Probability |
| url | https://arxiv.org/abs/2502.00885 |