The sample complexity of multi-distribution learning

2023/12/07 by Peng, Binghui · 2 citations
#Artificial Intelligence (cs.AI) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML)

paper · doi:10.48550/arxiv.2312.04027

Abstract

Multi-distribution learning generalizes the classic PAC learning to handle data coming from multiple distributions. Given a set of k data distributions and a hypothesis class of VC dimension d, the goal is to learn a hypothesis that minimizes the maximum population loss over k distributions, up to ε additive error. In this paper, we settle the sample complexity of multi-distribution learning by giving an algorithm of sample complexity \widetildeO((d+k)ε^-2) ⋅ (k/ε)^o(1). This matches the lower bound up to sub-polynomial factor and resolves the COLT 2023 open problem of Awasthi, Haghtalab and Zhao [AHZ23].

Cited by

• Optimal Deterministic Multicalibration and Omniprediction
• Sample-Adaptivity Tradeoff in On-Demand Sampling

Related

• The Sample Complexity of Multi-Distribution Learning for VC Classes
• Optimal Multi-Distribution Learning
• Towards Fundamental Limits for Active Multi-distribution Learning
• Derandomizing Multi-Distribution Learning
• Sample-Efficient Learning of Mixtures