Variance-Reduced Gradient Estimator for Nonconvex Zeroth-Order Distributed Optimization
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917392858218496 |
|---|---|
| author | Mu, Huaiyi Tang, Yujie Song, Jie Li, Zhongkui |
| author_facet | Mu, Huaiyi Tang, Yujie Song, Jie Li, Zhongkui |
| contents | This paper investigates distributed zeroth-order optimization for smooth nonconvex problems, targeting the trade-off between convergence rate and sampling cost per zeroth-order gradient estimation in current algorithms that use either the $2$-point or $2d$-point gradient estimators. We propose a novel variance-reduced gradient estimator that either randomly renovates a single orthogonal direction of the true gradient or calculates the gradient estimation across all dimensions for variance correction, based on a Bernoulli distribution. Integrating this estimator with gradient tracking mechanism allows us to address the trade-off. We show that the oracle complexity of our proposed algorithm is upper bounded by $O(d/ε)$ for smooth nonconvex functions and by $O(dκ\ln (1/ε))$ for smooth and gradient dominated nonconvex functions, where $d$ denotes the problem dimension and $κ$ is the condition number. Numerical simulations comparing our algorithm with existing methods confirm the effectiveness and efficiency of the proposed gradient estimator. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2409_19567 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Variance-Reduced Gradient Estimator for Nonconvex Zeroth-Order Distributed Optimization Mu, Huaiyi Tang, Yujie Song, Jie Li, Zhongkui Optimization and Control Multiagent Systems Systems and Control This paper investigates distributed zeroth-order optimization for smooth nonconvex problems, targeting the trade-off between convergence rate and sampling cost per zeroth-order gradient estimation in current algorithms that use either the $2$-point or $2d$-point gradient estimators. We propose a novel variance-reduced gradient estimator that either randomly renovates a single orthogonal direction of the true gradient or calculates the gradient estimation across all dimensions for variance correction, based on a Bernoulli distribution. Integrating this estimator with gradient tracking mechanism allows us to address the trade-off. We show that the oracle complexity of our proposed algorithm is upper bounded by $O(d/ε)$ for smooth nonconvex functions and by $O(dκ\ln (1/ε))$ for smooth and gradient dominated nonconvex functions, where $d$ denotes the problem dimension and $κ$ is the condition number. Numerical simulations comparing our algorithm with existing methods confirm the effectiveness and efficiency of the proposed gradient estimator. |
| title | Variance-Reduced Gradient Estimator for Nonconvex Zeroth-Order Distributed Optimization |
| topic | Optimization and Control Multiagent Systems Systems and Control |
| url | https://arxiv.org/abs/2409.19567 |