Research map / Optimization / Nonconvex and smooth optimization
Decentralized Gradient-Free Methods for Stochastic Non-smooth Non-convex 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 DGFM and DGFM+, decentralized zeroth-order gradient-tracking methods using randomized smoothing to find (δ,ε)-Goldstein stationary points of nonsmooth nonconvex Lipschitz functions, with improved stochastic zeroth-order complexity for DGFM+.
Problem
Decentralized stochastic optimization of Lipschitz functions that are neither smooth nor convex, using only zeroth-order (function value) oracles, targeting (δ,ε)-Goldstein stationarity.
Approach
Combines randomized smoothing with gradient tracking in a decentralized setting: DGFM tracks averaged smoothed gradients via zeroth-order estimates, and DGFM+ adds periodic large-batch gradient refreshes with multi-round gossip (mixing) to reduce variance, yielding improved complexity over prior decentralized zeroth-order approaches.
Key results
- DGFM achieves (δ,ε)-Goldstein stationarity with stochastic zeroth-order complexity O(Δ δ^-1 ε^-4), per the supplementary corollary.
- DGFM+ achieves stochastic zeroth-order complexity O(Δ δ^-1 ε^-3) with communication rounds O(Δ ε^-2(ε^-1+log ε^-1)).
- The supplement proves consensus error decay and descent lemmas for both algorithms under Lipschitz and bounded-variance assumptions.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use DGFM+ with periodic gradient-estimator refresh and recursive gradient estimation instead of DGFM | Decentralized gradient-free optimization · Stochastic non-smooth non-convex optimization | stochastic zeroth-order oracle complexity: \mathcal{O}(\Delta_{\delta} \delta^{-1}\varepsilon^{-4}) -> \mcal O(\Delta_{\delta}\delta^{-1}\varepsilon^{-3}) | Helped |
Limitations
- Analysis is restricted to Lipschitz objectives and doubly stochastic mixing matrices with spectral gap assumptions as stated in the supplement.
- Experimental details are not present in the supplementary text provided.
Experimental setup
Datasets: MNIST Fashion-MNIST
Benchmarks: MNIST Fashion-MNIST
Metrics: convergence Goldstein stationarity
Builds on: randomized smoothing gradient tracking Goldstein stationarity
Closest papers by meaning
- Decentralized Convex Finite-Sum Optimization with Better Dependence on Condition Numbers (ICML 2024 · similarity 0.90)
- An Online Optimization Perspective on First-Order and Zero-Order Decentralized Nonsmooth Nonconvex Stochastic Optimization (ICML 2024 · similarity 0.90)
- Optimizing $(L_0, L_1)$-Smooth Functions by Gradient Methods (ICLR 2025 · similarity 0.89)
- Nonlinearly Preconditioned Gradient Methods under Generalized Smoothness (ICML 2025 · similarity 0.89)
- Efficiently Escaping Saddle Points under Generalized Smoothness via Self-Bounding Regularity (NeurIPS 2025 · similarity 0.89)
- Methods for Convex $(L_0,L_1)$-Smooth Optimization: Clipping, Acceleration, and Adaptivity (ICLR 2025 · similarity 0.89)
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.