On-Demand Sampling: Learning Optimally from Multiple Distributions
Preprint
Abstract
Social and real-world considerations such as robustness, fairness, social welfare and multi-agent tradeoffs have given rise to multi-distribution learning paradigms, such as collaborative learning, group distributionally robust optimization, and fair federated learning. In each of these settings, a learner seeks to uniformly minimize its expected loss over $n$ predefined data distributions, while using as few samples as possible. In this paper, we establish the optimal sample complexity of these learning paradigms and give algorithms that meet this sample complexity. Importantly, our sample complexity bounds for multi-distribution learning exceed that of learning a single distribution by only an additive factor of $n \log(n) / \epsilon^2$. This improves upon the best known sample complexity bounds for fair federated learning by Mohri et al. and collaborative learning by Nguyen and Zakynthinou by multiplicative factors of $n$ and $\log(n)/\epsilon^3$, respectively. We also provide the first sample complexity bounds for the group DRO objective of Sagawa et al. To guarantee these optimal sample complexity bounds, our algorithms learn to sample from data distributions on demand. Our algorithm design and analysis are enabled by our extensions of online learning techniques for solving stochastic zero-sum games. In particular, we contribute stochastic variants of no-regret dynamics that can trade off between players' differing sampling costs.
Keywords
All Related Versions
This publication has 7 references indexed in Scilit:
- Learning models with uniform performance via distributionally robust optimizationThe Annals of Statistics, 2021
- Distributed Optimization and Statistical Learning via the Alternating Direction Method of MultipliersFoundations and Trends in Machine Learning, 2011
- Quantized incremental algorithms for distributed optimizationIEEE Journal on Selected Areas in Communications, 2005
- Mirror descent and nonlinear projected subgradient methods for convex optimizationOperations Research Letters, 2003
- A Simple Adaptive Procedure Leading to Correlated EquilibriumEconometrica, 2000
- A Decision-Theoretic Generalization of On-Line Learning and an Application to BoostingJournal of Computer and System Sciences, 1997
- A general lower bound on the number of examples needed for learningInformation and Computation, 1989