Research map / Learning theory and algorithms / Sample complexity
Pointwise Bounds for Distribution Estimation under Communication Constraints
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 two-round localization followed by adaptive refinement, allocating more samples to symbols according to their estimated square-root probabilities | Communication-constrained distribution estimation · All d-dimensional discrete distributions; sufficiently large n | squared ℓ2 error: O(\frac{d}{n2^b}) -> O\left( \max\left(\frac{\left\lVert p\right\rVert_{{1}/{2}}}{n2^b}, \frac{1}{n}\right) \right) | Helped |
| Use two-round localization followed by adaptive refinement | Communication-constrained distribution estimation · Truncated geometric distribution with constant β | squared ℓ2 error: O(\frac{d}{n2^b}) -> O\left(\max\left( \frac{1}{n(1-\sqrt{\beta})2^b}, \frac{1}{n} \right)\right) | Helped |
| Use two-round localization followed by adaptive refinement | Communication-constrained distribution estimation · Truncated Zipf distribution with λ > 2 | squared ℓ2 error: O(\frac{d}{n2^b}) -> O\left(\frac{1}{n}\right) | Helped |
| Tune the second-round allocation to cube-root probabilities for ℓ1 loss | Two-round localization-refinement · All d-dimensional discrete distributions | ℓ1 error: O\left(\max\left(\sqrt{\frac{\left\lVert p\right\rVert_{{1}/{3}}}{n2^b}}, \sqrt{\frac{\left\lVert p \right\rVert_{{1}/{2 | Helped |
| Adapt sample allocation to the estimated target distribution instead of using uniform grouping | Communication-constrained distribution estimation · Truncated geometric distribution, β = 0.8; varying d | estimation error: an order of magnitude smaller | Helped |
Closest papers by meaning
- Unified Lower Bounds for Interactive High-dimensional Estimation under Information Constraints (NeurIPS 2023 · similarity 0.91)
- Distributed Estimation with Multiple Samples per User: Sharp Rates and Phase Transition (NeurIPS 2021 · similarity 0.89)
- Refinement Methods for Distributed Distribution Estimation under $\ell^p$-Losses (NeurIPS 2025 · similarity 0.88)
- Improved Distribution Estimation in $\ell_\infty$ (ICML 2026 · similarity 0.88)
- Instance-Optimality for Private KL Distribution Estimation (NeurIPS 2025 · similarity 0.87)
- Locally Optimal Private Sampling: Beyond the Global Minimax (NeurIPS 2025 · similarity 0.86)
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.