Stochastic Nonsmooth Convex Optimization with Heavy-Tailed Noises

Zijian Liu, Zhengyuan ZhouarXiv 2023 · arXiv · OpenReview

Abstract

Recently, several studies have considered the stochastic optimization problem in a heavy-tailed noise regime, where the difference between the stochastic gradient and the true gradient is assumed to have a finite $p$-th moment ($p \in (1,2]$). This generalizes the traditional finite variance assumption ($p=2$) and reflects phenomena observed in several practical tasks. While progress has been made for smooth objectives, the nonsmooth case remains poorly understood. This paper fills this gap by providing a comprehensive analysis of stochastic nonsmooth convex optimization with heavy-tailed noises. We revisit a simple clipping-based algorithm and establish the first high-probability rates for both convex and strongly convex functions. Our results are optimal (or nearly optimal) with respect to the time horizon $T$ and include parameter-free variants that do not require prior knowledge of the noise level $\sigma$.

1. Introduction

Stochastic Gradient Descent (SGD) is the standard approach for large-scale optimization. However, traditional convergence analysis relies heavily on the assumption that the stochastic gradient noise has finite variance. In modern machine learning applications—particularly in Natural Language Processing (NLP) or when dealing with heavy-tailed data distributions—this assumption is often violated. In these cases, the noise is better modeled as having a finite $p$-th moment for $p \in (1, 2]$. When $p < 2$, the variance is infinite, and vanilla SGD can fail to converge.

While recent research has addressed this "heavy-tailed" regime for smooth functions, the nonsmooth case—where functions may have sharp transitions or kinks (e.g., ReLU activations or $L_1$ losses)—has lacked rigorous high-probability guarantees. This paper provides a comprehensive theoretical framework to address this deficiency.

2. The Challenge of Heavy-Tailed Noise

In the heavy-tailed regime, the stochastic gradient $\hat{g}_t$ satisfies $\mathbb{E}[\|\hat{g}_t - \nabla f(x_t)\|^p] \leq \sigma^p$. The primary difficulty is that standard concentration inequalities (like Hoeffding's) do not apply when variance is infinite. A single "wild" gradient can significantly derail the optimization process. To mitigate this, the authors analyze a Projected SGD with Clipping algorithm.

Instead of updating directly with the noisy gradient, the algorithm scales the gradient down if its magnitude exceeds a threshold $M_t$:

$$\text{clip}(\hat{g}_t, M_t) = \min\left(1, \frac{M_t}{\|\hat{g}_t\|}\right)\hat{g}_t$$

This clipping mechanism prevents extreme noise realizations from dominating the update, effectively "taming" the heavy tails.

3. Key Theoretical Contributions

3.1 High-Probability Bounds

Most existing literature on heavy-tailed noise focuses on "in-expectation" results, which describe average performance over many runs. This paper provides high-probability bounds, which guarantee performance for a single run of the algorithm. By utilizing Freedman’s inequality for martingales, the authors derive bounds where the error depends on the failure probability $\delta$ as $O(\log(1/\delta))$, the gold standard for robust optimization.

3.2 Optimal Convergence Rates

The paper establishes rates that match known lower bounds up to logarithmic factors:

  • Convex Functions: Achieves a rate of $\tilde{O}(T^{\frac{1-p}{p}})$. When $p=2$ (finite variance), this recovers the standard $O(1/\sqrt{T})$ rate.
  • Strongly Convex Functions: Achieves a rate of $O(T^{\frac{2(1-p)}{p}})$. When $p=2$, this recovers the standard $O(1/T)$ rate.

These results are "any-time," meaning they hold for any iteration $T$ even if the total horizon is not known in advance.

3.3 Parameter-Free and Adaptive Optimization

A significant hurdle in clipping-based methods is choosing the clipping threshold $M_t$, which usually depends on the noise level $\sigma$. The authors demonstrate a parameter-free version of the algorithm that guarantees convergence without prior knowledge of $\sigma$. Additionally, they provide an "initial distance adaptive" rate, where the dependence on the starting distance from the optimum is logarithmic rather than quadratic, significantly improving performance when the initial guess is far from the solution.

4. Conclusion and Limitations

This work provides the first comprehensive analysis of nonsmooth convex optimization under heavy-tailed noise, proving that simple gradient clipping is sufficient to achieve optimal high-probability rates. While the algorithm is parameter-free regarding the noise level $\sigma$, it still requires knowledge of the moment order $p$, the Lipschitz constant $G$, and the strong convexity parameter $\mu$. Developing a fully adaptive algorithm that requires none of these constants remains an open and promising direction for future research.

Summary updated

Abstract

Recently, several studies consider the stochastic optimization problem but in a heavy-tailed noise regime, i.e., the difference between the stochastic gradient and the true gradient is assumed to have a finite $p$-th moment (say being upper bounded by $\sigma^{p}$ for some $\sigma\geq0$) where $p\in(1,2]$, which not only generalizes the traditional finite variance assumption ($p=2$) but also has been observed in practice for several different tasks. Under this challenging assumption, lots of new progress has been made for either convex or nonconvex problems, however, most of which only consider smooth objectives. In contrast, people have not fully explored and well understood this problem when functions are nonsmooth. This paper aims to fill this crucial gap by providing a comprehensive analysis of stochastic nonsmooth convex optimization with heavy-tailed noises. We revisit a simple clipping-based algorithm, whereas, which is only proved to converge in expectation but under the additional strong convexity assumption. Under appropriate choices of parameters, for both convex and strongly convex functions, we not only establish the first high-probability rates but also give refined in-expectation bounds compared with existing works. Remarkably, all of our results are optimal (or nearly optimal up to logarithmic factors) with respect to the time horizon $T$ even when $T$ is unknown in advance. Additionally, we show how to make the algorithm parameter-free with respect to $\sigma$, in other words, the algorithm can still guarantee convergence without any prior knowledge of $\sigma$. Furthermore, an initial distance adaptive convergence rate is provided if $\sigma$ is assumed to be known.
BibTeX
@misc{liu2023stochastic,
  author = {Zijian Liu and Zhengyuan Zhou},
  title = {{Stochastic Nonsmooth Convex Optimization with Heavy-Tailed Noises}},
  year = {2023},
  eprint = {2303.12277},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2303.12277},
}
Figure