mlsanityData to 14 Oct 2026

Online Optimization Perspective on First-Order and Zero-Order Decentralized Nonsmooth Nonconvex Stochastic Optimization

arXiv 2406.01484 ↗First posted 3 Jun 2024math.OC cs.LG cs.SYcited by 4

Not on the map. Why?

Abstract (arXiv)

We investigate the finite-time analysis of finding (δ,ε)-stationary points for nonsmooth nonconvex objectives in decentralized stochastic optimization. A set of agents aim at minimizing a global function using only their local information by interacting over a network. We present a novel algorithm, called Multi Epoch Decentralized Online Learning (ME-DOL), for which we establish the sample complexity in various settings. First, using a recently proposed online-to-nonconvex technique, we show that our algorithm recovers the optimal convergence rate of smooth nonconvex objectives. We then extend our analysis to the nonsmooth setting, building on properties of randomized smoothing and Goldstein-subdifferential sets. We establish the sample complexity of O(δ-1ε-3), which to the best of our knowledge is the first finite-time guarantee for decentralized nonsmooth nonconvex stochastic optimization in the first-order setting (without weak-convexity), matching its optimal centralized counterpart. We further prove the same rate for the zero-order oracle setting without using variance reduction.

Key facts. Cited by 4 papers in the map (data through 14 Oct 2026). Builds on 28 of its 37 references that are in the map. First posted on arXiv 3 Jun 2024.

Builds on

28 of 37 references.

References · 28

  1. 2018Federated Optimization in Heterogeneous Networkscited by 2,987
  2. 2016Federated Learning: Strategies for Improving Communication Efficiencycited by 1,475
  3. 2020Tackling the Objective Inconsistency Problem in Heterogeneous Federated Optimizationcited by 906
  4. 2013Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programmingcited by 724
  5. 2017Can Decentralized Algorithms Outperform Centralized Algorithms? A Case Study for Decentralized Parallel Stochastic Gradient Descentcited by 502
  6. 2019Why gradient clipping accelerates training: A theoretical justification for adaptivitycited by 341
  7. 2019Lower Bounds for Non-Convex Stochastic Optimizationcited by 307
  8. 2019Decentralized Stochastic Optimization and Gossip Algorithms with Compressed Communicationcited by 221
  9. 2018Stochastic model-based minimization of weakly convex functionscited by 159
  10. 2018D2: Decentralized Training over Decentralized Datacited by 140
  11. 2017Lower Bounds for Finding Stationary Points Icited by 126
  12. 2015An Optimal Algorithm for Bandit and Zero-Order Convex Optimization with Two-Point Feedbackcited by 111
16 more
  1. 2021Asynchronous Federated Learning on Heterogeneous Devices: A Surveycited by 93
  2. 2020Optimal Complexity in Decentralized Trainingcited by 60
  3. 2023Optimal Stochastic Non-smooth Non-convex Optimization through Online-to-Non-convex Conversioncited by 45
  4. 2022Gradient-Free Methods for Deterministic and Stochastic Nonsmooth Nonconvex Optimizationcited by 43
  5. 2018Optimal Algorithms for Non-Smooth Distributed Optimization in Networkscited by 41
  6. 2021A gradient sampling method with complexity guarantees for Lipschitz functions in high and low dimensionscited by 39
  7. 2016Distributed Online Optimization in Dynamic Environments Using Mirror Descentcited by 32
  8. 2021On the Finite-Time Complexity and Practical Computation of Approximate Stationarity Concepts of Lipschitz Functionscited by 31
  9. 2017Revisiting Normalized Gradient Descent: Fast Evasion of Saddle Pointscited by 29
  10. 2023Deterministic Nonsmooth Nonconvex Optimizationcited by 26
  11. 2018Analysis of nonsmooth stochastic approximation: the differential inclusion approachcited by 23
  12. 2023An Algorithm with Optimal Dimension-Dependence for Zero-Order Nonsmooth Nonconvex Stochastic Optimizationcited by 23
  13. 2023Faster Gradient-Free Algorithms for Nonsmooth Nonconvex Stochastic Optimizationcited by 17
  14. 2020Distributed Stochastic Gradient Descent: Nonconvexity, Nonsmoothness, and Convergence to Local Minimacited by 13
  15. 2022On the Complexity of Deterministic Nonsmooth and Nonconvex Optimizationcited by 6
  16. 2023Decentralized Gradient-Free Methods for Stochastic Non-Smooth Non-Convex Optimizationcited by 5

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2025: 3; 2026: 1.

4 papers.

  1. 2025Decentralized Online Riemannian Optimization Beyond Hadamard Manifoldscited by 4
  2. 2025Finite-Time Analysis of Stochastic Nonconvex Nonsmooth Optimization on the Riemannian Manifoldscited by 2
  3. 2025Frequency Response Identification of Low-Order Systems: Finite-Sample Analysiscited by 0
  4. 2026Dimension-Free Decentralized Nonsmooth Nonconvex Stochastic Optimizationcited by 0