Learning Distributions from Multiple Data Providers

arXiv:2607.24732 · cs.DS, cs.GT, cs.LG, stat.ML · Submitted 2026-07-27 · Read on arXiv

Jon Kleinberg, Amin Saberi, Xizhi Tan, Grigoris Velegkas

cs.DS, cs.GT, cs.LG, stat.ML

Submitted: 2026-07-27

License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/

Terminology

• Sample Complexity — 27× in this paper · explained in 20 episodes
• Consistency — 17× in this paper · explained in 3 episodes
• Editor — 9× in this paper · explained in 2 episodes
• Mutual Information — 7× in this paper · explained in 2 episodes
• Accuracy — 4× in this paper · explained in 1 episode
• Benchmark — 4× in this paper · explained in 2 episodes
• Query Complexity — 4× in this paper · explained in 2 episodes
• Hamming Distance — 3× in this paper · explained in 2 episodes
• Hypergraph — 3× in this paper · explained in 2 episodes
• Pairwise Comparisons — 3× in this paper · explained in 2 episodes
• Redundancy — 3× in this paper · explained in 2 episodes
• Spectral Gap — 3× in this paper · explained in 6 episodes
• Sample Complexity Bounds — 2× in this paper · explained in 4 episodes
• Structural Properties — 2× in this paper · explained in 2 episodes
• Sufficiency — 2× in this paper · explained in 2 episodes
• VC Dimension — 2× in this paper · explained in 2 episodes
• Adam — 1× in this paper · explained in 3 episodes
• Clarity — 1× in this paper · explained in 3 episodes
• Coarse-Graining — 1× in this paper · explained in 3 episodes
• Error Decomposition — 1× in this paper · explained in 4 episodes
• Generalization — 1× in this paper · explained in 14 episodes
• Generative Model — 1× in this paper · explained in 2 episodes
• Generative Modeling — 1× in this paper · explained in 3 episodes
• Generative Models — 1× in this paper · explained in 3 episodes
• Hierarchical Structure — 1× in this paper · explained in 3 episodes
• Kullback–Leibler Divergence — 1× in this paper · explained in 2 episodes
• Localization — 1× in this paper · explained in 2 episodes
• Selection Bias — 1× in this paper · explained in 5 episodes

Sources

• A short note on learning discrete distributions
• Bernstein's inequalities for general Markov chains

Related papers

• Cascaded Learned Bloom Filter for Optimizing Model-Filter Size Balance and Fast Rejection
• Computational and Statistical Hardness of Calibration Distance
• Edge-Private Matching Kernels Through Local Decoding
• Tight Bounds for Equivalence Testing with Non-Adaptive Conditional Samples
• Local Node Differential Privacy
• Cheaper by the Batch: Shared Traversal for Genotype Graph Editing