Research map / Learning theory and algorithms / Sample complexity
Distributed Nonparametric Estimation: from Sparse to Dense Samples per Terminal
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.
Characterizes minimax optimal rates for communication-constrained distributed nonparametric function estimation across all sample-per-terminal regimes (sparse to dense), via a two-layer wavelet-based protocol and strong data processing inequality lower bounds.
Problem
Distributed nonparametric function estimation where m terminals each hold n i.i.d. samples and send only l bits, with the goal of finding minimax rates across all relative sizes of n and m (sparse to dense samples per terminal).
Approach
A two-layer protocol: wavelet-based sample-wise unbiased coefficient estimators are truncated and quantized into a finite-alphabet distribution, whose parametric distribution is estimated with an optimal interactive protocol; the lower bound uses a generalized SDPI tensorization analyzed via balls-and-bins.
Key results
- Establishes minimax rate R(m,n,l,r) approximately (N_ess)^{-2r/(2r+1)} up to polylog factors, with N_ess an effective sample size combining total sample mn and communication budget l for all regimes.
- Shows exponential dependence on l in the sparsest regime m >= n^{2r+1} for small l, polynomial dependence otherwise.
- Optimal rates for density, Gaussian, binary, Poisson and heteroskedastic regression follow as corollaries.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Increase communication budget l in the sparse regime m >= n^{2r+1}, initially 1 <= l <= (1/(2r+1)) log(m/n^{2r+1}) | Distributed nonparametric estimation · Sparse samples per terminal | minimax squared L2 risk: R(m,n,l,r) is approximately (N_{ess})^{-2r/(2r+1)}; N_{ess}=(2^lmn)^{(2r+1)/(2r+2)} in this range | Helped |
| Increase communication budget l beyond the initial sparse-regime range | Distributed nonparametric estimation · Sparse samples per terminal | minimax squared L2 risk: N_{ess}=lm in one regime; N_{ess}=(lm)^{2r+1} in another | Helped |
| Increase communication budget l | Distributed nonparametric estimation · Regimes other than m >= n^{2r+1} | minimax squared L2 risk: N_{ess}=lm; (lmn)^{(2r+1)/(2r+2)}; or (lm)^{2r+1}, depending on the regime | Helped |
| Increase communication budget to at least n when m > n^{2r}, or (mn)^{1/(2r+1)} when m <= n^{2r} | Distributed nonparametric estimation · All sample-per-terminal regimes | minimax squared L2 risk: N_{ess}=mn | Helped |
Surprising findings
- Rate depends exponentially on communication budget l in the sparsest regime, unlike the polynomial dependence in the Gaussian sequence model.
Limitations
- Results hold up to logarithmic factors (polylog N).
- Requires regularity assumptions (sub-exponential estimators, sub-exponential log-likelihood ratios) on the sample distribution.
- Analysis restricted to L2 loss on Sobolev balls; extension to Besov spaces and L^s norms left open.
Experimental setup
Metrics: minimax L2 estimation rate
Baselines: Acharya et al. nonparametric density estimation with n=1 Gaussian sequence model rates (Szabo and van Zanten)
Builds on: Barnes et al. distributed parametric/nonparametric estimation with n=1 (simulate Acharya et al. communication-constrained distribution estimation Szabo-Van Zanten wavelet approximation
Closest papers by meaning
- Distributed Nonparametric Regression under Communication Constraints (ICML 2018 · similarity 0.90)
- Communication-Efficient Distributed Learning of Discrete Distributions (NeurIPS 2017 · similarity 0.89)
- Optimal Rates for Nonparametric Density Estimation under Communication Constraints (NeurIPS 2021 · similarity 0.89)
- Robust Estimation Under Heterogeneous Corruption Rates (NeurIPS 2025 · similarity 0.84)
- Sharp Optimality of Simple, Plug-in Estimation of the Fisher Information of a Smoothed Density (ICML 2025 · similarity 0.84)
- Fundamental Limits of Distributed Covariance Matrix Estimation Under Communication Constraints (ICML 2024 · 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.