Vanilla SGD with Momentum Survives Heavy-Tailed Noise: Convergence Analysis without Gradient Clipping or Normalization

Jul 16, 2026

Stochastic gradient descent (SGD) is analyzed for its ability to converge under heavy-tailed noise without relying on gradient clipping or gradient normalization. The study refines convergence results for vanilla SGD and provides a comprehensive first analysis for vanilla SGD with momentum across strongly convex, convex, and nonconvex objectives. Under only heavy-tailed noise assumptions (bounded p-th moments), derived rates are shown to be inferior to clipped or normalized SGD, exposing intrinsic limitations of unmodified methods. Experiments on synthetic functions support the theory.

LanguageEnglish

CategoryResearch & Report

FormatPDF

Pages31

Reading Time1 h 18 min

Introduction

Problem setting and noise assumptions

Related work and motivation

Comparison of convergence rates

Vanilla SGD with Momentum Survives Heavy-Tailed Noise: Convergence Analysis without Gradient Clipping or Normalization Ryusei Yamada 1 * Naoki Sato 1 * Hideaki Iiduka 1 1Meiji University, Japan *Equal contribution arXiv :2607 .08 104v 1 [ cs .LG] 9 Jul 2026 Abstract Stochastic gradient descent (SGD) is a cornerstone of modern optimization. While its performance under heavy-tailed noise is often addressed through specialized modifications such as gradient clipping or normalization, we investigate a more fundamental question: how does vanilla SGD, particularly with momentum, perform in the presence of heavytailed noise? In this paper, we refine existing convergence results for vanilla SGD and, more importantly, provide the first comprehensive convergence analysis of vanilla SGD with momentum for strongly convex, convex, and nonconvex objectives, without employing any gradient control mechanisms. Our results demonstrate that the obtained convergence rates are inferior to the optimal rates achieved by clipped or normalized variants of SGD, thereby revealing inherent limitations of vanilla methods under heavy-tailed noise. The theoretical findings are supported by experiments on synthetic functions. 1 INTRODUCTION This paper considers the following optimization problem: min f (x) := 1 x∈Rd n n X fi (x), i=1 where each fi (i ∈ [n]) is differentiable. We address three fundamental cases where f is strongly convex, convex, or nonconvex. Empirical risk minimization is a paramount objective that lies at the core of machine learning. As primary solvers for this problem, stochastic gradient descent (SGD)[Robbins and Monro, 1951] and its momentum-based variant [Polyak, 1964, Rumelhart et al., 1986] remain the gold standard in contemporary optimization. A standard assump- tion in the convergence analysis of such stochastic algorithms is bounded variance of stochastic noise, specifically, that the second moment of the error between the stochastic and full gradients is bounded. While numerous seminal results [Nemirovski et al., 2009, Rakhlin et al., 2012, Liu et al., 2020] rely on this assumption, recent experimental evidence suggests that stochastic noise in modern deep learning [Simsekli et al., 2019, Battash et al., 2024, Ahn et al., 2024] and reinforcement learning [Garg et al., 2021] often exhibits heavy tails. Consequently, research has shifted focus toward the convergence behavior of algorithms when the bounded variance assumption is violated, specifically, when stochastic noise possesses only bounded p-th moments for p ∈ (1 , 2] . Under this bounded p-th moment assumption, the convergence of vanilla SGD is known to break down [Zhang et al., 2020] . To mitigate this issue, clipped SGD, which scales the gradient magnitude to stay within a predefined threshold, has emerged as a robust alternative. Clipped SGD and its variants have been proven to converge in both expectation [Zhang et al., 2020] and with high probability [Cutkosky and Mehta, 2021, Liu et al., 2023, Sadiev et al., 2023, Nguyen et al., 2023a,b, Liu et al., 2024] . Notably, these studies often incorporate gradient normalization (see Table 1), and it has been widely considered essential to clip or normalize gradients to ensure convergence when noise variance is unbounded. Recently, several studies have begun to challenge this notion by exploring the convergence of SGD (with momentum) without clipping under bounded p-th moment assumptions. Hübler et al. [2025] demonstrated that normalized SGD converges with high probability even without clipping. Liu and Zhou [2025] were the first to establish that normalized SGD with momentum converges in expectation, achieving rates of O 􀀐T − 3pp12 􀀑 when the tail index p is known, and O 􀀐T − ~~ ~~p−2p1 􀀑 when it is unknown. Most recently, Fatkhullinet al. [2025] and He and Lu [2025] proved that vanilla SGD without any normalization or clipping can indeed converge Table 1: Comparison of assumptions, algorithmic

FAQs

What problem does the paper study?

The paper studies the convergence of vanilla stochastic gradient descent, especially with momentum, when stochastic gradients are corrupted by heavy-tailed noise. It considers strongly convex, convex, and nonconvex objectives.

What mechanisms does the paper avoid?

The analysis is performed without gradient clipping and without gradient normalization. The goal is to understand whether momentum can still ensure convergence under heavy-tailed noise without gradient control.

How do the paper’s convergence rates compare to clipped or normalized SGD?

The derived convergence rates for vanilla (unclipped and unnormalized) SGD are shown to be inferior to the optimal rates achieved by clipped or normalized variants. This indicates inherent limitations of vanilla methods under heavy-tailed noise.

Jul 16, 2026

Upload by Genevieve