Distributed Stochastic Zeroth-Order Optimization With Compressed Communication

The dual challenges of high communication costs and gradient inaccessibility–common in privacy-sensitive systems or black-box environments–drive our work on communication-constrained, gradient-free distributed optimization. We propose a compressed distributed stochastic zeroth-order algorithm (Com-DSZO), which requires only two function evaluations per iteration and incorporates general compression operators. Rigorous analysis establishes a sublinear convergence rate for both smooth and nonsmooth objectives, explicitly characterizing the trade-off between compression and convergence. Furthermore, we develop a variance-reduced variant (VR-Com-DSZO) under stochastic mini-batch feedback. The effectiveness of the proposed algorithms is demonstrated through numerical experiments.