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

2025/09/10 by Luo Luo, Xue Cui, Luo, Luo +4
Computer Science · #Distributed Control Multi-Agent Systems #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Optimization and Control (math.OC) #Privacy-Preserving Technologies in Data #Stochastic Gradient Optimization Techniques

paper · pdf · doi:10.48550/arxiv.2509.08726

openalex publication_date 2025/09/10 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

This paper focuses on the decentralized stochastic optimization problem f(x)=(1)/(m)∑_i=1^m f_i(x) over a connected network of n agents, where each local function has the form of f_i(x) = \mathbb E[F(x;\boldsymbol ξ_i)] which satisfies the (L₀,L₁)-smooth condition but possibly nonconvex and each random variable \boldsymbol ξ_i follows distribution \mathcal D_i. 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 (L₀,L₁)-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_fσ²Δ_fε^-4 + σ²ε^-2 + L_f^-2L₁³σ²Δ_fε^-1 + L_f^-2L₁²σ²)) per agent and the communication complexity of \mathcal O((L_fε^-2 + L₁ε^-1)γ^-1/2Δ_f), where L_f=L₀ +L₁ζ, σ² 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 L₁=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.

Citations

• Decentralized Relaxed Smooth Optimization with Gradient Descent Methods
• Nesterov Finds GRAAL: Optimal and Adaptive Gradient Method for Convex Optimization
• Convergence of Clipped-SGD for Convex (L₀,L₁)-Smooth Optimization with Heavy-Tailed Noise
• Complexity Lower Bounds of Adaptive Gradient Algorithms for Non-convex Stochastic Optimization under Relaxed Smoothness
• Revisiting Stochastic Proximal Point Methods: Generalized Smoothness and Similarity
• Nonconvex Stochastic Optimization under Heavy-Tailed Noises: Optimal Convergence without Gradient Clipping
• Linear Convergence Rate in Convex Setup is Possible! Gradient Descent Method Variants under (L₀,L₁)-Smoothness
• Toward a Unified Theory of Gradient Descent under Generalized Smoothness
• Optimizing (L₀, L₁)-Smooth Functions by Gradient Methods
• Problem-Parameter-Free Decentralized Nonconvex Stochastic Optimization
• On the Complexity of Finite-Sum Smooth Optimization under the Polyak-Łojasiewicz Condition
• Trust Region Methods For Nonconvex Stochastic Optimization Beyond Lipschitz Smoothness
• Revisiting Gradient Clipping: Stochastic bias and tight convergence guarantees
• Convergence of Adam Under Relaxed Assumptions
• Generalized-Smooth Nonconvex Optimization is As Efficient As Smooth Nonconvex Optimization
• Revisiting Optimal Convergence Rate for Smooth and Non-convex Stochastic Decentralized Optimization
• Robustness to Unbounded Smoothness of Generalized SignSGD
• Optimal Gradient Tracking for Decentralized Optimization
• Local SGD: Unified Theory and New Efficient Methods
• Improved Analysis of Clipping Algorithms for Non-convex Optimization
• A general framework for decentralized optimization with first-order methods
• Variance Reduced EXTRA and DIGing and Their Optimal Acceleration for Strongly Convex Decentralized Optimization
• Optimal Complexity in Decentralized Training
• Minibatch vs Local SGD for Heterogeneous Distributed Learning
• An Optimal Algorithm for Decentralized Finite Sum Optimization
• Multi-consensus Decentralized Accelerated Gradient Descent
• Momentum Improves Normalized SGD
• Why gradient clipping accelerates training: A theoretical justification for adaptivity
• LEAF: A Benchmark for Federated Settings
• SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimator
• Network Topology and Communication-Computation Tradeoffs in\n Decentralized Optimization
• Fashion-MNIST: a Novel Image Dataset for Benchmarking Machine Learning Algorithms
• Can Decentralized Algorithms Outperform Centralized Algorithms? A Case Study for Decentralized Parallel Stochastic Gradient Descent
• Optimal algorithms for smooth and strongly convex distributed optimization in networks
• Communication-Efficient Algorithms for Decentralized and Stochastic Optimization
• Beyond Convexity: Stochastic Quasi-Convex Optimization
• Gradient-based learning applied to document recognition

Related

• On the Complexity of Decentralized Smooth Nonconvex Finite-Sum Optimization
• Problem-Parameter-Free Decentralized Nonconvex Stochastic Optimization
• Communication-Efficient Algorithms for Decentralized and Stochastic Optimization
• Decentralized Relaxed Smooth Optimization with Gradient Descent Methods
• Online Optimization Perspective on First-Order and Zero-Order Decentralized Nonsmooth Nonconvex Stochastic Optimization