Optimal Complexity in Byzantine-Robust Distributed Stochastic Optimization with Data Heterogeneity
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917963383177216 |
|---|---|
| author | Shi, Qiankun Peng, Jie Yuan, Kun Wang, Xiao Ling, Qing |
| author_facet | Shi, Qiankun Peng, Jie Yuan, Kun Wang, Xiao Ling, Qing |
| contents | In this paper, we establish tight lower bounds for Byzantine-robust distributed first-order stochastic optimization methods in both strongly convex and non-convex stochastic optimization. We reveal that when the distributed nodes have heterogeneous data, the convergence error comprises two components: a non-vanishing Byzantine error and a vanishing optimization error. We establish the lower bounds on the Byzantine error and on the minimum number of queries to a stochastic gradient oracle required to achieve an arbitrarily small optimization error. Nevertheless, we identify significant discrepancies between our established lower bounds and the existing upper bounds. To fill this gap, we leverage the techniques of Nesterov's acceleration and variance reduction to develop novel Byzantine-robust distributed stochastic optimization methods that provably match these lower bounds, up to logarithmic factors, implying that our established lower bounds are tight. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2503_16337 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Optimal Complexity in Byzantine-Robust Distributed Stochastic Optimization with Data Heterogeneity Shi, Qiankun Peng, Jie Yuan, Kun Wang, Xiao Ling, Qing Optimization and Control Machine Learning In this paper, we establish tight lower bounds for Byzantine-robust distributed first-order stochastic optimization methods in both strongly convex and non-convex stochastic optimization. We reveal that when the distributed nodes have heterogeneous data, the convergence error comprises two components: a non-vanishing Byzantine error and a vanishing optimization error. We establish the lower bounds on the Byzantine error and on the minimum number of queries to a stochastic gradient oracle required to achieve an arbitrarily small optimization error. Nevertheless, we identify significant discrepancies between our established lower bounds and the existing upper bounds. To fill this gap, we leverage the techniques of Nesterov's acceleration and variance reduction to develop novel Byzantine-robust distributed stochastic optimization methods that provably match these lower bounds, up to logarithmic factors, implying that our established lower bounds are tight. |
| title | Optimal Complexity in Byzantine-Robust Distributed Stochastic Optimization with Data Heterogeneity |
| topic | Optimization and Control Machine Learning |
| url | https://arxiv.org/abs/2503.16337 |