Decentralized Stochastic Nonconvex Optimization under the (L0,L1)-Smoothness

This paper focuses on the decentralized stochastic optimization problem f(x)=frac1msumi=1m fi(x) over a connected network of n agents, where each local function has the form of fi(x) = mathbb Eleft[F(x;boldsymbol xii)right] which satisfies the (L0,L1)-smooth condition but possibly nonconvex and each random variable boldsymbol xii follows distribution mathcal Di. We propose a novel algorithm called decentralized normalized stochastic gradient descent (DNSGD), which can achieve an ε-stationary point at each local agent. We present a new framework for analyzing decentralized first-order methods in the (L0,L1)-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(Lfσ2Deltafε-4 + σ2ε-2 + Lf-2L13σ2Deltafε-1 + Lf-2L12σ2)) per agent and the communication complexity of tildemathcal O((Lfε-2 + L1ε-1)γ-1/2Deltaf), where Lf=L0 +L1zeta, σ2 is the variance of the stochastic gradient, Deltaf is the initial optimal function value gap, γ is the spectral gap of the network, and zeta is the degree of the gradient dissimilarity. In the special case of L1=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.