Distributed Zeroth-Order Composite Finite-Sum Optimization via Incremental Variance Reduction
Abstract
We study decentralized composite finite-sum optimization over a fixed connected undirected network, where agents access local component functions through function evaluations and share a possibly nonsmooth convex regularizer. In this setting, standard two-point gradient estimators can retain nonvanishing variance at a solution, complicating their integration with gradient tracking. We propose Distributed Zeroth-Order Incremental Variance Reduction (Distributed ZIVR), which combines incrementally updated component-gradient estimates with a proximal gradient-tracking scheme. The method admits an implementation using a constant number of function evaluations per agent at every iteration, without intermittent full-component or full-coordinate refreshes. For convex smooth component functions and strongly convex local averages, we establish linear convergence up to a controllable finite-difference error. With the finite-difference radius chosen for the target accuracy, Chebyshev-accelerated mixing yields a per-agent oracle complexity of Õ(d(m+κ)log(1/ε)) for expected squared solution error ε, where d is the dimension, m is the number of components per agent, and κ is the condition number. This matches the centralized ZIVR oracle bound, while the communication bound has only an inverse square-root dependence on the network spectral gap. Experiments on logistic and robust regression demonstrate rapid reduction of solution and consensus errors.
Related
- Revisiting Distributed Sign-Based Variance Reduction
- Optimistic Gradient Algorithms with Randomized Coordinate and Variance Reduction Strategies for Composite Inclusions
- Variance Reduction with Delayed Feedback for Non-Convex Optimization
- Variance Reduction for Decentralized Stochastic Optimization with Multiple Local Updates
- Lower Bounds for Stochastic First-Order Algorithms with Variance Reduction in Nonconvex--Concave Minimax Optimization
BibTeX
@misc{zhang2026distributed,
title = {{Distributed Zeroth-Order Composite Finite-Sum Optimization via Incremental Variance Reduction}},
author = {Silan Zhang and Yujie Tang},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.41615},
eprint = {2610.41615},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.41615},
}
RIS
TY - UNPB
TI - Distributed Zeroth-Order Composite Finite-Sum Optimization via Incremental Variance Reduction
AU - Silan Zhang
AU - Yujie Tang
PY - 2026
DA - 2026/10/30
PB - arXiv
DO - 10.48550/arxiv.2610.41615
UR - https://arxiv.org/abs/2610.41615
AB - We study decentralized composite finite-sum optimization over a fixed connected undirected network, where agents access local component functions through function evaluations and share a possibly nonsmooth convex regularizer. In this setting, standard two-point gradient estimators can retain nonvanishing variance at a solution, complicating their integration with gradient tracking. We propose Distributed Zeroth-Order Incremental Variance Reduction (Distributed ZIVR), which combines incrementally updated component-gradient estimates with a proximal gradient-tracking scheme. The method admits an implementation using a constant number of function evaluations per agent at every iteration, without intermittent full-component or full-coordinate refreshes. For convex smooth component functions and strongly convex local averages, we establish linear convergence up to a controllable finite-difference error. With the finite-difference radius chosen for the target accuracy, Chebyshev-accelerated mixing yields a per-agent oracle complexity of Õ(d(m+κ)log(1/ε)) for expected squared solution error ε, where d is the dimension, m is the number of components per agent, and κ is the condition number. This matches the centralized ZIVR oracle bound, while the communication bound has only an inverse square-root dependence on the network spectral gap. Experiments on logistic and robust regression demonstrate rapid reduction of solution and consensus errors.
ER -