We study prior distributions for Poisson parameter estimation under$L^{1}$loss. Specifically, we construct a new family of prior distributions whose optimal Bayesian estimators (the conditional medians) can be any prescribed increasing function that satisfies certain regularity conditions. In the case of affine estimators, this family is distinct from the usual conjugate priors, which are gamma distributions. Our prior distributions are constructed through a limiting process that matches certain moment conditions. These results provide the first explicit description of a family of distributions, beyond the conjugate priors, that satisfy the affine conditional median property; and more broadly for the Poisson noise model they can give any arbitrarily prescribed conditional median.

An unbiased m-sparsification of a vector$p$E Rnis a random vector$Q$∊ Rnwith mean$p$that has at most m$n$nonzero coordinates. Unbiased sparsification compresses the original vector without introducing bias; it arises in various contexts, such as in federated learning and sampling sparse probability distributions. Ideally, unbiased sparsification should also minimize the expected value of a divergence function Div(Q, p) that measures how far away$Q$is from the original$p$. If$Q$is optimal in this sense, then we call it efficient. Our main results describe efficient unbiased sparsifications for divergences that are either permutation-invariant or additively separable. Surprisingly, the characterization for permutation-invariant divergences is robust to the choice of divergence function, in the sense that our class of optimal$Q$for squared Euclidean distance coincides with our class of optimal$Q$for Kullback-Leibler divergence, or indeed any of a wide variety of divergences.

Consider the task of estimating a random vector$X$from noisy observations$Y=X+Z$, where$Z$is a standard normal vector, under the$L^{p}$fidelity criterion. This work establishes that, for$1\leq p\leq 2$, the optimal Bayesian estimator is linear and positive definite if and only if the prior distribution on$X$is a (non-degenerate) multivariate Gaussian. Furthermore, for$p > 2$, it is demonstrated that there are infinitely many priors that can induce such an estimator.

Consider the problem of estimating a random variable X from noisy observations$Y = X+ Z$, where Z is standard normal, under the$L^{1}$fidelity criterion. It is well known that the optimal Bayesian estimator in this setting is the conditional median. This work shows that the only prior distribution on X that induces linearity in the conditional median is Gaussian. Along the way, several other results are presented. In particular, it is demonstrated that if the conditional distribution$P_{X|Y=y}$is symmetric for all y, then X must follow a Gaussian distribution. Additionally, we consider other$L^{p}$losses and observe the following phenomenon: for$p \in [{1,2}]$, Gaussian is the only prior distribution that induces a linear optimal Bayesian estimator, and for$p \in (2,\infty)$, infinitely many prior distributions on X can induce linearity. Finally, extensions are provided to encompass noise models leading to conditional distributions from certain exponential families.

Consider the problem of estimating a random variable X in Gaussian noise under L1fidelity criteria. It is well-known that in the L1setting, the optimal Bayesian estimator is given by the conditional median. The goal of this work is to characterize the set of prior distributions on X for which the conditional median corresponds to a linear estimator. This work shows that neither discrete nor compactly supported distributions can induce a linear conditional median. Moreover, under certain non-trivial restrictions on the set of allowed probability distributions, the Gaussian is shown to be the only solution that induces a linear conditional median.

We consider information-theoretic bounds on expected generalization error for statistical learning problems in a networked setting. In this setting, there are K nodes, each with its own independent dataset, and the models from each node have to be aggregated into a final centralized model. We consider both simple averaging of the models as well as more complicated multi-round algorithms. We give upper bounds on the expected generalization error for a variety of problems, such as those with Bregman divergence or Lipschitz continuous losses, that demonstrate an improved dependence of 1/K on the number of nodes. These "per node" bounds are in terms of the mutual information between the training dataset and the trained weights at each node, and are therefore useful in describing the generalization properties inherent to having communication or privacy constraints at each node.

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 consider the processing of statistical samples$X\sim P_{\theta}$by a channel$p(y\vert x)$, and characterize how the statistical information from the samples for estimating the parameter$\theta\in \mathbb{R}^{d}$can scale with the mutual information or capacity of the channel. We show that if the statistical model has a sub-Gaussian score function, then the trace of the Fisher information matrix for estimating$\theta$from$Y$can scale at most linearly with the mutual information between$X$and$Y$. We apply this result to obtain minimax lower bounds in distributed statistical estimation problems, and obtain a tight preconstant for Gaussian mean estimation. We then show how our Fisher information bound can also imply mutual information or Jensen-Shannon divergence based distributed strong data processing inequalities.

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.

We consider the Courtade-Kumar most informative Boolean function conjecture for balanced functions, as well as a conjecture by Li and Médard that dictatorship functions also maximize the Lαnorm of Tpf for 1 ≤ α ≤ 2 where Tpis the noise operator and f is a balanced Boolean function. By using a result due to Laguerre from the 1880's, we are able to bound how many times an Lα-norm related quantity can cross zero as a function of α, and show that these two conjectures are essentially equivalent.

We consider the problem of learning high-dimensional discrete distributions and structured (e.g. Gaussian) distributions in distributed networks, where each node in the network observes an independent sample from the underlying distribution and can use k bits to communicate its sample to a central processor. We consider a blackboard communication model, where nodes can share information interactively through a public blackboard but each node is restricted to write at most k bits on the final transcript. We characterize the impact of the communication constraint k on the minimax risk of estimating the underlying distribution under ℓ2loss, and develop minimax lower bounds that apply in a unified way to many common statistical models. This is achieved by explicitly characterizing the Fisher information from the blackboard transcript.

Consider a memoryless relay channel, where the relay is connected to the destination with an isolated bit pipe of capacity C0. Let C(C0) denote the capacity of this channel as a function of C0. What is the critical value of C0, such that C(C0) first equals C(∞)? This is a long-standing open problem posed by Cover and named “The Capacity of the Relay Channel,” in Open Problems in Communication and Computation, Springer-Verlag, 1987. In this paper, we answer this question in the Gaussian case and show that C(C0) cannot equal to C(∞) unless C0= ∞, regardless of the SNR of the Gaussian channels. This result follows as a corollary to a new upper bound we develop on the capacity of this channel. Instead of “single-letterizing” expressions involving information measures in a high-dimensional space as is typically done in converse results in information theory, our proof directly quantifies the tension between the pertinent n-letter forms. This is done by translating the information tension problem to a problem in high-dimensional geometry. As an intermediate result, we develop an extension of the classical isoperimetric inequality on a high-dimensional sphere, which can be of interest in its own right.

Consider a memoryless relay channel, where the channel from the relay to the destination is an isolated bit pipe of capacity C0. Let C(C0) denote the capacity of this channel as a function of C0. What is the critical value of C0such that C(C0) first equals C(∞)? This is a long-standing open problem posed by Cover and named “The Capacity of the Relay Channel,” in Open Problems in Communication and Computation, Springer-Verlag, 1987. In our recent work, we answered this question in the case when the channels from the source to the relay and destination are symmetric, which is the original assumption imposed by Cover, and when these channels are Gaussian. We showed that C(C0) can not equal to C(∞) unless C0= ∞, regardless of the SNR of the Gaussian channels, while the cut-set bound would suggest that C(∞) can be achieved at finite C0. In this paper, we show that our techniques for solving Cover's problem can be naturally extended to the general Gaussian case, where the channels from the source to the relay and destination may be asymmetric, and prove an upper bound on the capacity C(C0) of a general Gaussian relay channel for any C0. This upper bound immediately implies that our previous conclusion, i.e. C(C0) can not equal to C(∞) unless C0= ∞, also holds in the asymmetric case. Our approach is geometric and relies on a strengthening of the isoperimetric inequality on the sphere by using the Riesz rearrangement inequality.