Near-Optimal Resilient Aggregation Rules for Distributed Learning Using 1-Center and 1-Mean Clustering with Outliers

Abstract

Byzantine machine learning has garnered considerable attention in light of the unpredictable faults that can occur in large-scale distributed learning systems. The key to secure resilience against Byzantine machines in distributed learning is resilient aggregation mechanisms. Although abundant resilient aggregation rules have been proposed, they are designed in ad-hoc manners, imposing extra barriers on comparing, analyzing, and improving the rules across performance criteria. This paper studies near-optimal aggregation rules using clustering in the presence of outliers. Our outlier-robust clustering approach utilizes geometric properties of the update vectors provided by workers. Our analysis show that constant approximations to the 1-center and 1-mean clustering problems with outliers provide near-optimal resilient aggregators for metric-based criteria, which have been proven to be crucial in the homogeneous and heterogeneous cases respectively. In addition, we discuss two contradicting types of attacks under which no single aggregation rule is guaranteed to improve upon the naive average. Based on the discussion, we propose a two-phase resilient aggregation framework. We run experiments for image classification using a non-convex loss function. The proposed algorithms outperform previously known aggregation rules by a large margin with both homogeneous and heterogeneous data distributions among non-faulty workers. Code and appendix are available at https://github.com/jerry907/AAAI24-RASHB.

17 pages, 4 figures. Accepted by the 38th Annual AAAI Conference on Artificial Intelligence (AAAI'24)

References in corpus (19)

• Measuring the Effects of Non-Identical Data Distribution for Federated Visual Classification
• Byzantine-Robust Distributed Learning: Towards Optimal Statistical Rates
• The Hidden Vulnerability of Distributed Learning in Byzantium
• Robust Federated Learning in a Heterogeneous Environment
• Distributed Statistical Machine Learning in Adversarial Settings: Byzantine Gradient Descent
• Fall of Empires: Breaking Byzantine-tolerant SGD by Inner Product Manipulation
• Learning from History for Byzantine Robust Optimization
• RSA: Byzantine-Robust Stochastic Aggregation Methods for Distributed Learning from Heterogeneous Datasets
• Byzantine-Resilient Non-Convex Stochastic Gradient Descent
• Byzantine-Robust Learning on Heterogeneous Datasets via Bucketing
• Back to the Drawing Board: A Critical Evaluation of Poisoning Attacks on Production Federated Learning
• Byzantine Machine Learning Made Easy by Resilient Averaging of Momentums
• Approximate Byzantine Fault-Tolerance in Distributed Optimization
• Fixing by Mixing: A Recipe for Optimal Byzantine ML under Heterogeneity
• PRIOR: Personalized Prior for Reactivating the Information Overlooked in Federated Learning
• Grundy Distinguishes Treewidth from Pathwidth
• Clustering What Matters: Optimal Approximation for Clustering with Outliers
• On the Privacy-Robustness-Utility Trilemma in Distributed Learning
• Deterministic $O(1)$-Approximation Algorithms to 1-Center Clustering with Outliers