Technical Summary: One-Bit Distributed Mean Estimation with Unknown Variance

1. Problem Statement

This work addresses the problem of Distributed Mean Estimation (DME) under extreme communication constraints where each user is limited to transmitting a single bit of information to a central server. Unlike prior works that often assume the variance is known or that the mean is the sole unknown parameter, this paper considers the scale-location family of distributions where both the mean ($\mu$) and the variance ($\sigma^2$) are unknown. The variance is treated as a nuisance parameter.

The setting involves $n$ users, each holding an independent and identically distributed (i.i.d.) sample $X_i$ drawn from a distribution $f_{X,\mu,\sigma}(x) = \frac{1}{\sigma}f_X(\frac{x-\mu}{\sigma})$, where $f_X$ is a known base density with zero mean and unit variance. The goal is to design a communication protocol $\Pi$ (consisting of $n$ encoders and one decoder) that allows the server to estimate $\mu$ with minimal asymptotic Mean Squared Error (MSE). The paper distinguishes between:

• Non-adaptive protocols: Each user's bit $Y_i$ depends only on their local sample $X_i$.
• Adaptive protocols: A user's bit $Y_i$ may depend on $X_i$ and the previously transmitted bits $Y_1, \dots, Y_{i-1}$ (or a broadcast message from the server).

2. Methodology and Protocols

Non-Adaptive Protocols

The authors propose a simple two-threshold non-adaptive protocol to jointly estimate $\mu$ and $\sigma$.

• Mechanism: Users are partitioned into two groups of sizes $n_1$ and $n_2$. The first group uses a threshold $\theta_1$, and the second uses $\theta_2$. Each user transmits a bit indicating whether their sample is below the respective threshold.
• Estimation: The server computes the empirical cumulative distribution function (CDF) values at these thresholds, inverts the known base CDF $F_X$, and solves a system of equations to obtain coarse estimates $\hat{\mu}_c$ and $\hat{\sigma}_c$.
• Performance: Theorem 3.1 establishes that this protocol is strongly consistent and asymptotically normal. However, the asymptotic MSE depends on the true $\mu$ and grows unbounded as $|\mu| \to \infty$ for fixed thresholds.

The paper also introduces a multi-threshold non-adaptive protocol for non-parametric mean estimation (Section 3.4), which approximates the expectation via Riemann sums. However, the authors note this approach generally yields an MSE scaling worse than $O(1/n)$ unless the support of the distribution is bounded.

Adaptive Protocol

To overcome the limitations of non-adaptive schemes, the authors design a simple two-round adaptive protocol:

1. Round 1 (Coarse Estimation): A subset of users ($n_1 + n_2$) executes the non-adaptive two-threshold protocol described above to generate coarse estimates $\hat{\mu}_c$ and $\hat{\sigma}_c$.
2. Broadcast: The server broadcasts $\hat{\mu}_c$ to the remaining users ($n_3$).
3. Round 2 (Refinement): The remaining users use $\hat{\mu}_c$ as their quantization threshold, transmitting $Y_i = \mathbb{1}\{X_i < \hat{\mu}_c\}$.
4. Final Estimation: The server uses the new empirical CDF value and the coarse variance estimate $\hat{\sigma}_c$ to refine the final estimate $\hat{\mu}_f$.

Theoretical analysis (Theorem 4.1) shows this scheme achieves an asymptotic MSE of $\frac{\sigma^2}{4f_X(0)^2}$, which is independent of the true $\mu$.

3. Key Contributions and Theoretical Results

Lower Bounds for Non-Adaptive Protocols

A primary contribution is the derivation of a general lower bound on the minimax MSE for any 1-bit non-adaptive protocol for symmetric, strictly log-concave distributions.

• Using Le Cam's two-point method and a refined analysis of the squared Hellinger distance, the authors prove that for any such distribution, the asymptotic minimax MSE is lower-bounded by:
  $$\lim_{n \to \infty} \sup_{\mu} n \cdot \text{MSE}(\hat{\mu}) \geq \frac{\alpha^* \sigma^2}{T(f_X)}$$
  where $\alpha^* \approx 0.1034$ and $T(f_X)$ is a distribution-dependent constant derived from the density $f_X$.
• This bound applies to a broad class of distributions, including the generalized Gaussian family.

Optimality of the Adaptive Protocol

The authors establish the information-theoretic optimality of their simple adaptive protocol for a large subclass of symmetric, strictly log-concave distributions (where a specific shape condition on the density holds).

• By deriving a matching lower bound using the Van Trees inequality, they prove that no 1-bit adaptive protocol can achieve an asymptotic MSE lower than $\frac{\sigma^2}{4f_X(0)^2}$.
• Since their adaptive protocol achieves this bound, it is optimal for these distributions.

The Gap Between Adaptive and Non-Adaptive

The paper demonstrates a strict performance gap between adaptive and non-adaptive protocols for many common distributions.

• For the Generalized Gaussian Distribution (GGD) with shape parameter $1 < \beta < 1.85$ and the hyperbolic secant distribution, the lower bound for non-adaptive protocols is strictly larger than the upper bound achieved by the adaptive protocol.
• Specifically, for GGD with $\beta < 1.85$, the ratio of the non-adaptive lower bound to the adaptive upper bound is greater than 1, proving that non-adaptive protocols are strictly suboptimal in these regimes.
• For $\beta > 1.85$, the adaptive constant becomes smaller than the non-adaptive lower bound, though the authors conjecture the non-adaptive lower bound may be loose for these heavier-tailed shapes.

Comparison with Unquantized Limits

The authors compare their adaptive one-bit bounds against the Fisher information bound (the limit with no communication constraints).

• For many distributions (e.g., Gaussian, Logistic, Hyperbolic Secant), the constant achieved by the adaptive one-bit protocol is very close to the centralized Fisher information limit.
• This suggests that increasing the bit budget beyond one bit per user yields only marginal improvements in asymptotic MSE for these distributions.

4. Significance and Claims

The paper claims that its work provides fundamental insights into the cost of communication constraints in distributed estimation when nuisance parameters (variance) are present.

• Optimality of Adaptation: The work rigorously proves that for a broad class of distributions, adaptive protocols are strictly superior to non-adaptive ones when the variance is unknown. This contrasts with some prior literature where non-adaptive schemes were shown to be order-optimal under different assumptions (e.g., known variance or bounded mean).
• Practical Efficiency: The proposed adaptive protocol is simple (requiring only two rounds of communication) and achieves the theoretical lower bound, making it an information-theoretically optimal solution for the stated problem.
• Marginal Gains from More Bits: The proximity of the adaptive one-bit performance to the centralized Fisher information bound implies that in many practical scenarios involving symmetric log-concave distributions, the "cost" of 1-bit quantization is minimal, and the primary bottleneck is the lack of adaptation rather than the bit budget itself.
• Limitations: The authors modestly note that their non-adaptive lower bound may not be tight for all distributions (specifically for GGD with $\beta > 1.85$) and that the results for variance estimation are currently limited to the non-adaptive setting without a claim of optimality. They also identify extending these techniques to high-dimensional vectors and multi-bit budgets as open directions for future work.

The simulation results presented in the paper confirm the theoretical predictions, showing a consistent positive gap between the empirical MSE of adaptive and non-adaptive protocols across various distributions, aligning with the derived asymptotic bounds.