Research map / Learning theory and algorithms / Sample complexity
Collaborative Learning with Different Labeling Functions
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Studies collaborative PAC learning when distributions have different labeling functions under a (k,ε)-realizability assumption, giving an ERM-based sample-efficient learner, NP-hardness results, and polynomial-time learners for identical marginals and 2-refutable classes.
Problem
Collaborative PAC learning of n distributions when no single classifier is accurate for all of them (different labeling functions), aiming for sample-efficient and computationally efficient learning.
Approach
Replaces the common-labeling-function assumption with (k,ε)-realizability (k classifiers cover all n distributions), reduces to single-classifier learning on a (n,k)-augmented class whose VC dimension is O(kd + n log k), and gives matching-style hardness and efficient special cases via approximate graph coloring.
Key results
- Under (k,ε)-realizability, an ERM-based learner achieves sample complexity O(kd log(n/k) log(1/ε)/ε + (n log k log(1/ε) + n log(n/δ))/ε).
- ERM over the (n,k)-augmented class is NP-hard for any k≥3, and for k=2 for a specific regular hypothesis family.
- For identical marginals, a poly-time algorithm uses at most k ERM calls and achieves O(kd log(1/ε)/ε + n log(n/δ)/ε) samples; for 2-refutable classes with k=2, a coloring-based learner achieves O(((d log(1/ε)+n)/ε) log n) samples.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use ERM on the (n, k)-augmented hypothesis class under (k, ε)-realizability | Collaborative PAC learning · (k, ε)-realizable distributions | sample complexity: O(kd\log(n/k) + n\log n) | Helped |
| Learn each distribution separately instead of using collaboration | Collaborative PAC learning · n distributions | sample complexity: linear in n | Hurt |
| Assume identical marginals and use the clustering learner | Collaborative PAC learning · (k, ε)-realizable distributions with identical marginals | sample complexity: O\left(\frac{kd\log(1/\epsilon)}{\epsilon} + \frac{n\log(n/\delta)}{\epsilon}\right) | Helped |
| Use approximate coloring for a 2-refutable class with k = 2 | Collaborative PAC learning · (k, 0)-realizable distributions, k = 2 | sample complexity: O\left(\frac{d\log(1/\epsilon) + n}{\epsilon}\cdot \log n + \frac{n\log(1/\delta)}{\epsilon}\right) | Helped |
| Use approximate coloring for a 2-refutable class with fixed k ≥ 3 | Collaborative PAC learning · (k, 0)-realizable distributions, k ≥ 3 | sample complexity overhead: from \log n to \mathrm{poly}(n); sub-linear in n for any fixed k | Mixed |
Surprising findings
- ERM over the augmented class is NP-hard even for randomly drawn datasets when k≥3 (unless NP=RP).
Limitations
- Sample complexity lower bound for the (1,0)-realizable case is open, so the leading kd log(n/k)/ε term may not be tight.
- The general algorithm is computationally hard (NP-hard ERM); efficient learners exist only for special cases.
- Poly-time learner for 2-refutable classes with k≥3 has poly(n) overhead rather than polylog.
Experimental setup
Metrics: sample complexity computational complexity (NP-hardness)
Baselines: Collaborative PAC Learning (common labeling function algorithm) naive individual learning
Builds on: Collaborative PAC Learning multi-task learning realizability assumption lifelong learning algorithms
Closest papers by meaning
- Improved Algorithms for Collaborative PAC Learning (NeurIPS 2018 · similarity 0.93)
- Derandomizing Multi-Distribution Learning (NeurIPS 2024 · similarity 0.87)
- Fast Rates for Bandit PAC Multiclass Classification (NeurIPS 2024 · similarity 0.87)
- Improved Sample Complexity for Multiclass PAC Learning (NeurIPS 2024 · similarity 0.86)
- Learning Distributions from Multiple Data Providers (NeurIPS 2026 · similarity 0.85)
- A Kernel Perspective on Distillation-based Collaborative Learning (NeurIPS 2024 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.