# Towards Fundamental Limits for Active Multi-distribution Learning

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 23 of its 58 references that are in the map.
- First posted on arXiv 21 Jun 2025.

## Builds on (most cited first, 23 of 23)

- [Deep Bayesian Active Learning with Image Data](https://mlsanity.com/paper/1703.02910/) (2017)
- [Agnostic Federated Learning](https://mlsanity.com/paper/1902.00146/) (2019)
- [Distributionally Robust Federated Averaging](https://mlsanity.com/paper/2102.12660/) (2021)
- [Fairness-aware Agnostic Federated Learning](https://mlsanity.com/paper/2010.05057/) (2020)
- [Minimax Analysis of Active Learning](https://mlsanity.com/paper/1410.0996/) (2014)
- [Multi-group Agnostic PAC Learnability](https://mlsanity.com/paper/2105.09989/) (2021)
- [Active Learning for Cost-Sensitive Classification](https://mlsanity.com/paper/1703.01014/) (2017)
- [On-Demand Sampling: Learning Optimally from Multiple Distributions](https://mlsanity.com/paper/2210.12529/) (2022)
- [Active classification with comparison queries](https://mlsanity.com/paper/1704.03564/) (2017)
- [Beyond Disagreement-based Agnostic Active Learning](https://mlsanity.com/paper/1407.2657/) (2014)
- [Efficient Active Learning with Abstention](https://mlsanity.com/paper/2204.00043/) (2022)
- [Improved Algorithms for Collaborative PAC Learning](https://mlsanity.com/paper/1805.08356/) (2018)
- [The Power of Comparisons for Actively Learning Linear Classifiers](https://mlsanity.com/paper/1907.03816/) (2019)
- [Efficient and Parsimonious Agnostic Active Learning](https://mlsanity.com/paper/1506.08669/) (2015)
- [Tight Bounds for Collaborative PAC Learning via Multiplicative Weights](https://mlsanity.com/paper/1805.09217/) (2018)
- [Optimal Multi-Distribution Learning](https://mlsanity.com/paper/2312.05134/) (2023)
- [Selective Sampling and Imitation Learning via Online Regression](https://mlsanity.com/paper/2307.04998/) (2023)
- [The sample complexity of multi-distribution learning](https://mlsanity.com/paper/2312.04027/) (2023)
- [A Compression Technique for Analyzing Disagreement-Based Active Learning](https://mlsanity.com/paper/1404.1504/) (2014)
- [Diameter-Based Active Learning](https://mlsanity.com/paper/1702.08553/) (2017)
- [Agnostic Multi-Group Active Learning](https://mlsanity.com/paper/2306.01922/) (2023)
- [A Competitive Algorithm for Agnostic Active Learning](https://mlsanity.com/paper/2310.18786/) (2023)
- [Distribution-Dependent Rates for Multi-Distribution Learning](https://mlsanity.com/paper/2312.13130/) (2023)

## Built on by (most cited first, 1 of 1)

- [Is Multi-Distribution Learning as Easy as PAC Learning: Sharp Rates with Bounded Label Noise](https://mlsanity.com/paper/2602.21039/) (2026)

## Abstract (arXiv)

Multi-distribution learning extends agnostic Probably Approximately Correct (PAC) learning to the setting in which a family of k distributions, Dii∈[k], is considered and a classifier's performance is measured by its error under the worst distribution. This problem has attracted a lot of recent interests due to its applications in collaborative learning, fairness, and robustness. Despite a rather complete picture of sample complexity of passive multi-distribution learning, research on active multi-distribution learning remains scarce, with algorithms whose optimality remaining unknown. In this paper, we develop new algorithms for active multi-distribution learning and establish improved label complexity upper and lower bounds, in distribution-dependent and distribution-free settings. Specifically, in the near-realizable setting we prove an upper bound of widetildeOBigl(θmax(d+k)lnfrac1varepsilonBigr) and widetildeOBigl(θmax(d+k)Bigl(lnfrac1varepsilon+fracnu2varepsilon2Bigr)+fracknuvarepsilon2Bigr) in the realizable and agnostic settings respectively, where θmax is the maximum disagreement coefficient among the k distributions, d is the VC dimension of the hypothesis class, nu is the multi-distribution error of the best hypothesis, and varepsilon is the target excess error. Moreover, we show that the bound in the realizable setting is information-theoretically optimal and that the knu/varepsilon2 term in the agnostic setting is fundamental for proper learners. We also establish instance-dependent sample complexity bound for passive multidistribution learning that smoothly interpolates between realizable and agnostic regimes~citepblum2017collaborative,zhang2024optimal, which may be of independent interest.