TY - JOUR
T1 - Distributed Nonsmooth Nonconvex Optimization
T2 - Deterministic and Stochastic Zeroth-Order Algorithms with Decaying Step Sizes
AU - Hou, Jie
AU - Jiang, Xia
AU - Zeng, Xianlin
AU - Zhao, Lulu
AU - Sun, Jian
N1 - Publisher Copyright:
© 2015 IEEE All rights reserved.
PY - 2026
Y1 - 2026
N2 - 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(d3/8δ−1/4T−1/4) 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(d1/3δ−1/2T−1/3) and enhancing the function query complexity to O(d3/2δ−4/3ϵ−4). Finally, we demonstrate the efficacy of our algorithms through several numerical experiments.
AB - 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(d3/8δ−1/4T−1/4) 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(d1/3δ−1/2T−1/3) and enhancing the function query complexity to O(d3/2δ−4/3ϵ−4). Finally, we demonstrate the efficacy of our algorithms through several numerical experiments.
KW - Distributed optimization
KW - Non-asymptotic convergence
KW - Nonsmooth nonconvex optimization
KW - Stochastic optimization
KW - Zeroth-order algorithms
UR - https://www.scopus.com/pages/publications/105037045095
U2 - 10.1109/TSIPN.2026.3682867
DO - 10.1109/TSIPN.2026.3682867
M3 - Article
AN - SCOPUS:105037045095
SN - 2373-776X
JO - IEEE Transactions on Signal and Information Processing over Networks
JF - IEEE Transactions on Signal and Information Processing over Networks
ER -