提出鲁棒分布式优化新方法，可逼近理论最优复杂度。
Optimal Complexity in Byzantine-Robust Distributed Stochastic Optimization with Data Heterogeneity
- 结合加速与方差缩减，设计新型抗拜占庭鲁棒算法
- 证明在异构数据下收敛误差存在理论下界
- 适用于存在恶意节点的分布式学习场景
本文针对分布式一阶随机优化在强凸与非凸情况下的拜占庭鲁棒性，建立了紧致的下界。当各节点数据异构时，收敛误差由不可消减的拜占庭误差和可趋零的优化误差两部分构成。我们推导出拜占庭误差的下界，以及达到任意小优化误差所需的最小随机梯度查询次数下界。然而，现有上界与这些下界存在显著差距。为此，我们引入Nesterov加速与方差缩减技术，提出新型拜占庭鲁棒分布式随机优化方法，其复杂度在对数因子内匹配所建下界，表明下界是紧致的。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。