Multi-Distribution Learning, for Robustness, Fairness, and Collaboration
summary
Argues that worst-case multi-distribution learning can avoid an O(K) blowup and often needs only log K dependence by recasting the problem as a min‑max game and using online tools: ERM and VC bounds for per‑distribution learning, no‑regret vs best‑response averaging to get guarantees, and refined solvers like stochastic mirror‑prox to tighten epsilon dependence. Provides concrete sample‑complexity formulas (poly(1/ε)·log K) but notes naive schemes incur worse ε rates. Highlights incentive failures: individual rationality and stable equilibria can force √K inefficiencies in some cases.
AI-written summary · about
chapters (20)
- 0:00Start
- 0:24Multi-Distribution Learning Problems
- 1:27Challenges
- 5:42What Is the Measure of Success of a Learning Algorithm
- 9:58How Should We Measure the Learning Performance across Different Tasks
- 14:12What Is Multiple Multi-Distribution Learning Problems
- 22:19Calibration Loss
- 23:31Collaborative Learning
- 24:02Agnostic Fair Federated Learning
- 24:38Group Distribution Robust Optimization
- 34:41Empirical Risk Minimization
- 37:48Vc Dimension
- 38:29Vc Dimension Bounds
- 58:23Multi-Distribution Learning as Game Solving
- 1:09:12Expected Error
- 1:10:09Sample Complexity
- 1:11:57Stochastic Mirror Prox Algorithm
- 1:15:59How Should We Procure Resources
- 1:18:51Individual Rationality
- 1:21:24What Is a Bad Case for an Equilibrium Not Existing
related talks
01h 11mA Theory of Multi-objective Machine Learning
38mMulti-objective Learning: An Algorithmic Toolbox for Optimal Predictions Anytime Anywhere!
33mDistributed Learning, Communication Complexity, and Privacy
53mDesigning Robust Learners
34mDistributional Robustness, Learning, and Empirical Likelihood
43mIs Interaction Necessary for Distributed Private Learning?
45mTesting and Learning Distributions Under Local Information Constraints
30mIndividual Statistical Fairness