Distributed Statistical Min-Max Learning in the Presence of Byzantine Agents
Authors:
- 6 December 2022
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 4179-4184
Abstract
Recent years have witnessed a growing interest in the topic of min-max optimization, owing to its relevance in the context of generative adversarial networks (GANs), robust control and optimization, and reinforcement learning. Motivated by this line of work, we consider a multi-agent min-max learning problem, and focus on the emerging challenge of contending with worst-case Byzantine adversarial agents in such a setup. By drawing on recent results from robust statistics, we design a robust distributed variant of the extragradient algorithm - a popular algorithmic approach for min-max optimization. Our main contribution is to provide a crisp analysis of the proposed robust extra-gradient algorithm for smooth convex-concave and smooth strongly convex-strongly concave functions. Specifically, we establish statistical rates of convergence to approximate saddle points. Our rates are near-optimal, and reveal both the effect of adversarial corruption and the benefit of collaboration among the non-faulty agents. Notably, this is the first paper to provide formal theoretical guarantees for large-scale distributed min-max learning in the presence of adversarial agents.Keywords
All Related Versions
Funding Information
- Air Force Office of Scientific Research
This publication has 16 references indexed in Scilit:
- Probability2019
- High-Dimensional Robust Mean Estimation in Nearly-Linear Time2019
- Distributed Optimization Under Adversarial NodesIEEE Transactions on Automatic Control, 2018
- Distributed Statistical Machine Learning in Adversarial SettingsProceedings of the ACM on Measurement and Analysis of Computing Systems, 2017
- Fault-Tolerant Multi-Agent Optimization2016
- Robust Optimization2009
- Subgradient Methods for Saddle-Point ProblemsJournal of Optimization Theory and Applications, 2009
- Prediction, Learning, and Games2006
- Prox-Method with Rate of Convergence O(1/t) for Variational Inequalities with Lipschitz Continuous Monotone Operators and Smooth Convex-Concave Saddle Point ProblemsSIAM Journal on Optimization, 2004
- Robust Estimation of a Location Parameter1992