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

arXiv: https://arxiv.org/abs/2509.08726 · HTML: https://mlsanity.com/paper/2509.08726/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 37 of its 54 references that are in the map.
- First posted on arXiv 10 Sep 2025.

## Builds on (most cited first, 30 of 37)

- [Fashion-MNIST: a Novel Image Dataset for Benchmarking Machine Learning Algorithms](https://mlsanity.com/paper/1708.07747/) (2017)
- [LEAF: A Benchmark for Federated Settings](https://mlsanity.com/paper/1812.01097/) (2018)
- [Can Decentralized Algorithms Outperform Centralized Algorithms? A Case Study for Decentralized Parallel Stochastic Gradient Descent](https://mlsanity.com/paper/1705.09056/) (2017)
- [Why gradient clipping accelerates training: A theoretical justification for adaptivity](https://mlsanity.com/paper/1905.11881/) (2019)
- [SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimator](https://mlsanity.com/paper/1807.01695/) (2018)
- [On the Convergence of Decentralized Gradient Descent](https://mlsanity.com/paper/1310.7063/) (2013)
- [Minibatch vs Local SGD for Heterogeneous Distributed Learning](https://mlsanity.com/paper/2006.04735/) (2020)
- [Momentum Improves Normalized SGD](https://mlsanity.com/paper/2002.03305/) (2020)
- [Network Topology and Communication-Computation Tradeoffs in Decentralized Optimization](https://mlsanity.com/paper/1709.08765/) (2017)
- [Convergence of Adam Under Relaxed Assumptions](https://mlsanity.com/paper/2304.13972/) (2023)
- [Improved Analysis of Clipping Algorithms for Non-convex Optimization](https://mlsanity.com/paper/2010.02519/) (2020)
- [Local SGD: Unified Theory and New Efficient Methods](https://mlsanity.com/paper/2011.02828/) (2020)
- [Optimal algorithms for smooth and strongly convex distributed optimization in networks](https://mlsanity.com/paper/1702.08704/) (2017)
- [Revisiting Gradient Clipping: Stochastic bias and tight convergence guarantees](https://mlsanity.com/paper/2305.01588/) (2023)
- [Robustness to Unbounded Smoothness of Generalized SignSGD](https://mlsanity.com/paper/2208.11195/) (2022)
- [Beyond Convexity: Stochastic Quasi-Convex Optimization](https://mlsanity.com/paper/1507.02030/) (2015)
- [Optimal Complexity in Decentralized Training](https://mlsanity.com/paper/2006.08085/) (2020)
- [Communication-Efficient Algorithms for Decentralized and Stochastic Optimization](https://mlsanity.com/paper/1701.03961/) (2017)
- [Nonconvex Stochastic Optimization under Heavy-Tailed Noises: Optimal Convergence without Gradient Clipping](https://mlsanity.com/paper/2412.19529/) (2024)
- [Generalized-Smooth Nonconvex Optimization is As Efficient As Smooth Nonconvex Optimization](https://mlsanity.com/paper/2303.02854/) (2023)
- [A general framework for decentralized optimization with first-order methods](https://mlsanity.com/paper/2009.05837/) (2020)
- [Revisiting Optimal Convergence Rate for Smooth and Non-convex Stochastic Decentralized Optimization](https://mlsanity.com/paper/2210.07863/) (2022)
- [Multi-consensus Decentralized Accelerated Gradient Descent](https://mlsanity.com/paper/2005.00797/) (2020)
- [An Optimal Algorithm for Decentralized Finite Sum Optimization](https://mlsanity.com/paper/2005.10675/) (2020)
- [Optimizing (L0, L1)-Smooth Functions by Gradient Methods](https://mlsanity.com/paper/2410.10800/) (2024)
- [Optimal Gradient Tracking for Decentralized Optimization](https://mlsanity.com/paper/2110.05282/) (2021)
- [Variance Reduced EXTRA and DIGing and Their Optimal Acceleration for Strongly Convex Decentralized Optimization](https://mlsanity.com/paper/2009.04373/) (2020)
- [Trust Region Methods For Nonconvex Stochastic Optimization Beyond Lipschitz Smoothness](https://mlsanity.com/paper/2310.17319/) (2023)
- [Revisiting Stochastic Proximal Point Methods: Generalized Smoothness and Similarity](https://mlsanity.com/paper/2502.03401/) (2025)
- [Problem-Parameter-Free Decentralized Nonconvex Stochastic Optimization](https://mlsanity.com/paper/2402.08821/) (2024)

## Abstract (arXiv)

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.