Compressed Zeroth-Order Algorithm for Stochastic Distributed Nonconvex Optimization
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866914012200960000 |
|---|---|
| author | Wang, Haonan Yi, Xinlei Hong, Yiguang |
| author_facet | Wang, Haonan Yi, Xinlei Hong, Yiguang |
| contents | This paper studies the stochastic distributed nonconvex optimization problem over a network of agents, where agents only access stochastic zeroth-order information about their local cost functions and collaboratively optimize the global objective over bandwidth-limited communication networks. To mitigate communication overhead and handle the unavailability of explicit gradient information, we propose a communication compressed zeroth-order stochastic distributed (CZSD) algorithm. By integrating a generalized contractive compressor and a stochastic two-point zeroth-order oracle, CZSD achieves convergence rates comparable to its exact communication counterpart while reducing both communication overhead and sampling complexity. Specifically, to the best of our knowledge, CZSD is the first compressed zeroth-order algorithm achieving linear speedup, with convergence rates of $\mathcal{O}(\sqrt{p}/\sqrt{nT})$ and $\mathcal{O}(p/(nT))$ under general nonconvex settings and the Polyak--Łojasiewicz condition, respectively. Numerical experiments validate the algorithm's effectiveness and communication efficiency. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2503_23426 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Compressed Zeroth-Order Algorithm for Stochastic Distributed Nonconvex Optimization Wang, Haonan Yi, Xinlei Hong, Yiguang Optimization and Control This paper studies the stochastic distributed nonconvex optimization problem over a network of agents, where agents only access stochastic zeroth-order information about their local cost functions and collaboratively optimize the global objective over bandwidth-limited communication networks. To mitigate communication overhead and handle the unavailability of explicit gradient information, we propose a communication compressed zeroth-order stochastic distributed (CZSD) algorithm. By integrating a generalized contractive compressor and a stochastic two-point zeroth-order oracle, CZSD achieves convergence rates comparable to its exact communication counterpart while reducing both communication overhead and sampling complexity. Specifically, to the best of our knowledge, CZSD is the first compressed zeroth-order algorithm achieving linear speedup, with convergence rates of $\mathcal{O}(\sqrt{p}/\sqrt{nT})$ and $\mathcal{O}(p/(nT))$ under general nonconvex settings and the Polyak--Łojasiewicz condition, respectively. Numerical experiments validate the algorithm's effectiveness and communication efficiency. |
| title | Compressed Zeroth-Order Algorithm for Stochastic Distributed Nonconvex Optimization |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2503.23426 |