Leighton Barnes

Leighton Barnes, Alex Dytso

We study when optimal Bayesian estimators under Gaussian noise are approximately linear, and what this implies about the underlying prior distribution. Consider the classical model \(Y = X + Z\), where \(Z\) is Gaussian and independent of \(X\). It is well known that under squared-error loss, the conditional mean \(\mathbb{E}[X|Y]\) is a linear function of \(Y\) if and only if the prior is Gaussian. Much less is understood under absolute-error loss, where the optimal estimator is the conditional median and standard orthogonality-based tools no longer apply. Recent work has established that, in the Gaussian noise model, the Gaussian prior is also the unique distribution that induces an exactly linear conditional median. In this paper, we move beyond exact characterizations and develop a quantitative stability theory: if the optimal estimator is approximately linear, must the prior be close to Gaussian? For the \(L_2\) setting, we derive explicit rates showing that near-linearity of the conditional mean forces the prior to be close to Gaussian in the Levy metric. For the \(L_1\) setting, we develop a functional-analytic framework based on Hermite expansions and adjoint operators, establishing that approximate linearity of the conditional median implies proximity to the Gaussian family.

Leighton Barnes, Stephen Cameron, Timothy Chow et al.

An unbiased $m$-sparsification of a vector $p\in \mathbb{R}^n$ is a random vector $Q\in \mathbb{R}^n$ with 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 $\mathsf{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.