Title: Decentralized Stochastic Nonconvex Optimization under the $(L_0,L_1)$-Smoothness

Abstract:

This study addresses the decentralized stochastic optimization task defined by $f(\mathbf{x})=\frac{1}{m}\sum_{i=1}^m f_i(\mathbf{x})$ across a connected network comprising $n$ agents. In this setting, each local objective function is expressed as $f_i(\mathbf{x}) = {\mathbb E}\left[F(\mathbf{x};{\boldsymbol \xi}_i)\right]$, adhering to the $(L_0,L_1)$-smoothness constraint while potentially being nonconvex. Furthermore, the random variable ${\boldsymbol \xi}_i$ is drawn from a distribution denoted as ${\mathcal D}_i$. To solve this problem, we introduce a new algorithm named decentralized normalized stochastic gradient descent (DNSGD), designed to locate an $\epsilon$-stationary point at every individual agent.

We establish a novel analytical framework for decentralized first-order methods operating within the $(L_0,L_1)$-smooth context. This approach relies on a Lyapunov function constructed from the product of the consensus error and the gradient norm. Our analysis demonstrates that the proposed algorithm achieves specific upper bounds for both sample and communication complexities. Specifically, the sample complexity per agent is bounded by ${\mathcal O}(m^{-1}(L_f\sigma^2\Delta_f\epsilon^{-4} + \sigma^2\epsilon^{-2} + L_f^{-2}L_1^3\sigma^2\Delta_f\epsilon^{-1} + L_f^{-2}L_1^2\sigma^2))$. The communication complexity is given as $\tilde{\mathcal O}((L_f\epsilon^{-2} + L_1\epsilon^{-1})\gamma^{-1/2}\Delta_f)$. Here, $L_f=L_0 +L_1\zeta$, where $\sigma^2$ represents the variance of the stochastic gradient, $\Delta_f$ denotes the initial gap in the optimal function value, $\gamma$ is the network’s spectral gap, and $\zeta$ quantifies the degree of gradient dissimilarity. Notably, when $L_1=0$, these findings closely align with the established lower bounds for decentralized stochastic nonconvex optimization under standard smoothness conditions. Finally, numerical simulations are presented to validate the empirical effectiveness of our proposed method.

Source: arXiv Generated at: 2026-06-03 00:00:00 UTC