The Sample Complexity of Multi-Distribution Learning for VC Classes

2023/07/22 by Pranjal Awasthi, Nika Haghtalab, Awasthi, Pranjal +3
Computer Science · #FOS: Computer and information sciences #Imbalanced Data Classification Techniques #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Machine Learning and Algorithms #Machine Learning and Data Classification

paper · pdf · doi:10.48550/arxiv.2307.12135

openalex publication_date 2023/07/22 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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 ln(k)(d + k) + min\ε^-1 dk, ε^-4 ln(k) d\), the best lower bound is Ω(ε^-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.

Related

• The sample complexity of multi-distribution learning
• Towards Fundamental Limits for Active Multi-distribution Learning
• Impossibility of Characterizing Distribution Learning -- a simple solution to a long-standing problem
• Tight Bounds for Collaborative PAC Learning via Multiplicative Weights
• Optimal Multi-Distribution Learning