LBLeighton Pate Barnes

Leighton Pate Barnes

*This is an algorithmically generated author record based on publicly available information.

Current Organizations / Institutes

The organizations/institutes from the scholar's latest article

Previous Organizations / Institutes

The organizations / institutes from the scholar's other articles in the past ten years


Leighton Pate Barnes has a total of 10 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • L 1 Estimation: On the Optimality of Linear Estimators

    by Leighton P. Barnes, Alex Dytso, Jingbo Liu, H. Vincent Poor

    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.


  • Open Access

    Improved Information-Theoretic Generalization Bounds for Distributed, Federated, and Iterative Learning

    by Leighton Pate Barnes, Alex Dytso, Harold Vincent Poor

    We consider information-theoretic bounds on the expected generalization error for statistical learning problems in a network setting. In this setting, there are K nodes, each with its own independent dataset, and the models from the K nodes 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.


  • rTop-k: A Statistical Estimation Approach to Distributed SGD

    by Leighton Pate Barnes, Huseyin A. Inan, Berivan Isik, Ayfer Ozgur

    The large communication cost for exchanging gradients between different nodes significantly limits the scalability of distributed training for large-scale learning models. Motivated by this observation, there has been significant recent interest in techniques that reduce the communication cost of distributed Stochastic Gradient Descent (SGD), with gradient sparsification techniques such as top-k and random-k shown to be particularly effective. The same observation has also motivated a separate line of work in distributed statistical estimation theory focusing on the impact of communication constraints on the estimation efficiency of different statistical models. The primary goal of this paper is to connect these two research lines and demonstrate how statistical estimation models and their analysis can lead to new insights in the design of communication-efficient training techniques. We propose a simple statistical estimation model for the stochastic gradients which captures the sparsity and skewness of their distribution. The statistically optimal communication scheme arising from the analysis of this model leads to a new sparsification technique for SGD, which concatenates random-k and top-k, considered separately in the prior literature. We show through extensive experiments on both image and language domains with CIFAR-10, ImageNet, and Penn Treebank datasets that the concatenated application of these two sparsification methods consistently and significantly outperforms either method applied alone.


  • Fisher Information Under Local Differential Privacy

    by Leighton Pate Barnes, Wei-Ning Chen, Ayfer Ozgur

    We develop data processing inequalities that describe how Fisher information from statistical samples can scale with the privacy parameter ε under local differential privacy constraints. These bounds are valid under general conditions on the distribution of the score of the statistical model, and they elucidate under which conditions the dependence on ε is linear, quadratic, or exponential. We show how these inequalities imply order-optimal lower bounds for private estimation for both the Gaussian location model and discrete distribution estimation for all levels of privacy ε>0. We further apply these inequalities to sparse Bernoulli models and demonstrate privacy mechanisms and estimators with order-matching squared ℓ2 error.


  • “The Capacity of the Relay Channel”: Solution to Cover’s Problem in the Gaussian Case

    by Xiugang Wu, Leighton Pate Barnes, Ayfer Ozgur

    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) can not 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.


  • A Geometric Characterization of Fisher Information from Quantized Samples with Applications to Distributed Statistical Estimation

    by Leighton Pate Barnes, Yanjun Han, Ayfer Ozgur

    Consider the Fisher information for estimating a vector θ ∈ ℝ d from the quantized version of a statistical sample X ~ f(x|θ). Let M be a k-bit quantization of X. We provide a geometric characterization of the trace of the Fisher information matrix I M (θ) in terms of the score function S θ (X). When k = 1, we exactly solve the extremal problem of maximizing this geometric quantity for the Gaussian location model, which allows us to conclude that in this model, a halfspace quantization is the one-bit quantization that maximizes T r (I M (θ)). Under assumptions on the tail of the distribution of S θ (X) projected onto any unit vector in ℝ d , we give upper bounds demonstrating how T r (I M (θ)) can scale with k. We apply these results to find lower bounds on the minimax risk of estimating θ from multiple quantized samples of X, for example in a distributed setting where the samples are distributed across multiple nodes and each node has a total budget of k-bits to communicate its sample to a centralized estimator. Our bounds apply in a unified way to many common statistical models including the Gaussian location model and discrete distribution estimation, and they recover and generalize existing results in the literature with simpler and more transparent proofs.


  • A solution to cover's problem for the binary symmetric relay channel: Geometry of sets on the hamming sphere

    by Leighton Pate Barnes, Xiugang Wu, Ayfer Ozgur

    We solve a long-standing open problem posed by Cover and named “The Capacity of the Relay Channel,” Open Problems in Communication and Computation, Springer-Verlag, 1987, in the case when the channels from the source to the relay and the destination are binary symmetric channels. Similar to our recent solution of this problem in the Gaussian case, we solve this problem by connecting it to high-dimensional geometry. However, our geometric approach in the binary case significantly deviates from the Gaussian case, since our treatment of the Gaussian case relied on an extension of the classical isoperimetric inequality on the Euclidean sphere, the counterpart of which does not exist on the Hamming sphere. Instead, we prove a Riesz rearrangement type inequality on the Hamming sphere, which allows us to develop a new upper bound on the capacity of the binary symmetric relay channel. Our argument (and consequently our upper bound) for the binary case is weaker than the one we obtained in the Gaussian case, but nevertheless strong enough to resolve Cover's problem.


  • Cover's open problem: “The Capacity of the Relay Channel”

    by Xiugang Wu, Leighton Pate Barnes, Ayfer Ozgur

    Consider a memoryless relay channel, where the channel from the relay to the destination is an isolated bit pipe of capacity C 0 . Let C(C 0 ) denote the capacity of this channel as a function of C 0 . What is the critical value of C 0 such that C(C 0 ) 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(C 0 ) can not equal to C(∞) unless C 0 = ∞, regardless of the SNR of the Gaussian channels, while the cutset bound would suggest that C(∞) can be achieved at finite C 0 . Our approach is geometric and relies on a strengthening of the isoperimetric inequality on the sphere by using Riesz rearrangement inequality.