Distributed Nonsmooth Nonconvex Optimization: Deterministic and Stochastic Zeroth-Order Algorithms with Decaying Step Sizes

This paper addresses distributed nonsmooth nonconvex optimization over time-varying networks. Unlike prior works, we consider a more general formulation that does not require the nonsmooth nonconvex objective function to possess composite structures. While existing algorithms for such problems typically provide asymptotic convergence guarantees, we establish non-asymptotic rates and oracle complexities by introducing the (δ, ϵ)-Goldstein stationarity. For the deterministic setting, we propose a Distributed Zeroth-Order algorithm over Time-Varying networks (DZO-TV) with a decaying step size. Combining the averaged consensus protocol, randomized smoothing, and two-point function queries, the algorithm achieves a sublinear convergence rate of O(d³/⁸δ⁻¹/⁴T⁻¹/⁴⁾ to a (δ, ϵ)Goldstein stationary point. For the stochastic setting, we develop a stochastic variant (DStoZO-TV) that employs either increasing-batch or single-batch data sampling, achieving an improved convergence rate of O(d¹/³δ⁻¹/²T⁻¹/³⁾ and enhancing the function query complexity to O(d³/²δ⁻⁴/³ϵ⁻⁴). Finally, we demonstrate the efficacy of our algorithms through several numerical experiments.