An Improved Analysis of the Clipped Stochastic subGradient Method under Heavy-Tailed Noise

Daniela A. Parletta, Andrea Paudice, Saverio SalzoarXiv 2024 · DOI · arXiv

TL;DR

This paper provides the first optimal convergence rates for the last iterate of the Clipped Stochastic subGradient Method (C-SsGM) when dealing with heavy-tailed noise. By refining the mathematical analysis, the authors "shave off" unnecessary logarithmic factors from previous state-of-the-art results and demonstrate that clipping isn't just a heuristic—it’s a theoretically sound way to achieve robust performance in modern, outlier-prone machine learning.

What Problem Does This Paper Address?

Standard Stochastic Gradient Descent (SGD) is the workhorse of machine learning, but its theoretical guarantees usually rely on a big assumption: that the noise in our gradient estimates is "light-tailed" (specifically, that it has a bounded variance).

In the real world—especially with massive, messy datasets—noise is often heavy-tailed. This means outliers are common, and the variance might even be infinite. In these cases, standard SGD can fail to converge or behave erratically. To fix this, researchers use clipping, where they cap the magnitude of the gradient if it exceeds a certain threshold.

While clipping is popular in practice (e.g., in training Deep Learning models), we lacked a tight theoretical understanding of the last iterate—the final model weights you actually use. Most existing proofs only covered the average of all weights produced during training, which practitioners rarely use because it's computationally expensive and often performs worse.

Methods

The authors analyze the Clipped Stochastic subGradient Method (C-SsGM). The core idea is simple: at each step, take your noisy subgradient estimate and "clip" it so its norm doesn't exceed a threshold $\lambda$.

The paper introduces several key technical innovations:

  • Bias Management: Clipping introduces a "bias" because you aren't moving exactly in the direction of the true gradient. The authors developed a new "unrolling" technique for recursive inequalities to handle this bias, even when the optimization happens over an infinitely large (unbounded) space.
  • Parameter Schedules: They provide specific rules for how to tune the step size ($\gamma$) and the clipping threshold ($\lambda$) for two scenarios: Finite-Horizon (when you know exactly how many steps you will take) and Anytime (when the algorithm might run indefinitely).
  • Kernelization: They show that C-SsGM can be "kernelized," allowing it to work in infinite-dimensional Hilbert spaces, which is crucial for non-linear supervised learning.

Datasets

The paper focuses primarily on theoretical proofs, but it validates the theory using:

  • Synthetic Heavy-Tailed Data: A minimization problem ($f(x) = \|x\|_1$) in 100 dimensions subjected to Pareto noise. Pareto noise is a classic "heavy-tailed" distribution where you can specifically tune the "shape" to ensure only the first $p$ moments exist.
  • Supervised Learning Framework: The authors apply their results to kernel-based learning, though the "experiments" section focuses on the synthetic Pareto noise setup to clearly demonstrate the failure of standard methods vs. the success of clipping.

Key Insights and Ideas

  • The "Last Iterate" Gap is Closed: For the first time, we have optimal convergence rates for the last iterate under heavy-tailed noise. For a fixed number of steps $k$, the error drops at a rate of $1/k^{(p-1)/p}$.
  • Shaving the Logs: Previous research on the average iterate included extra logarithmic factors (like $\log^2 k$). This paper proves those factors aren't necessary, improving the rate by a factor of roughly $\log^{(2p-1)/p} k$.
  • Robustness to Outliers: The results show that as long as the noise has some structure (specifically, a bounded $p$-th moment where $1 < p \le 2$), clipping allows the algorithm to ignore massive outliers that would otherwise derail standard SGD.
  • Anytime vs. Finite Horizon: The authors found that if you don't know your "budget" of steps in advance (Anytime), you pay a small penalty—a factor of $(\log^{1/p} k)$.

Key Results

The quantitative improvements are significant, as shown in their experimental comparison:

  • Accuracy: In the heavy-tailed Pareto noise test ($p=1.1$), standard SGD had an average error of 5.767. The clipped version (C-SsGM) achieved an error of 0.003.
  • Convergence Rates:
    • Last Iterate (Finite Horizon): $O(1/k^{(p-1)/p})$ — this is proven to be optimal.
  • Last Iterate (Anytime): $O((\log^{1/p} k)/k^{(p-1)/p})$.
  • Average Iterate: Improved high-probability bounds that match the expectation bounds up to a simple $\log(1/\delta)$ factor.

Limitations and Future Work

  • The Anytime Penalty: The authors note it is still an "interesting open question" whether the extra $\log^{1/p} k$ factor in the anytime setting is actually necessary or just a limitation of the current proof technique.
  • High Probability for Last Iterate: While they provide high-probability bounds for the average iterate, doing the same for the last iterate under heavy-tailed noise remains an open challenge.
  • Constants: The theoretical constants in the last-iterate bound grow very quickly as $p$ approaches 1 (the "heaviest" tail). Finding ways to tighten these constants would make the theory even more practical.

Summary updated

Abstract

In this paper, we provide novel optimal (or near optimal) convergence rates for a clipped version of the stochastic subgradient method. We consider nonsmooth convex problems over possibly unbounded domains, under heavy-tailed noise that possesses only the first $p$ moments for $p \in \left]1,2\right]$. For the last iterate, we establish convergence in expectation for the objective values with rates of order $(\log^{1/p} k)/k^{(p-1)/p}$ and $1/k^{(p-1)/p}$, for anytime and finite-horizon respectively. We also derive new convergence rates, in expectation and with high probability, for the objective values along the average iterates--improving existing results by a $\log^{(2p-1)/p} k$ factor. Those results are applied to the problem of supervised learning with kernels demonstrating the effectiveness of our theory. Finally, we give preliminary experiments.
BibTeX
@misc{parletta2024improved,
  author = {Daniela A. Parletta and Andrea Paudice and Saverio Salzo},
  title = {{An Improved Analysis of the Clipped Stochastic subGradient Method under Heavy-Tailed Noise}},
  year = {2024},
  eprint = {2410.00573},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2410.00573},
}
Figure