We study schemes and lower bounds for distributed minimax statistical estimation over a Gaussian multiple-access channel (MAC) under squared error loss. Our framework combines statistical estimation and wireless communication. First, we develop “analog” joint estimation-communication schemes that exploit the superposition property of the Gaussian MAC. We characterize their risk in terms of the number of nodes and dimension of the parameter space. Then, we derive information-theoretic lower bounds on the minimax risk of any estimation scheme that is restricted to communicate the samples over a given number of uses of the channel. This shows that the risk achieved by our proposed schemes is within a logarithmic factor of these lower bounds. We compare both achievability and lower bound results to previous “digital” lower bounds, where nodes transmit errorless bits at the Shannon capacity of the MAC. Our key finding is that analog estimation schemes that leverage the physical layer offer a drastic reduction in estimation error over digital schemes relying on a physical-layer abstraction.

We study lower bounds for minimax statistical estimation over a Gaussian multiple-access channel (MAC) under squared error loss, using techniques from both statistical estimation and information theory. We characterize these bounds in terms of the number of nodes$n$and the dimension of the parameter space$d$, showing that the risk must be$\Omega(d/n\log n)$. This is within a$\log n$factor of previous analog achievability results. While lower bounds for minimax statistical estimation have been previously studied under quantization constraints that abstract the physical layer as noiseless bit pipes, to our knowledge our paper provides the first lower bounds for statistical estimation over noisy multi-user channels. This adds to a body of works showing how analog schemes that consider the physical layer jointly with the estimation scheme, can outperform digital schemes that separate the two with an abstraction layer.

We study minimax statistical estimation over a Gaussian multiple-access channel (MAC) under squared error loss, in a framework combining statistical estimation and wireless communication. We develop “analog” joint estimationcommunication schemes that leverage the additive nature of the Gaussian MAC and characterize their minimax risk in terms of the number of nodes , the dimension of the parameter space and the signal-to-noise ratio of the MAC, for two estimation tasks: Gaussian location and product Bernoulli model. We then compare this risk to existing lower bounds for risk in digital schemes, in which nodes transmit bits noiselessly at the Shannon capacity. We show that, by leveraging the summation inherent in the Gaussian MAC, our analog schemes in both cases outperform these lower bounds, scaling with (d/n) rather than Ω(d/log ). This suggests that in over-the-air statistical estimation, drastic improvements in estimation error can be obtained by using analog schemes that work in tandem with the physical layer, rather than digital schemes using a physical-layer abstraction.

Entropy estimation is one of the prototypical problems in distribution property testing. To consistently estimate the Shannon entropy of a distribution on $S$ elements with independent samples, the optimal sample complexity scales sublinearly with $S$ as $\Theta(\frac{S}{\log S})$ as shown by Valiant and Valiant \cite{Valiant--Valiant2011}. Extending the theory and algorithms for entropy estimation to dependent data, this paper considers the problem of estimating the entropy rate of a stationary reversible Markov chain with $S$ states from a sample path of $n$ observations. We show that \begin{itemize} \item Provided the Markov chain mixes not too slowly, \textit{i.e.}, the relaxation time is at most $O(\frac{S}{\ln^3 S})$, consistent estimation is achievable when $n \gg \frac{S^2}{\log S}$. \item Provided the Markov chain has some slight dependency, \textit{i.e.}, the relaxation time is at least $1+\Omega(\frac{\ln^2 S}{\sqrt{S}})$, consistent estimation is impossible when $n \lesssim \frac{S^2}{\log S}$. \end{itemize} Under both assumptions, the optimal estimation accuracy is shown to be $\Theta(\frac{S^2}{n \log S})$. In comparison, the empirical entropy rate requires at least $\Omega(S^2)$ samples to be consistent, even when the Markov chain is memoryless. In addition to synthetic experiments, we also apply the estimators that achieve the optimal sample complexity to estimate the entropy rate of the English language in the Penn Treebank and the Google One Billion Words corpora, which provides a natural benchmark for language modeling and relates it directly to the widely used perplexity measure.