Optimal Complexity in Byzantine-Robust Distributed Stochastic Optimization with Data Heterogeneity
This addresses the problem of robust distributed optimization in adversarial settings for machine learning and systems researchers, providing foundational theoretical insights.
The paper establishes tight lower bounds for Byzantine-robust distributed stochastic optimization with heterogeneous data, revealing a non-vanishing Byzantine error and a vanishing optimization error, and develops novel methods that match these bounds up to logarithmic factors.
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.