# Tight Bounds for Collaborative PAC Learning via Multiplicative Weights

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

## Key facts

- Cited by 15 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 May 2018.

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

- [Collaborative Learning for Hand and Object Reconstruction with Attention-guided Graph Convolution](https://mlsanity.com/paper/2204.13062/) (2022)
- [One for One, or All for All: Equilibria and Optimality of Collaboration in Federated Learning](https://mlsanity.com/paper/2103.03228/) (2021)
- [On-Demand Sampling: Learning Optimally from Multiple Distributions](https://mlsanity.com/paper/2210.12529/) (2022)
- [Memory Bounds for Continual Learning](https://mlsanity.com/paper/2204.10830/) (2022)
- [An Equivalence Between Data Poisoning and Byzantine Gradient Attacks](https://mlsanity.com/paper/2202.08578/) (2022)
- [Optimal Multi-Distribution Learning](https://mlsanity.com/paper/2312.05134/) (2023)
- [The sample complexity of multi-distribution learning](https://mlsanity.com/paper/2312.04027/) (2023)
- [On the Convergence of the Shapley Value in Parametric Bayesian Learning Games](https://mlsanity.com/paper/2205.07428/) (2022)
- [Derandomizing Multi-Distribution Learning](https://mlsanity.com/paper/2409.17567/) (2024)
- [How Many Domains Suffice for Domain Generalization? A Tight Characterization via the Domain Shattering Dimension](https://mlsanity.com/paper/2506.16704/) (2025)
- [Collaborative Learning with Different Labeling Functions](https://mlsanity.com/paper/2402.10445/) (2024)
- [Towards Fundamental Limits for Active Multi-distribution Learning](https://mlsanity.com/paper/2506.17607/) (2025)
- [Sample-Adaptivity Tradeoff in On-Demand Sampling](https://mlsanity.com/paper/2511.15507/) (2025)
- [Is Multi-Distribution Learning as Easy as PAC Learning: Sharp Rates with Bounded Label Noise](https://mlsanity.com/paper/2602.21039/) (2026)
- [Sample Complexity of Linear Regression Models for Opinion Formation in Networks](https://mlsanity.com/paper/2311.02349/) (2023)

## Abstract (arXiv)

We study the collaborative PAC learning problem recently proposed in Blum et al.~citeBHPQ17, in which we have k players and they want to learn a target function collaboratively, such that the learned function approximates the target function well on all players' distributions simultaneously. The quality of the collaborative learning algorithm is measured by the ratio between the sample complexity of the algorithm and that of the learning algorithm for a single distribution (called the overhead). We obtain a collaborative learning algorithm with overhead O(ln k), improving the one with overhead O(ln2 k) in citeBHPQ17. We also show that an Omega(ln k) overhead is inevitable when k is polynomial bounded by the VC dimension of the hypothesis class. Finally, our experimental study has demonstrated the superiority of our algorithm compared with the one in Blum et al. on real-world datasets.