Stochastic Weakly Convex Optimization Under Heavy-Tailed Noises
Tianxi Zhu, Yi Xu, Xiangyang Ji · 2025
Read Stochastic Weakly Convex Optimization Under Heavy-Tailed Noises by Tianxi Zhu, Yi Xu, Xiangyang Ji (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2507-13283.txt.
Introduction
Tianxi Zhu, Yi Xu, and Xiangyang Ji study how well a basic training method holds up when data noise has heavy tails, in a 2025 paper. Heavy tailed noise, with rare huge jumps, shows up when training real deep learning models. Their setting is weakly convex goals, a broad class that covers many non smooth and non convex tasks.
They test two noise forms: one with a named tail shape, and one where only a low moment is bounded, which allows endless variance. For the plain method under the first form, high chance bounds match the smooth case. For the harder form, a clipped version keeps the same chance bounds, though it needs more samples than the smooth case.
Catalog record
| CREATOR | Tianxi Zhu, Yi Xu, Xiangyang Ji |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 96 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2507-13283
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Stochastic Weakly Convex Optimization Under Heavy-Tailed Noises Tianxi Zhu, Yi Xu, Xiangyang Ji Abstract An increasing number of studies have focused on stochastic first-order methods (SFOMs) under heavy-tailed gradient noises, which have been observed in the training of practical deep learning models. In this paper, we focus on two types of gradient noises: one is sub-Weibull noise, and the other is noise under the assumption that it has a bounded p p -th central moment ( p p -BCM) with p ∈ ( 1 , 2 ] p\in(1,2] . The latter is more challenging due to the occurrence of infinite variance when p ∈ ( 1 , 2 ) p\in(1,2) . Under these two gradient noise assumptions, the in-expectation and high-probability convergence of SFOMs have been extensively studied in the contexts of convex optimization and standard smooth optimization. However, for weakly convex objectives—a class that includes all Lipschitz-continuous convex objectives and smooth objectives—our understanding of the in-expectation and high-probability convergence of SFOMs under these two types of noises remains incomplete. We investigate the high-probability convergence of the vanilla stochastic subgradient descent (SsGD) method under sub-Weibull noises, as well as the high-probability and in-expectation convergence of clipped SsGD under the p p -BCM noises. Both analyses are conducted in the context of weakly convex optimization. For weakly convex objectives that may be non-convex and non-smooth, our results demonstrate that the theoretical dependence of vanilla SsGD on the failure probability and number of iterations under sub-Weibull noises does not degrade compared to the case of smooth objectives. Under p p -BCM noises, our findings indicate that the non-smoothness and non-convexity of weakly convex objectives do not impact the theoretical dependence of clipped SGD on the failure probability relative to the smooth case; however, the sample complexity we derived is worse than a well-known lower bound for smooth optimization. First version: July 17, 2025 1 Introduction In this paper, we focus on the following stochastic optimization problem, which commonly arises in the field of machine learning. \displaystyle\min_{x\in\mathcal{X}}f(x),\quad f(x)\triangleq\mathbb{E}_{\zeta}[f(x,\zeta)] (1) where \zeta is a random variable following an unknown distribution and f(x) is a closed proper function defined on a closed convex set \mathcal{X} . For solving problem ( 1 ), stochastic first-order optimization methods (SFOMs) such as stochastic gradient descent (SGD) ( Robbins 1951 ) have been commonly adopted. Unlike deterministic gradient-based methods, SFOMS are done using unbiased or biased estimators of the true gradient of f to improve training efficiency. The convergence of SFOMs, whether in expectation or with high probability, has been extensively studied in the contexts of convex or smooth optimization ( Ghadimi and Lan 2013 ; Fang et al. 2018 ; Cutkosky and Orabona 2019 ; Lan 2020 ; Cutkosky and Mehta 2020 ; Liu et al. 2023a ) . Specifically, we focus on weakly convex optimization in problem ( 1 ), where f(x) is weakly convex. The definition of weakly convexity is straightforward, i.e., a function f is \rho -weakly convex if and only if f(x)+\rho/2\|x\|^{2} is convex, where \rho\geq 0 . Readers might consider this merely a relaxation of standard convexity. In fact, an important proposition of weakly convex function is that given a L -Lipschitz continous and convex function h:\mathbb{R}^{m}\mapsto\mathbb{R} and a \beta -smooth function c:\mathbb{R}^{d}\mapsto\mathbb{R}^{m} , then their composition h\circ c is a \beta L -weakly convex function (see Lemma 4.2 in ( Drusvyatskiy and Paquette 2017 ) ). By letting h and c be the identity function, we can conclude that weakly convex functions include all Lipschitz continuous convex functions and smooth functions, since the identity function is obviously 1-Lipschitz continuous, convex, and 1-smooth. Furthermore, this composition function structure can be connected with the architecture of neural networks. For instance, with a standard loss function like the logistic loss, the sample loss of a neural network employing sigmoid or tanh activation functions exhibits weak convexity while being non-convex and non-smooth. A lot of prior works has studied the convergence of SFOMs in weakly optimization, such as ( Davis and Drusvyatskiy 2018a ; Davis and Drusvyatskiy 2018c ; Alacaoglu et al. 2020 ; Chen et al. 2022 ; Li et al. 2022 ; Gao and Deng 2023 ; Gao and Deng 2024 ; Hu et al. 2024 ; Liao et al. 2024 ; Hong and Lin 2025 ) . A key assumption in their theoretical analysis is that the gradient noise is supposed to be variance bounded or sub-Gaussian, which is defined as light-tailed type distribution in statistical terminology. However, recent observations have empirically shown that the distributions of gradient noises may be heavy-tailed, both in training convolutional neural networks ( Simsekli et al. 2019 ) and BERT ( Devlin et al. 2019 ) . All these observations motivate us to assume that gradient noises should satisfy weaker assumptions than variance boundedness or sub-Gaussian properties. In this paper, we consider the heavy-tailed gradient noises in weakly convex optimization. We first focus on the sub-Weibull noises distribution. We say that X follows a \sigma -sub-Weibull( \theta ) distribution, i.e., for a random vector X , if there exists a nonnegative real number \sigma and satisfy \displaystyle\mathbb{E}\left[\exp\left\{\left(|X|/\sigma\right)^{1/\theta}\right\}\right]\leq 2, (2) where \theta\geq 1/2 is the tail parameter. The sub-Weibull distribution is more general than the sub-Gaussian distribution. When \theta=1/2 , it reduces to sub-Gaussian distributions, and when \theta=1 , it corresponds to sub-exponential distributions. As the tail parameter \theta increases, the tails of sub-Weibull distributions become heavier. For more equivalent definitions of sub-Weibull, we refer interested readers to ( Vladimirova et al. 2020a ) . Prior works such as ( Madden et al. 2020 ; Li and Liu 2022 ; Li et al. 2025 ) have studied the high-probability convergence of SFOMs under sub-Weibull noises in smooth optimization 1 1 1 Smoothness assumption is stronger than the assumption of weakly convexity . Given the existence of weakly convex objectives in machine learning, we pose our first question: Q1: For stochastic weakly convex optimization under sub-Weibull noises, does SGD exhibit a worse dependency on the number of iterations and failure probability \delta than in smooth optimization cases? Note that due to the possible non-differentiability of weakly convex functions, the SGD method here specifically refers to the stochastic sub-gradient descent (SsGD) method. Next, we focus on the assumption that assume the distribution of gradient noises have bounded p -th bounded central moment ( p -BCM), i.e., suppose that the random vector X is centralized ( \mathbb{E}[X]=0 ) and if for p\in(1,2] , we have \displaystyle\mathbb{E}[\|X\|^{p}]\leq\sigma^{p}\leq+\infty. (3) We say random X has bounded p -th bounded central moments. The p -BCM noise assumption is more challenging than the sub-Weibull noise assumption. Notice that if the gradient noises satisfy p -BCM assumption for p<2 , the second central moment of the noises could be possibly infinite, hence the p -BCM assumption is strictly weaker than the variance bounded assumption. Particularly, the case of p\in(1,2) is much more complicated as the existing theory for vanilla SGD shows that SGD may divergence. A lot of prior works, such as ( Zhang et al. 2020b ; Cutkosky and Mehta 2021 ; Nguyen et al. 2023 ; Gorbunov et al. 2024 ) , has demonstrated that through gradient clipping—i.e., restricting the stochastic gradient norm to a