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

作者：Jie Hou, Xia Jiang, Xianlin Zeng, Lulu Zhao, J. Shen J.F. Sun · 发表于：IEEE Transactions on Signal and Information Processing over Networks · 年份：2026 · DOI：10.1109/tsipn.2026.3682867 · 研究领域：Stochastic Gradient Optimization Techniques、Distributed Control Multi-Agent Systems、Risk and Portfolio Optimization

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$(\delta,\epsilon)$-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$\mathcal {O}(d^{3/8} \delta ^{-1/4}T^{-1/4})$to a$(\delta,\epsilon)$-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$\mathcal {O}(d^{1/3} \delta ^{-1/2}T^{-1/3})$and enhancing the function query complexity to$\mathcal {O}(d^{3/2} \delta ^{-4/3} \epsilon ^{-4})$. Finally, we demonstrate the efficacy of our algorithms through several numerical experiments.