A zeroth-order variance-reduced method for decentralized stochastic non-convex optimization
Hongxu Chen, Jinchi Chen, Ke Yu Wei · Optimization · 2025
In this paper, we consider a distributed stochastic non-convex optimization problem, which is about minimizing a sum of n local cost functions over a network with only zeroth-order information. A novel single-loop Decentralized Zeroth-Order Variance Reduction algorithm, called DZOVR, is proposed, which achieves O(dn−1ϵ−3) sample complexity at each node to reach an ϵ-accurate stationary point and also exhibits network-independent and linear speedup properties. To the best of our knowledge, this is the first stochastic decentralized zeroth-order algorithm that achieves this sample complexity in smooth setting. Numerical experiments demonstrate that DZOVR outperforms the other state-of-the-art algorithms and has network-independent and linear speedup properties.