# The Sample Complexity of Multi-Distribution Learning for VC Classes

arXiv: https://arxiv.org/abs/2307.12135 · HTML: https://mlsanity.com/paper/2307.12135/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- First posted on arXiv 22 Jul 2023.

## Abstract (arXiv)

Multi-distribution learning is a natural generalization of PAC learning to settings with multiple data distributions. There remains a significant gap between the known upper and lower bounds for PAC-learnable classes. In particular, though we understand the sample complexity of learning a VC dimension d class on k distributions to be O(ε-2 ln(k)(d + k) + minε-1 dk, ε-4 ln(k) d), the best lower bound is Omega(ε-2(d + k ln(k))). We discuss recent progress on this problem and some hurdles that are fundamental to the use of game dynamics in statistical learning.