Decentralized Nonsmooth Nonconvex Optimization with Client Sampling

Abstract

This paper considers decentralized nonsmooth nonconvex optimization problem with Lipschitz continuous local functions. We propose an efficient stochastic first-order method with client sampling, achieving the $(\delta ,ϵ)$-Goldstein stationary point with the overall sample complexity of $\mathcal{O}({\delta }^{-1}{ϵ}^{-3})$, the computation rounds of $\mathcal{O}({\delta }^{-1}{ϵ}^{-3})$, and the communication rounds of $\tilde{\mathcal{O}}({\gamma }^{-1/2}{\delta }^{-1}{ϵ}^{-3})$, where $\gamma$ is the spectral gap of the mixing matrix for the network. Our results achieve the optimal sample complexity and the sharper communication complexity than existing methods. We also extend our ideas to zeroth-order optimization. Moreover, the numerical experiments show the empirical advantage of our methods.