Research map / Learning theory and algorithms / Sample complexity
Optimal Sparsity-Sensitive Bounds for Distributed Mean Estimation
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 sparsity-sensitive quantization and constant-weight coding instead of prior DME protocols | distributed K-means · MNIST uniform, 10 clients | total bits per dimension at same objective: 52.8 -> 46.8 | Helped |
| same, on non-uniformly distributed data | distributed K-means · MNIST non-uniform, 10 clients | total bits per dimension at same objective: 49.9 -> 36.4 | Helped |
| same, in distributed power iteration | distributed power iteration · MNIST uniform, 100 clients | total bits per dimension at same error: 24.2 -> 23.4 | Helped |
| same, power iteration on non-uniform data | distributed power iteration · MNIST non-uniform, 100 clients | total bits per dimension at same error: 26.6 -> 20.6 | Helped |
| use global quantization step size across clients on data unbalanced across clients | sparsity-sensitive DME · synthetic t-distribution, sparseness 0.36 | log(MSE) vs bits per dimension | Helped |
| increase input sparsity (zero out dimensions) | sparsity-sensitive DME vs baselines · synthetic, sparseness 0.60 to 0.06 | MSE at equal communication | Helped |
Closest papers by meaning
- Efficient Distributed Learning with Sparsity (ICML 2017 · similarity 0.89)
- Correlation Aware Sparsified Mean Estimation Using Random Projection (NeurIPS 2023 · similarity 0.89)
- Scalable Distributed Stochastic Optimization via Bidirectional Compression: Beyond Pessimistic Limits (NeurIPS 2026 · similarity 0.88)
- The Price of Sparsity: Sufficient Conditions for Sparse Recovery using Sparse and Sparsified Measurements (NeurIPS 2025 · similarity 0.86)
- Distributed Nonparametric Estimation: from Sparse to Dense Samples per Terminal (ICML 2025 · similarity 0.86)
- Distributed Sparse Regression via Penalization (NeurIPS 2024 · 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.