Decentralized Gradient-Free Methods for Stochastic Non-Smooth Non-Convex Optimization
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2023
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866909467545698304 |
|---|---|
| author | Lin, Zhenwei Xia, Jingfan Deng, Qi Luo, Luo |
| author_facet | Lin, Zhenwei Xia, Jingfan Deng, Qi Luo, Luo |
| contents | We consider decentralized gradient-free optimization of minimizing Lipschitz continuous functions that satisfy neither smoothness nor convexity assumption. We propose two novel gradient-free algorithms, the Decentralized Gradient-Free Method (DGFM) and its variant, the Decentralized Gradient-Free Method$^+$ (DGFM$^{+}$). Based on the techniques of randomized smoothing and gradient tracking, DGFM requires the computation of the zeroth-order oracle of a single sample in each iteration, making it less demanding in terms of computational resources for individual computing nodes. Theoretically, DGFM achieves a complexity of $\mathcal O(d^{3/2}δ^{-1}\varepsilon ^{-4})$ for obtaining an $(δ,\varepsilon)$-Goldstein stationary point. DGFM$^{+}$, an advanced version of DGFM, incorporates variance reduction to further improve the convergence behavior. It samples a mini-batch at each iteration and periodically draws a larger batch of data, which improves the complexity to $\mathcal O(d^{3/2}δ^{-1} \varepsilon^{-3})$. Moreover, experimental results underscore the empirical advantages of our proposed algorithms when applied to real-world datasets. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2310_11973 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Decentralized Gradient-Free Methods for Stochastic Non-Smooth Non-Convex Optimization Lin, Zhenwei Xia, Jingfan Deng, Qi Luo, Luo Optimization and Control Distributed, Parallel, and Cluster Computing We consider decentralized gradient-free optimization of minimizing Lipschitz continuous functions that satisfy neither smoothness nor convexity assumption. We propose two novel gradient-free algorithms, the Decentralized Gradient-Free Method (DGFM) and its variant, the Decentralized Gradient-Free Method$^+$ (DGFM$^{+}$). Based on the techniques of randomized smoothing and gradient tracking, DGFM requires the computation of the zeroth-order oracle of a single sample in each iteration, making it less demanding in terms of computational resources for individual computing nodes. Theoretically, DGFM achieves a complexity of $\mathcal O(d^{3/2}δ^{-1}\varepsilon ^{-4})$ for obtaining an $(δ,\varepsilon)$-Goldstein stationary point. DGFM$^{+}$, an advanced version of DGFM, incorporates variance reduction to further improve the convergence behavior. It samples a mini-batch at each iteration and periodically draws a larger batch of data, which improves the complexity to $\mathcal O(d^{3/2}δ^{-1} \varepsilon^{-3})$. Moreover, experimental results underscore the empirical advantages of our proposed algorithms when applied to real-world datasets. |
| title | Decentralized Gradient-Free Methods for Stochastic Non-Smooth Non-Convex Optimization |
| topic | Optimization and Control Distributed, Parallel, and Cluster Computing |
| url | https://arxiv.org/abs/2310.11973 |