Search papers, labs, and topics across Lattice.
This paper investigates the statistical complexity of multi-distribution learning under bounded label noise, aiming to determine if the fast rates of single-task learning extend to this setting. The authors demonstrate a lower bound showing that learning across *k* distributions incurs a slower rate scaling with *k/ε²*, even with constant noise, unless each distribution is learned independently. They introduce a structured hypothesis-testing framework to quantify the cost of certifying near-optimality under bounded noise, and show this cost is unavoidable in the multi-distribution setting.
Multi-distribution learning suffers an unavoidable $k/ε^2$ sample complexity scaling with the number of distributions, even under bounded label noise, challenging the intuition that shared structure can easily translate to faster learning.
Towards understanding the statistical complexity of learning from heterogeneous sources, we study the problem of multi-distribution learning. Given $k$ data sources, the goal is to output a classifier for each source by exploiting shared structure to reduce sample complexity. We focus on the bounded label noise setting to determine whether the fast $1/ε$ rates achievable in single-task learning extend to this regime with minimal dependence on $k$. Surprisingly, we show that this is not the case. We demonstrate that learning across $k$ distributions inherently incurs slow rates scaling with $k/ε^2$, even under constant noise levels, unless each distribution is learned separately. A key technical contribution is a structured hypothesis-testing framework that captures the statistical cost of certifying near-optimality under bounded noise-a cost we show is unavoidable in the multi-distribution setting. Finally, we prove that when competing with the stronger benchmark of each distribution's optimal Bayes error, the sample complexity incurs a \textit{multiplicative} penalty in $k$. This establishes a \textit{statistical} separation between random classification noise and Massart noise, highlighting a fundamental barrier unique to learning from multiple sources.
