Generative Adversarial Networks (GANs) 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 facilitate its computation and 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 learned by a Wasserstein GAN in a simple benchmark setting where the generator is linear and the target distribution is high-dimensional Gaussian. We show that entropy regularization of Wasserstein distance promotes sparsification of the solution, while replacing the Wasserstein distance with the Sinkhorn divergence recovers the unregularized solution. The significant benefit of both regularization techniques is that they remove the curse of dimensionality suffered by Wasserstein distance. We show that in both cases the optimal generator can be learned to accuracy $\epsilon$ with $O(1/\epsilon^2)$ samples from the target distribution without requiring to constrain the discriminator. We thus conclude that these regularization techniques can improve the quality of the generator learned from empirical data in a way that is applicable for a large class of distributions.

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.

Generative Adversarial Networks (GANs) 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 facilitate its computation and 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 learned by a Wasserstein GAN in a simple benchmark setting where the generator is linear and the target distribution is high-dimensional Gaussian. We show that entropy regularization of Wasserstein distance promotes sparsification of the solution, while replacing the Wasserstein distance with the Sinkhorn divergence recovers the unregularized solution. The significant benefit of both regularization techniques is that they remove the curse of dimensionality suffered by Wasserstein distance. We show that in both cases the optimal generator can be learned to accuracy ∊ with$O$(1/ ∊2) samples from the target distribution without requiring to constrain the discriminator. We thus conclude that these regularization techniques can improve the quality of the generator learned from empirical data in a way that is applicable for a large class of distributions.

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 inequality to network information theory. We show that it can be used to recover a recent solution to a long-standing open problem posed by Cover regarding the capacity of the relay channel.

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 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.

Consider a primitive diamond relay channel, where a source X wants to send information to a destination with the help of two relays Y1and Y2, and the two relays can communicate to the destination via error-free digital links of capacities C1and C2respectively, while Y1and Y2are conditionally independent given X. In this paper, we develop new upper bounds on the capacity of such primitive diamond relay channels that are tighter than the cut-set bound. Our results include both the Gaussian and the discrete memoryless case and build on the information inequalities recently developed in [6]-[8] that characterize the tension between information measures in a certain Markov chain.

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.

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.

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 cannot 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 lead to a lower bound on the pre-constant.

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.

We consider the discrete memoryless symmetric primitive relay channel, where, a source$X$wants to send information to a destination$Y$with the help of a relay$Z$and the relay can communicate to the destination via an error-free digital link of rate$R_{0}$, while$Y$and$Z$are conditionally independent and identically distributed given$X$. We develop two new upper bounds on the capacity of this channel that are tighter than existing bounds, including the celebrated cut-set bound. Our approach significantly deviates from the standard information-theoretic approach for proving upper bounds on the capacity of multi-user channels. We build on the blowing-up lemma to analyze the probabilistic geometric relations between the typical sets of the$n$-letter random variables associated with a reliable code for communicating over this channel. These relations translate to new entropy inequalities between the$n$-letter random variables involved. As an application of our bounds, we study an open question posed by (Cover, 1987), namely, what is the minimum rate$R_{0}^{*}$needed for the$Z$–$Y$link in order for the capacity of the relay channel to be equal to that of the broadcast cut. We consider the special case when the$X$–$Y$and$X$–$Z$links are both binary symmetric channels. Our tighter bounds on the capacity of the relay channel immediately translate to tighter lower bounds for$R_{0}^{*}$. More interestingly, we show that when$p\to 1/2$,$R_{0}^{*}\geq 0.1803$; even though the broadcast channel becomes completely noisy as$p\to 1/2$and its capacity, and therefore the capacity of the relay channel, goes to zero, a strictly positive rate$R_{0}$is required for the relay channel capacity to be equal to the broadcast bound. Existing upper bounds on the capacity of the relay channel, and the cut-set bound in particular, would rather imply$R_{0}^{*}\to 0$, while achievability schemes require$R_{0}^{*}\to 1$. We conjecture that$R_{0}^{*}\to 1$as$p\to 1/2$.

Consider a primitive relay channel, where, a source X wants to send information to a destination Y with the help of a relay Z and the relay can communicate to the destination via an error-free digital link of rate R0. For the symmetric case, i.e., when Y and Z are conditionally i.i.d. given X, we have recently developed new upper bounds on the capacity of this channel that are tighter than existing bounds, including the celebrated cut-set bound. In this paper, we extend these bounds to the asymmetric case, where Y and Z are conditionally independent given X with arbitrary conditional marginal distributions, for both discrete memoryless and Gaussian channels.

The data center network (DCN), wired or wireless, features large amounts of many-to-one (M2O) sessions. Each M2O session is currently established using point-to-point (P2P) communications and store-and-forward (SAF) relays, and is generally followed by a certain computation at the destination, typically a weighted summation of the received information digits. Fundamentally different from this separate P2P/SAF-based-transmission and computation framework, this paper proposes simultaneous transmission and air computation (STAC), a novel physical layer scheme that achieves STAC in wireless DCNs. In particular, STAC builds on a number of distinguishing characteristics of DCs to take advantage of the superposition nature of electromagnetic signals. With STAC, multiple sources transmit in the same time slot with appropriately chosen parameters, such that the superimposed signal can be directly transformed to the desired summation at the receiver. To enable STAC, we propose an enhanced software-defined network architecture, where a wired low-bandwidth backbone provides wireless transceivers with external reference signals. We also discuss some new challenges that STAC brings to scheduling and routing. Theoretical analysis and simulation results show that STAC can significantly improve both bandwidth and energy efficiency in DCNs.

Consider a symmetric primitive relay channel, where, the source X wants to send information to the destination Y with the help of a relay Z, the relay Z can communicate to the destination Y via an error-free digital link of rate R0, and Y, Z are conditionally independent and identically distributed given X. This paper presents two new upper bounds on the capacity of such relay channels, where the first one is a sharpened version of the recently proposed bound by (Xue, 2014), and the second one is novel. These two bounds are shown to be generally tighter than the cut-set bound, and as an example they are numerically evaluated for the case of binary symmetric channels.

Decode-and-forward (D-F) and compress-and-forward (C-F) are two fundamentally different relay strategies proposed by Cover and El Gamal in 1979. Individually, either of them has been successfully generalized to multirelay channels. In this paper, to allow each relay node the freedom of choosing either of the two strategies, we propose a unified framework, where both the D-F and C-F strategies can be employed simultaneously in the network. It turns out that, to incorporate in full the advantages of both the best known D-F and C-F strategies into a unified framework, the major challenge arises as follows: For the D-F relay nodes to fully utilize the help of the C-F relay nodes, decoding at the D-F relay nodes should not be conducted until all the blocks have been finished; however, in the multilevel D-F strategy, the upstream nodes have to decode prior to the downstream nodes in order to help, which makes simultaneous decoding at all the D-F relay nodes after all the blocks have been finished inapplicable. To tackle this problem, nested blocks combined with backward decoding are used in our framework, so that the D-F relay nodes at different levels can perform backward decoding at different frequencies. As such, the upstream D-F relay nodes can decode before the downstream D-F relay nodes, and the use of backward decoding at each D-F relay node ensures the full exploitation of the help of both the other D-F relay nodes and the C-F relay nodes. The achievable rates under our unified relay framework are found to combine both the best known D-F and C-F achievable rates and include them as special cases. It is also demonstrated through a Gaussian network example that our achievable rates are generally better than the rates obtained with existing unified schemes and with D-F or C-F alone.

In the classical compress-and-forward relay scheme developed by Cover and El Gamal, the decoding process operates in a successive way: the destination first decodes the compression of the relay's observation and then decodes the original message of the source. Recently, several modified compress-and-forward relay schemes were proposed, where the destination jointly decodes the compression and the message, instead of successively. Such a modification on the decoding process was motivated by realizing that it is generally easier to decode the compression jointly with the original message, and more importantly, the original message can be decoded even without completely decoding the compression. Thus, joint decoding provides more freedom in choosing the compression at the relay. However, the question remains in these modified compress-and-forward relay schemes-whether this freedom of selecting the compression necessarily improves the achievable rate of the original message. It has been shown by El Gamal and Kim in 2010 that the answer is negative in the single-relay case. In this paper, it is further demonstrated that in the case of multiple relays, there is no improvement on the achievable rate by joint decoding either. More interestingly, it is discovered that any compressions not supporting successive decoding will actually lead to strictly lower achievable rates for the original message. Therefore, to maximize the achievable rate for the original message, the compressions should always be chosen to support successive decoding. Furthermore, it is shown that any compressions not completely decodable even with joint decoding will not provide any contribution to the decoding of the original message. The above phenomenon is also shown to exist under the repetitive encoding framework recently proposed by Lim , which improved the achievable rate in the case of multiple relays. Here, another interesting discovery is that the improvement is not a result of repetitive encoding, but the benefit of delayed decoding after all the blocks have been finished. The same rate is shown to be achievable with the simpler classical encoding process of Cover and El Gamal with a block-by-block backward decoding process.

The output distribution of a Gaussian channel, when the rate is above capacity, is investigated. It is shown that there is an asymptotic equipartition property (AEP) of the typical output sequences, independently of the specific codebook used, as long as the codebook is typical according to the standard random codebook generation. This equipartition of the typical output sequences is caused by the mixup of input sequences when there are too many of them, namely, when the rate is above capacity. This discovery may shed some light on the optimal design of the compress-and-forward relay schemes.

The compress-and-forward relay scheme developed by (Cover and El Gamal, 1979) is modified by realizing that it is not necessary for the destination to decode the compressed observation of the relay; and even if the compressed observation is to be decoded, it can be more easily done by joint decoding with the original message, rather than in a successive way. This modification introduces flexibility in choosing the compression rate at the relay, which improves the robustness of the compress-and-forward relay scheme in the application to uncertain networks. Nevertheless, it is also shown that this flexibility is associated with a penalty on the achievable rate, and higher than necessary compression rates will incur suboptimal achievable rates.