Research map / Learning theory and algorithms / Sample complexity
Learning Distributions from Multiple Data Providers
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 distribution learning in total variation from conditional samples restricted to a fixed family of queryable sets, characterizing learnability via the co-occurrence graph and giving tight sample complexity rates ranging from near-linear to quadratic in the domain size.
Problem
Learning an unknown discrete distribution on [n] when the learner can only obtain conditional samples from a fixed family of provider sets; determining which overlap structures make learning possible and what the optimal sample complexity is.
Approach
Characterizes PAC learnability and pointwise consistency by connectivity/completeness of the co-occurrence graph of the query family; shows sample complexity is not determined by learnability alone, with near-linear rates under hierarchical comparability and a continuum of polynomial rates n^{1+gamma} for complete families.
Key results
- Every complete co-occurrence query family admits PAC sample complexity O~(n^2/eps^2) via a simulated Markov chain, and a hub-dominated family shows this is tight in the worst case (Omega(n^2/eps^2)).
- Under hierarchical comparability (including pairwise queries), PAC sample complexity is O~(n/eps^2) with (log n)^2 factors.
- With all subsets queryable or [n] in the family, the optimal rate is Theta(n/eps^2); for every alpha in (1,2) there is a complete family with rate O~(n^alpha/eps^2).
Surprising findings
- Completeness of the co-occurrence graph is necessary and sufficient for PAC learning, yet among learnable families the optimal sample complexity can be quadratic rather than linear in n.
Limitations
- Stylized finite discrete setting with an abstract query model; not directly tested on real data or models.
- Upper bounds carry log factors (e.g., (log m)^2 for hierarchical families) that are not tight.
- Analysis restricted to total variation loss and a fixed known query family.
Experimental setup
Metrics: total variation distance sample complexity
Baselines: ordinary sampling over [n] complete-graph Markov chain learner
Builds on: COND conditional sampling model Luce choice rule Bradley-Terry-Luce model Fano inequality
Closest papers by meaning
- Scale-Sensitive Shattering: Learnability and Evaluability at Optimal Scale (NeurIPS 2026 · similarity 0.86)
- Distribution Learning Meets Graph Structure Sampling (NeurIPS 2025 · similarity 0.85)
- Collaborative Learning with Different Labeling Functions (ICML 2024 · similarity 0.85)
- Optimal Sample Complexity of Contrastive Learning (ICLR 2024 · similarity 0.85)
- Algorithms and SQ Lower Bounds for Robustly Learning Real-valued Multi-Index Models (NeurIPS 2025 · similarity 0.85)
- Computationally Efficient Replicable Learning of Parities and Applications (NeurIPS 2026 · similarity 0.84)
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.