Decentralized Stochastic Nonconvex Optimization under the (L₀,L₁)-Smoothness

This paper focuses on the decentralized stochastic optimization problem f(x)=1/m gi=1m fi(x) over a connected network of n agents, where each local function has the form of fi(x) = E[F(x;ζ i)] which satisfies the (L0,L1)-smooth condition but possibly nonconvex and each random variable ζi follows distribution 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 O(m-1 (Lfσ2Δfϵ-4 + σ2ϵ-2 + Lf-2 L13σ2?fΔ-1 + Lf-2 L12σ2)) per agent and the communication complexity of ∼O ((Lfϵ-2 + L1ϵ-1)γ-1/2 Δf), where Lf=L0 +L1ζ, σ2 is the variance of the stochastic gradient, Δf is the initial optimal function value gap, γis the spectral gap of the network, and ζ 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.