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. 

© 2026 IEEE. All rights reserved, including rights for text and data mining, and training of artificial intelligence and similar technologies. Personal use is permitted, but republication/redistribution requires IEEE permission.