The Sample Complexity of Multi-Distribution Learning for VC Classes

Abstract

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 (k)(d + k) + \^-1 dk, ^-4 (k) d\), the best lower bound is (^-2(d + k (k))). We discuss recent progress on this problem and some hurdles that are fundamental to the use of game dynamics in statistical learning.

Tasks

Reproductions