Research map / Learning theory and algorithms / Sample complexity
Derandomizing Multi-Distribution Learning
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.
Shows that derandomizing multi-distribution learning is NP-hard in general via discrepancy minimization, and gives a black-box algorithm converting randomized multi-distribution learners into deterministic predictors for label-consistent distributions over finite domains.
Problem
Multi-distribution (collaborative) agnostic learning outputs randomized predictors, but a single deterministic classifier is desired that performs well simultaneously across k distributions; the question is whether this derandomization is computationally and statistically feasible.
Approach
Reduces derandomization hardness to discrepancy minimization (NP-hard) for general distributions, and for label-consistent distributions uses a bias-based split: heavily biased points are fixed by majority vote from samples, while lightly biased points are randomly rounded using concentration (Hoeffding, later r-wise independent hashing) so a deterministic classifier retains the randomized guarant
Key results
- Shows NP-hardness: unless BPP = NP, deterministic derandomization of multi-distribution learning requires super-polynomial training or evaluation time for any VC class where shattered points can be found in polynomial time, even with efficient ERM and known distributions.
- For label-consistent distributions over finite domains, a black-box algorithm converts any randomized multi-distribution learner with m samples into a deterministic classifier with sample complexity m(k,d,OPT,eps/2,delta/2)+O(k ln^2(k/(eps delta))/eps^2).
- With r-wise independent hashing the storage overhead is only O(ln(n/delta) ln(|X| ln(k/delta)/eps)) extra bits, making the derandomized predictor polynomial-time when combined with the O~((d+k)/eps^2) learner.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Derandomize the randomized predictor using the label-consistency condition | Randomized multi-distribution learner · Label-consistent multi-distribution learning | worst-case error: \mathrm{OPT} + \varepsilon/2 -> \mathrm{OPT} + \varepsilon | Helped |
| Require label consistency across distributions | Multi-distribution learning · Label-consistent multi-distribution learning | deterministic learnability | Helped |
| Replace independent random rounding with r-wise independent hash rounding (ablation) | DeterministicLearner · Label-consistent multi-distribution learning | sample complexity: O(k\ln^2(k/(\varepsilon \delta))/\varepsilon^2) -> O(k\ln^3(k/(\varepsilon \delta))/\varepsilon^2) | Hurt |
| Use randomized rather than deterministic predictors in the general multi-distribution setting | Multi-distribution learning · General multi-distribution learning | training time or evaluation time: n^{\omega(1)} | Helped |
Surprising findings
- Simple majority-vote aggregation of ERM predictors cannot be made sample- and oracle-efficient in polynomial time for general distributions, unless BPP = NP.
- Randomized predictors can have a factor-k gap in worst-case error versus a single sampled predictor, so naive sampling-based derandomization is inadequate.
Limitations
- Derandomization algorithm requires label-consistent distributions and a finite input domain X; extension to infinite domains is only sketched.
- Hardness is worst-case and holds only under the assumption BPP != NP; the positive result's sample and time overheads add logarithmic factors.
- Storage of the output classifier can be large (F plus hash function), and the sampling step adds cost in |X| without the hashing trick.
Experimental setup
Baselines: randomized multi-distribution learners (e.g., oracle-efficient algorithm with O~
Builds on: multi-distribution learning agnostic PAC learning Hoeffding inequality
Closest papers by meaning
- Collaborative Learning with Different Labeling Functions (ICML 2024 · similarity 0.87)
- Iterative Chow Filtering for Learning with Distribution Shift (NeurIPS 2026 · similarity 0.84)
- Tolerant Algorithms for Learning with Arbitrary Covariate Shift (NeurIPS 2024 · similarity 0.84)
- Learning Distributions from Multiple Data Providers (NeurIPS 2026 · similarity 0.83)
- The Power of Random Features and the Limits of Distribution-Free Gradient Descent (ICML 2025 · similarity 0.83)
- It's My Data Too: Private ML for Datasets with Multi-User Training Examples (ICML 2025 · similarity 0.83)
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.