Research map / Learning theory and algorithms / Sample complexity
Communication-Efficient Distributed Learning of Discrete Distributions
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's title only (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use structured (k-histogram) learning protocols instead of sending full samples | k-histogram distributions · l1 and l2 distributed density estimation | communication bits | Helped |
| unstructured distributions with one sample per player (no structure exploited) | unstructured discrete distributions · s=1, blackboard model, l1 | communication bits | No clear effect |
| top-down splitting algorithm for l2 histograms instead of bottom-up | k-histogram l2 learner · l2 distributed histogram learning | communication bits | Helped |
| black-box reduction replacing domain size n with O(k/ε) at additive cost k/ε log n | k-histogram l1 learner · large domain size | communication bits | Helped |
Closest papers by meaning
- Distributed Nonparametric Estimation: from Sparse to Dense Samples per Terminal (ICML 2025 · similarity 0.89)
- Distributed Mean Estimation with Limited Communication (ICML 2017 · similarity 0.89)
- Collaborative Learning of Discrete Distributions under Heterogeneity and Communication Constraints (NeurIPS 2022 · similarity 0.88)
- Distributed Estimation with Multiple Samples per User: Sharp Rates and Phase Transition (NeurIPS 2021 · similarity 0.88)
- Instance-Optimality for Private KL Distribution Estimation (NeurIPS 2025 · similarity 0.85)
- Derandomizing Multi-Distribution 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.