Research map / Optimization / Nonconvex and smooth optimization
An Online Optimization Perspective on First-Order and Zero-Order Decentralized Nonsmooth Nonconvex Stochastic Optimization
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes ME-DOL, a decentralized online-learning-based restarting method for nonsmooth nonconvex stochastic optimization that reaches O(δ^{-1}ε^{-3}) sample complexity for (δ,ε)-stationarity in first-order and zero-order settings.
Problem
Finite-time analysis of finding (δ,ε)-Goldstein stationary points of nonsmooth nonconvex global functions in decentralized stochastic optimization over networks, with first-order or zero-order oracles.
Approach
Extends the online-to-nonconvex conversion to the decentralized setting by restarting a decentralized online gradient method each epoch, combined with randomized smoothing and the Goldstein subdifferential geometric lemma (splitting δ between smoothing and stationarity radius) so that smoothness-dependent terms are controlled and the centralized rate is matched.
Key results
- Theoretical sample complexity O(δ^{-1}ε^{-3}) for decentralized nonsmooth nonconvex stochastic optimization with first-order oracles, matching the centralized rate and being the first such finite-time guarantee without weak convexity.
- Zero-order setting achieves O(d δ^{-1} ε^{-3}) without variance reduction, improving dimension dependence from d^{3/2} (DGFM/DGFM+).
- Smooth first-order case recovers the optimal O(ε^{-4}) rate when δ=O(ε); the rate scales as (1-ρ)^{-2} in network connectivity.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use ME-DOL instead of DGFM | Decentralized zero-order nonsmooth nonconvex stochastic optimization · Decentralized nonsmooth nonconvex stochastic optimization | sample complexity: $O(d^{\frac{3}{2}}\delta^{-1}\epsilon^{-4})$ -> $O(d\delta^{-1} \epsilon^{-3})$ | Helped |
| Use ME-DOL without variance reduction instead of DGFM+ | Decentralized zero-order nonsmooth nonconvex stochastic optimization · Decentralized nonsmooth nonconvex stochastic optimization | dimension dependence of sample complexity: $O(d^{\frac{3}{2}} \delta^{-1} \epsilon^{-3})$ -> $O(d\delta^{-1} \epsilon^{-3})$ | Helped |
| Use ME-DOL for first-order nonsmooth optimization without weak-convexity | Decentralized stochastic optimization · Decentralized nonsmooth nonconvex stochastic optimization | sample complexity: $O(\delta^{-1} \epsilon^{-3})$ | Helped |
| Increase network connectivity (decrease $\rho$) | ME-DOL · First-order experiments on ring graphs and random graphs | convergence speed: $\{0.81, 0.70 , 0.57, 0.44 \}$; $\{0.83, 0.63, 0.56, 0.47\}$ | Helped |
Experimental setup
Datasets: ijcnn rcv1 SUSY a9a HIGGS covtype
Metrics: global gradient norm test classification accuracy
Baselines: DGFM DGFM+ DPSGD DPSM
Builds on: online-to-nonconvex conversion randomized smoothing decentralized online learning (Dec-OGD/DOLA-style) DGFM DPSGD
Closest papers by meaning
- Decentralized Convex Finite-Sum Optimization with Better Dependence on Condition Numbers (ICML 2024 · similarity 0.90)
- Jointly Improving the Sample and Communication Complexities in Decentralized Stochastic Minimax Optimization (AAAI 2024 · similarity 0.90)
- Decentralized Gradient-Free Methods for Stochastic Non-smooth Non-convex Optimization (AAAI 2024 · similarity 0.90)
- Decentralized Sum-of-Nonconvex Optimization (AAAI 2024 · similarity 0.89)
- Lower Bounds and Optimal Algorithms for Non-Smooth Convex Decentralized Optimization over Time-Varying Networks (NeurIPS 2024 · similarity 0.89)
- Faster Adaptive Decentralized Learning Algorithms (ICML 2024 · similarity 0.88)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.