Xiugang Wu
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
Research Subjects
Xiugang Wu has a total of 14 co-authors. Here are the top co-authors by number of shared publications:
Ayfer Ozgur
Stanford University, Stanford, CA, USA
6 shared publications- Ayfer Ozgur
Stanford University
5 shared publications - Ayfer Ozgur
Department of Electrical Engineering Stanford
3 shared publications - Leighton Pate Barnes
Department of Electrical Engineering, Stanford University, Stanford, CA 94305, USA
3 shared publications Yikun Bai
Department of Electrical and Computer Engineering, University of Delaware, Newark, DE, USA
3 shared publications- Abbas El Gamal
School of Engineering and the Department of Electrical Engineering, Stanford University, Stanford, CA, USA
2 shared publications
Latest Publications
- 16 January 2023
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 69 (4) , 2059-2073
Information Constrained Optimal Transport: From Talagrand, to Marton, to Cover
The optimal transport problem studies how to transport one measure to another in the most cost-effective way and has wide range of applications from economics to machine learning. In this paper, we introduce and study an information constrained variation of this problem. Our study yields a strengthening and generalization of Talagrand’s celebrated transportation cost inequality. Following Marton’s approach, we show that the new transportation cost inequality can be used to recover old and new concentration of measure results. Finally, we provide an application of this new inequality to network information theory. We show that it can be used to recover almost immediately a recent solution to a long-standing open problem posed by Cover regarding the capacity of the relay channel.
- 16 January 2023
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 69 (4) , 2059-2073
Information Constrained Optimal Transport: From Talagrand, to Marton, to Cover
The optimal transport problem studies how to transport one measure to another in the most cost-effective way and has wide range of applications from economics to machine learning. In this paper, we introduce and study an information constrained variation of this problem. Our study yields a strengthening and generalization of Talagrand’s celebrated transportation cost inequality. Following Marton’s approach, we show that the new transportation cost inequality can be used to recover old and new concentration of measure results. Finally, we provide an application of this new inequality to network information theory. We show that it can be used to recover almost immediately a recent solution to a long-standing open problem posed by Cover regarding the capacity of the relay channel.
- Open Access
Understanding Entropic Regularization in GANs
Generative Adversarial Networks are a popular method for learning distributions from data by modeling the target distribution as a function of a known distribution. The function, often referred to as the generator, is optimized to minimize a chosen distance measure between the generated and target distributions. One commonly used measure for this purpose is the Wasserstein distance. However, Wasserstein distance is hard to compute and optimize, and in practice entropic regularization techniques are used to improve numerical convergence. The influence of regularization on the learned solution, however, remains not well-understood. In this paper, we study how several popular entropic regularizations of Wasserstein distance impact the solution in a simple benchmark setting where the generator is linear and the target distribution is high-dimensional Gaussian. We show that entropy regularization promotes the solution sparsification, while replacing the Wasserstein distance with the Sinkhorn divergence recovers the unregularized solution. Both regularization techniques remove the curse of dimensionality suffered by Wasserstein distance. We show that the optimal generator can be learned to accuracy $\epsilon$ with $O(1/\epsilon^2)$ samples from the target distribution. We thus conclude that these regularization techniques can improve the quality of the generator learned from empirical data for a large class of distributions.Open AccessUnderstanding Entropic Regularization in GANs
Generative Adversarial Networks are a popular method for learning distributions from data by modeling the target distribution as a function of a known distribution. The function, often referred to as the generator, is optimized to minimize a chosen distance measure between the generated and target distributions. One commonly used measure for this purpose is the Wasserstein distance. However, Wasserstein distance is hard to compute and optimize, and in practice entropic regularization techniques are used to improve numerical convergence. The influence of regularization on the learned solution, however, remains not well-understood. In this paper, we study how several popular entropic regularizations of Wasserstein distance impact the solution in a simple benchmark setting where the generator is linear and the target distribution is high-dimensional Gaussian. We show that entropy regularization promotes the solution sparsification, while replacing the Wasserstein distance with the Sinkhorn divergence recovers the unregularized solution. Both regularization techniques remove the curse of dimensionality suffered by Wasserstein distance. We show that the optimal generator can be learned to accuracy $\epsilon$ with $O(1/\epsilon^2)$ samples from the target distribution. We thus conclude that these regularization techniques can improve the quality of the generator learned from empirical data for a large class of distributions. - 6 October 2020
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 66 (12) , 7929-7938
Minimax Learning for Distributed Inference
The classical problem of supervised learning is to infer an accurate estimate of a target variable $Y$ from a measured variable $X$ using a set of labeled training samples. Motivated by the increasingly distributed nature of data and decision making, this paper considers a variation of this classical problem in which the inference is distributed between two nodes, e.g., a mobile device and a cloud, with a rate constraint on the communication between them. The mobile device observes $X$ and sends a description $M$ of $X$ to the cloud, which computes an estimate $\hat {Y}$ of $Y$ . We follow the recent minimax learning approach to study this inference problem and show that it corresponds to a one-shot minimax noisy lossy source coding problem. We then establish information theoretic bounds on the risk-rate Lagrangian cost, leading to a general method for designing a near-optimal descriptor-estimator pair. A key ingredient in the proof of our result is a refined version of the strong functional representation lemma previously used to establish several one-shot source coding theorems. Our results show that a naive estimate-compress scheme for rate-constrained inference is not optimal in general. When the distribution of $(X,Y)$ is known and the error is measured by the logarithmic loss, our bounds on the risk-rate Lagrangian cost provide a new one-shot operational interpretation of the information bottleneck. We also demonstrate a way to bound the excess risk of the descriptor-estimator pair obtained by our method.
- 6 October 2020
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 66 (12) , 7929-7938
Minimax Learning for Distributed Inference
The classical problem of supervised learning is to infer an accurate estimate of a target variable $Y$ from a measured variable $X$ using a set of labeled training samples. Motivated by the increasingly distributed nature of data and decision making, this paper considers a variation of this classical problem in which the inference is distributed between two nodes, e.g., a mobile device and a cloud, with a rate constraint on the communication between them. The mobile device observes $X$ and sends a description $M$ of $X$ to the cloud, which computes an estimate $\hat {Y}$ of $Y$ . We follow the recent minimax learning approach to study this inference problem and show that it corresponds to a one-shot minimax noisy lossy source coding problem. We then establish information theoretic bounds on the risk-rate Lagrangian cost, leading to a general method for designing a near-optimal descriptor-estimator pair. A key ingredient in the proof of our result is a refined version of the strong functional representation lemma previously used to establish several one-shot source coding theorems. Our results show that a naive estimate-compress scheme for rate-constrained inference is not optimal in general. When the distribution of $(X,Y)$ is known and the error is measured by the logarithmic loss, our bounds on the risk-rate Lagrangian cost provide a new one-shot operational interpretation of the information bottleneck. We also demonstrate a way to bound the excess risk of the descriptor-estimator pair obtained by our method.
- Open Access
Information Constrained Optimal Transport: From Talagrand, to Marton, to Cover
The optimal transport problem studies how to transport one measure to another in the most cost-effective way and has wide range of applications from economics to machine learning. In this paper, we introduce and study an information constrained variation of this problem. Our study yields a strengthening and generalization of Talagrand's celebrated transportation cost inequality. Following Marton's approach, we show that the new transportation cost inequality can be used to recover old and new concentration of measure results. Finally, we provide an application of this new inequality to network information theory. We show that it can be used to recover almost immediately a recent solution to a long-standing open problem posed by Cover regarding the capacity of the relay channel.
Open AccessInformation Constrained Optimal Transport: From Talagrand, to Marton, to Cover
The optimal transport problem studies how to transport one measure to another in the most cost-effective way and has wide range of applications from economics to machine learning. In this paper, we introduce and study an information constrained variation of this problem. Our study yields a strengthening and generalization of Talagrand's celebrated transportation cost inequality. Following Marton's approach, we show that the new transportation cost inequality can be used to recover old and new concentration of measure results. Finally, we provide an application of this new inequality to network information theory. We show that it can be used to recover almost immediately a recent solution to a long-standing open problem posed by Cover regarding the capacity of the relay channel.
- 22 August 2020
- Published by Springer Nature
- p. 981-983
Network Information Theory
- 22 October 2018
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 65 (1) , 255-275
“The Capacity of the Relay Channel”: Solution to Cover’s Problem in the Gaussian Case
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.
- 22 October 2018
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 65 (1) , 255-275
“The Capacity of the Relay Channel”: Solution to Cover’s Problem in the Gaussian Case
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.
- 1 August 2018
- Published by Springer Nature
- p. 1-3
Network Information Theory
- 1 June 2018
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 541-545
Minimax Learning for Remote Prediction
The classical problem of supervised learning is to infer an accurate predictor of a target variable Y from a measured variable X by using a finite number of labeled training samples. Motivated by the increasingly distributed nature of data and decision making, in this paper we consider a variation of this classical problem in which the prediction is performed remotely based on a rate-constrained description M of X. Upon receiving M, the remote node computes an estimate Y of Y. We follow the recent minimax approach to study this learning problem and show that it corresponds to a one-shot minimax noisy source coding problem. We then establish information theoretic bounds on the risk-rate Lagrangian cost and a general method to design a near-optimal descriptor-estimator pair, which can be viewed as a rate-constrained analog to the maximum conditional entropy principle used in the classical minimax learning problem. Our results show that a naive estimate-compress scheme for rate-constrained prediction is not in general optimal.
- 1 June 2018
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 541-545
Minimax Learning for Remote Prediction
The classical problem of supervised learning is to infer an accurate predictor of a target variable Y from a measured variable X by using a finite number of labeled training samples. Motivated by the increasingly distributed nature of data and decision making, in this paper we consider a variation of this classical problem in which the prediction is performed remotely based on a rate-constrained description M of X. Upon receiving M, the remote node computes an estimate Y of Y. We follow the recent minimax approach to study this learning problem and show that it corresponds to a one-shot minimax noisy source coding problem. We then establish information theoretic bounds on the risk-rate Lagrangian cost and a general method to design a near-optimal descriptor-estimator pair, which can be viewed as a rate-constrained analog to the maximum conditional entropy principle used in the classical minimax learning problem. Our results show that a naive estimate-compress scheme for rate-constrained prediction is not in general optimal.
- 1 October 2017
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 844-851
A solution to cover's problem for the binary symmetric relay channel: Geometry of sets on the hamming sphere
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.
- 1 October 2017
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 844-851
A solution to cover's problem for the binary symmetric relay channel: Geometry of sets on the hamming sphere
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.
- Open Access
- 26 July 2017
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 64 (2) , 1023-1037
Cut-Set Bound is Loose for Gaussian Relay Networks
The cut-set bound developed by Cover and El Gamal in 1979 has since remained the best known upper bound on the capacity of the Gaussian relay channel. We develop a new upper bound on the capacity of the Gaussian primitive relay channel which is tighter than the cut-set bound. Our proof uses Gaussian measure concentration to establish geometric relations, satisfied with high probability, between the n-letter random variables associated with a reliable code for communicating over this channel. We then translate these geometric relations into new information inequalities that can not be obtained with classical methods. Combined with a tensorization argument proposed by Courtade and Ozgur in 2015, our result also implies that the current capacity approximations for Gaussian relay networks, which have linear gap to the cut-set bound in the number of nodes, are order-optimal and leads to a lower bound on the preconstant.
- 26 July 2017
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 64 (2) , 1023-1037
Open AccessCut-Set Bound is Loose for Gaussian Relay Networks
The cut-set bound developed by Cover and El Gamal in 1979 has since remained the best known upper bound on the capacity of the Gaussian relay channel. We develop a new upper bound on the capacity of the Gaussian primitive relay channel which is tighter than the cut-set bound. Our proof uses Gaussian measure concentration to establish geometric relations, satisfied with high probability, between the n-letter random variables associated with a reliable code for communicating over this channel. We then translate these geometric relations into new information inequalities that can not be obtained with classical methods. Combined with a tensorization argument proposed by Courtade and Ozgur in 2015, our result also implies that the current capacity approximations for Gaussian relay networks, which have linear gap to the cut-set bound in the number of nodes, are order-optimal and leads to a lower bound on the preconstant.