Clipped Stochastic Gradient Tracking For Locally Smooth Functions

Leilei Mei, Junyu Zhang · 2026

Read Clipped Stochastic Gradient Tracking For Locally Smooth Functions by Leilei Mei, Junyu Zhang (2026) 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-2605-17027.txt.

Introduction

Mei and Zhang design a distributed optimization method that copes when a problem's smoothness changes sharply across its domain. Older methods lean on one global smoothness bound, which can be far too cautious, while raw local values can swing wildly. The pair sets out a broad regularity rule covering steady, slow-growing, and fast-growing cases. They then build a clipped tracking method with staged variance cuts that needs only local smoothness.

Catalog record

CREATORLeilei Mei, Junyu Zhang
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE111117
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2605.17027

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Clipped Stochastic Gradient Tracking For Locally Smooth Functions Leilei Mei, Junyu Zhang Abstract Most stochastic gradient tracking (GT) methods adopt pre-scheduled stepsize rules, while a few recent works studied adaptive stepsizes that attempt to respond to the problem’s local landscape. These methods are typically built upon the problem’s global smoothness constant in both analysis and implementation, even for the adaptive ones. On the one hand, for many problems the local smoothness constant may vary drastically across the domain, and sometimes even unbounded, using the global upper bound of the local constants is too conservative. On the other hand, drastic stepsize changes can cause difficulties in the analysis of convergence and consensus of distributed algorithms, making the direct use of local smoothness constants risky and theoretically challenging. In this paper, we propose a Relative Uniform Continuity (RUC) regularity condition for the local smoothness constant as a function of sets. The RUC condition covers most common growth functions for local smoothness constant, ranging from constant and logarithmic to polynomial and even exponential. For RUC-regular distributed optimization problems with finite-sum structure, we derive a clipped gradient tracking method with staggered variance reduction, which only relies on the local smoothness of objective functions, and an 𝒪 ⁡ ( ∑ i n i 1.5 + n i 0.5 ​ ϵ − 1 ) \mathcal{O}(\sum_{i}n_{i}^{1.5}+n_{i}^{0.5}\epsilon^{-1}) complexity has been established for our algorithm. Keywords : Distributed Optimization, Gradient Clipping, Non-Lipschitz-Smooth 1 Introduction Distributed optimization is a key of large network systems in many signal processing, control, and machine learning applications [ 26 , 30 , 6 , 21 ] , where people aim to solve the following formulation: \displaystyle\min_{x_{1},\cdots,x_{m}}\,\,\frac{1}{m}\sum_{i=1}^{m}f_{i}(x_{i})\qquad\mathrm{s.t.}\qquad x_{i}=x_{j},\forall\,i,j\in[m]. (1) Efficient classic algorithms for this problem include the distributed gradient descent (DGD) [ 27 , 28 , 48 , 49 ] , gradient tracking (GT) [ 26 , 33 , 16 ] , Push-Pull [ 27 , 19 , 36 , 34 ] , the primal-dual (PD) methods [ 31 , 50 ] , as well as their numerous variants [ 36 , 10 , 40 , 23 , 37 , 46 , 33 , 39 ] , to name a few. In this paper, we are specifically interested in the stochastic distributed algorithms for the finite-sum setting: \min_{x\in\mathbb{R}^{d}}\frac{1}{m}\sum_{i=1}^{m}f_{i}(x)\qquad\mbox{with}\qquad f_{i}(x)=\frac{1}{n_{i}}\sum_{j=1}^{n_{i}}f_{i,j}(x),\quad i\in[m], (2) where n_{i} stands for the local data size of agent i , [m]:=\{1,\cdots,m\}, and the local objective function f_{i} ’s are differentiable but possibly nonconvex. Under the finite-sum setting, the predominant results are the distributed stochastic variance reduced first-order methods, including [ 38 , 46 , 43 , 42 , 44 , 12 , etc.] , most of which are based on gradient tracking due to its ability to simultaneously obtain consensus in iterates and gradient estimations. By adopting variance reduction technique, they behave significantly better than vanilla stochastic approximation variants of GT and DGD, such as [ 40 , 23 , 33 ] . In this paper, we are particularly interested in the problem setting where, instead of assuming each f_{i} to be globally L -smooth, we only require the knowledge of a set function \mathbb{L}(\mathcal{X}) that returns an upper bound of f_{i} ’s local smoothness constant in some set \mathcal{X} , which does not exclude the extreme case \mathbb{L}(\mathbb{R}^{d})=+\infty that corresponds to problems that are not globally Lipschitz-smooth. Our main motivation for considering local smoothness is that for many optimization problems, the local smoothness constants can vary drastically across the problem domain. One typical example is the so-called \alpha -generalized smoothness condition, which assumes the training loss f(x) to satisfy \|\nabla^{2}f(x)\|\leq L_{0}+L_{1}\|\nabla f(x)\|^{\alpha}. It holds with \alpha=1 for deep models in natural language processing (NLP), computer vision (CV) tasks [ 52 ] , and distributed robust optimization (DRO) tasks [ 13 ] . It also holds with \alpha=2/3 for phase retrieval problem [ 7 ] , and it is shown in [ 18 ] that the self-concordant functions [ 29 ] satisfy this condition with \alpha=2 . Note that for large problems, the initial gradient size is often large if no good guess of near-stationary initialization is provided, e.g., in our experiments, the initial gradient can be as large as 10^{5} . This brings large variation to local smoothness constants during problem solving. In addition, for the hard problem instances considered under the relative smooth optimization topic [ 4 , 22 ] , where \|\nabla^{2}f(x)\|\leq L\|\nabla^{2}h(x)\| for some general strictly convex but non-Lipschitz-smooth distance generating function h , the local smoothness constants can explode when the iterations approach the boundary \partial\mathrm{dom}(h) . In these problems, the global smoothness constant either does not exist or can be several orders greater than the local constants. According to the above discussion, it is crucial for an algorithm to adapt to a problem’s local smoothness properties if the problem has drastically varying local smoothness constants. Note that the state-of-the-art variance reduced algorithms [ 38 , 46 , 42 , 43 , 44 , 12 , etc.] in the existing results all work under the classic setting where a global smoothness constant is assumed and used throughout the design and analysis of the algorithm. Therefore, a straightforward idea is replacing the global smoothness constant by its local counterparts in each epoch of the variance reduced methods. Unfortunately, such a direct modification may not necessarily lead to a convergent method, which is mainly due to the technical intricacies of GT-based variance reduction methods in balancing consensus and convergence, as well as designing a descending Lyapunov functions that governs the algorithm’s convergence behavior. To resolve this gap, we introduce a new Relative Uniform Continuous (RUC) regularity condition for the local smoothness constant. Under this condition, for any \epsilon>0 , there exists a \delta>0 so that the relative difference between the local smoothness constants satisfies \left|1-\max\left\{\frac{\mathbb{L}(\mathcal{X})}{\mathbb{L}(\mathcal{Y})},\frac{\mathbb{L}(\mathcal{Y})}{\mathbb{L}(\mathcal{X})}\right\}\right|<\epsilon\qquad\forall d_{\mathrm{H}}(\mathcal{X},\mathcal{Y})\leq\delta, where d_{\mathrm{H}}(\cdot,\cdot) stands for the Hausdorff distance of the two sets. We should notice that the above relative difference bound is much milder than requiring the absolute value difference |\mathbb{L}(\mathcal{X})-\mathbb{L}(\mathcal{Y})| to be small in our interested problem setting, where both \mathbb{L}(\mathcal{X}) and \mathbb{L}(\mathcal{Y}) are large numbers. In this paper, we show that this condition covers a lot of common growth functions \mathbb{L}(\cdot) for local smoothness constants, ranging from constant and logarithmic to polynomial and even exponential. In particular, the \alpha -generalized smoothness condition with \alpha\in(0,1] , and the relative smoothness condition with appropriate kernels can also be covered. Moreover, we show that this regularity condition is very versatile and robust and it remains closed under various operations on the function \mathbb{L}(\cdot) , such as affine composition, scaling, linear combination, and point-wise maximum or minimum, making it convenient to construct or check new growth function for local smoothness constant by manipulating the known RUC-regular functions. If the objective function of problem ( 2 ) is RUC-regular, then it is implied that the local smoothness constants do not change so fast in a relative sense, even though they may still vary drastically in the absolute sense. To utilize this property, we consider a clipped gradient tracking technique that clips the update when it is too aggressive while preserving the update if it is in a controllable range. Based on this technique, we design a staggered variance reduced algorithms with clipped gradient tracking to solve problem

Read the complete text