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

arXiv:2509.08726v3 Announce Type: replace-cross Abstract: This paper focuses on the decentralized stochastic optimization problem f(mathbf{x})=frac{1}{m}sum_{i=1}^m f_i(mathbf{x}) over a connected network of n agents, where each local function has the form of f_i(mathbf{x}) = {mathbb E}left[F(mathbf{x};{oldsymbol xi}_i)right] which satisfies the (L_0,L_1)-smooth condition but possibly nonconvex and each random variable {oldsymbol xi}_i follows distribution {mathcal D}_i. We propose a novel algorithm called decentralized normalized stochastic gradient descent (DNSGD), which can achieve an epsilon-stationary point at each local agent. We present a new framework for analyzing decentralized first-order methods in the (L_0,L_1)-smooth setting, based on the Lyapunov function related to the product of the gradient norm and the consensus error. We show that the proposed algorithm attains the upper bounds on the sample complexity of {mathcal O}(m^{-1}(L_fsigma^2Delta_fepsilon^{-4} + sigma^2epsilon^{-2} + L_f^{-2}L_1^3sigma^2Delta_fepsilon^{-1} + L_f^{-2}L_1^2sigma^2)) per agent and the communication complexity of ilde{mathcal O}((L_fepsilon^{-2} + L_1epsilon^{-1})gamma^{-1/2}Delta_f), where L_f=L_0 +L_1zeta, sigma^2 is the variance of the stochastic gradient, Delta_f is the initial optimal function value gap, gamma is the spectral gap of the network, and zeta is the degree of the gradient dissimilarity. In the special case of L_1=0, the above results (nearly) match the lower bounds of decentralized stochastic nonconvex optimization under the standard smoothness. We also conduct numerical experiments to show the empirical superiority of our method.

Source: arXiv cs.LG | 2026-06-03