With the eventual goal of better understanding learning rates of general continuous distributions, we derive the first essentially min-max optimal estimators and learning rates for several natural classes of parametric non-smooth continuous distributions under KL divergence. In particular, we show that unlike the folk theorem of 1/2n learning-rate increase per distribution parameter, non-smooth distribution exhibit a wide range of learning rates.

Given two random variables X and Y, an operational approach is undertaken to quantify the “leakage” of information from X to Y. The resulting measure L (X→Y ) is called maximal leakage, and is defined as the multiplicative increase, upon observing Y , of the probability of correctly guessing a randomized function of X, maximized over all such randomized functions. A closed-form expression for L (X→Y) is given for discrete X and Y, and it is subsequently generalized to handle a large class of random variables. The resulting properties are shown to be consistent with an axiomatic view of a leakage measure, and the definition is shown to be robust to variations in the setup. Moreover, a variant of the Shannon cipher system is studied, in which performance of an encryption scheme is measured using maximal leakage. A single-letter characterization of the optimal limit of (normalized) maximal leakage is derived and asymptotically-optimal encryption schemes are demonstrated. Furthermore, the sample complexity of estimating maximal leakage from data is characterized up to subpolynomial factors. Finally, the guessing framework used to define maximal leakage is used to give operational interpretations of commonly used leakage measures, such as Shannon capacity, maximal correlation, and local differential privacy.

We consider the communication capacity of wireline networks for a two-unicast traffic pattern. The network has two sources and two destinations with each source communicating an independent message to its own destination, subject to the capacity constraints on the directed edges of the network. We propose a simple outer bound for the problem that we call the generalized network sharing (GNS) bound. We show that this bound is the tightest edge-cut bound for two-unicast networks and is tight in several cases, though it is not tight in general. We also show that the problem of computing the GNS bound is NP complete. Finally, we show that despite its seeming simplicity, the two-unicast problem is a very difficult problem: the general network coding problem can be reduced to two-unicast. As a consequence, linear coding is insufficient to achieve capacity for general two-unicast networks, and non-Shannon inequalities are necessary for characterizing the capacity of general two-unicast networks.

A variation of the Shannon cipher system, in which lossy communication is allowed and performance of an encryption scheme is measured in terms of maximal leakage (recently proposed by the authors [1]), is investigated. The asymptotic behavior of normalized maximal leakage is studied, and a single-letter characterization of the optimal limit is derived. Moreover, asymptotically-optimal encryption schemes are demonstrated.

Estimation of the entropy rate of a stochastic process with unknown statistics, from a single sample path is a classical problem in information theory. While universal estimators for general families of processes exist, the estimates have not been accompanied by guarantees for fixed-length sample paths. We provide finite sample bounds on the convergence of a plug-in type estimator for the entropy rate of a Markov chain in terms of its alphabet size and its mixing properties. We also discuss Rényi entropy rate estimation for reversible Markov chains.

We consider the following non-interactive simulation problem: Alice and Bob observe sequences Xnand Yn, respectively, where ((Xi, Yi)}i=1nare drawn independent identically distributed from P(x, y), and they output U and V, respectively, which is required to have a joint law that is close in total variation to a specified Q(u, v). It is known that the maximal correlation of U and V must necessarily be no bigger than that of X and Y if this is to be possible. Our main contribution is to bring hypercontractivity to bear as a tool on this problem. In particular, we show that if P(x, y) is the doubly symmetric binary source, then hypercontractivity provides stronger impossibility results than maximal correlation. Finally, we extend these tools to provide impossibility results for the k-agent version of this problem.

One of the most natural and important questions in statistical learning is: how well can a distribution be approximated from its samples. Surprisingly, this question has so far been resolved for only one loss, the KL-divergence and even in this case, the estimator used is ad hoc and not well understood. We study distribution approximations for general loss measures. For \ell_2^2 we determine the best approximation possible, for \ell_1 and χ^2 we derive tight bounds on the best approximation, and when the probabilities are bounded away from zero, we resolve the question for all sufficiently smooth loss measures, thereby providing a coherent understanding of the rate at which distributions can be approximated from their samples.

We consider the single-unicast communication problem in a network with a delay constraint. For this setting, it has recently been shown that network coding offers an advantage over routing. We show that the existing upper bound in the literature on the capacity offered by network coding can be a factor of Θ(D) larger than the true capacity where D is the delay bound. In this work, we tighten this gap significantly to 8 log(D + 1) by proving a new upper bound. The key insight is a connection to a new traffic model that we call triangle-cast (or degraded multiple-unicast), for which we obtain a logarithmic flow-cut gap by suitably adapting the techniques from the approximation algorithms literature.

We obtain the strong data processing constant for sums of real-valued i.i.d. random variables by means of a very simple information-theoretic proof. As a corollary, we recover a classical result concerning the maximal correlation between sums of a sequence of real-valued i.i.d. random variables.

In this paper we provide the correct tight constant to a data-processing inequality claimed by Erkip and Cover. The correct constant turns out to be a particular hypercontractivity parameter of (X,Y), rather than their squared maximal correlation. We also provide alternate geometric characterizations for both maximal correlation as well as the hypercontractivity parameter that characterizes the data-processing inequality.

Consider the k-unicast network coding problem over an acyclic wireline network: Given a rate vector k-tuple, determine whether the network of interest can support k unicast flows with those rates. It is well known that the one-unicast problem is easy and that it is solved by the celebrated max-flow min-cut theorem. The hardness of k-unicast problems with small k has been an open problem. We show that the two-unicast problem is as hard as any k-unicast problem for k ≥ 3. Our result suggests that the difficulty of a network coding instance is related more to the magnitude of the rates in the rate tuple than to the number of unicast sessions. As a consequence of our result and other well-known results, we show that linear coding is insufficient to achieve capacity, and non-Shannon inequalities are necessary for characterizing capacity, even for two-unicast networks.

The problem of designing near optimal strategies for multiple unicast traffic in wireline networks is wide open; however, channel symmetry or traffic symmetry can be leveraged to show that routing can achieve with a polylogarithmic approximation factor of the edge-cut bound. For the same problem, the edge-cut bound is known to only upper bound rates of routing flows and unlike the information theoretic cut-set bound, it does not upper bound (capacity-achieving) information rates with general strategies. In this paper, we demonstrate that under channel or traffic symmetry, the edge-cut bound upper-bounds general information rates, thus providing a capacity approximation result. The key technique is a combinatorial result relating edge-cut bounds to generalized network sharing bounds. Finally, we generalize the results to wireless networks via an intermediary class of combinatorial graphs known as polymatroidal networks-our main result is that a natural architecture separating the physical and networking layers is near optimal when the traffic is symmetric among source-destination pairs, even when the channel is asymmetric (due to asymmetric power constraints, or prior frequency allocation like frequency division duplexing). This result is complementary to an earlier work of two of the authors proving a similar result under channel symmetry.

We consider in-network computation of MAX and the approximate histogram in an n-node structure-free random multihop wireless network. The key assumption that we make is that the nodes do not know their relative or absolute locations and that they do not have an identity. For the Aloha MAC protocol, we first describe a protocol in which the MAX value becomes available at the origin in O(√{n/logn}) slots (bit-periods) with high probability. This is within a constant factor of that required by the best coordinated protocol. A minimal structure (knowledge of hop-distance from the sink) is imposed on the network and with this structure, we describe a protocol for pipelined computation of MAX that achieves a rate of Ω(1/(logn)2). Finally, we show how the protocol for computation of MAX can be modified to achieve approximate computation of the histogram. The approximate histogram can be computed in O(n7/2(logn)1/2) bit-periods with high probability.

We consider sum-rate edge-cut bounds on network coding rates for the multiple unicast problem. We first show that the Generalized Network Sharing (GNS) bound is equivalent to a functional dependence bound in the literature. After defining a notion of profile of an edge-cut, we show that the only profiles for which, every edge-cut with the said profile leads to a fundamental bound on network coding rates, are the so-called GNS profiles and further, we quantify with a tight constant factor, the amount by which network coding can potentially beat edge-cuts associated with other profiles. Finally, we show that the problem of computing the GNS bound is NP-complete, even for two-unicast networks.

It has been shown recently that a simple layering principle - local physical-layer schemes combined with global routing - can achieve approximately optimal performance in wireless networks. However, this result depends heavily on the assumption of reciprocity of wireless networks, which may be violated due to asymmetric power constraints, directional antennas or frequency-duplexing. In this paper, we show that the approximate optimality continues to hold even for wireless networks modeled as directed graphs as long as there is a symmetric demand constraint: every demand from source sito sink tiat rate Rihas a counterpart demand from source node tito sink node siat the same rate. This models several practical scenarios including voice calls, video calls, and interactive gaming. We prove this result in the context of several channel models for which good local schemes exist. The key technical contributions are an outer bound based on a Generalized Network Sharing bound for wireless networks and an achievable strategy based on a connection to polymatroidal networks.

We consider the problem of multiple unicast in wireline networks. Edge-cut based bounds which are simple bounds on the rates achievable by routing flow are not in general, fundamental, i.e. they are not outer bounds on the capacity region. It has been observed that when the problem has some kind of symmetry involved, then flows and edge-cut based bounds are `close', i.e. within a constant or poly-logarithmic factor of each other. In this paper, we make the observation that in these very cases, such edge-cut based bounds are actually `close' to fundamental yielding an approximate characterization of the capacity region for these problems. We demonstrate this in the case of k-unicast in undirected networks, k-pair unicast in directed networks with symmetric demands i.e. for every source communicating to a destination at a certain rate, the destination communicates an independent message back to the source at the same rate, and sum-rate of k-groupcast in directed networks, i.e. a group of nodes, each of which has an independent message for every other node in the group. We place our work in context of existing results to suggest a meta-theorem: if there is inherent symmetry either in the network connectivity or in the traffic pattern, then edge-cut bounds are near-fundamental and flows approximately achieve capacity.

We study the scaling of the capacity per unit energy of a wireless network as a function of the number of nodes and the deployment area. We show that in a network of n nodes located randomly in a region of area scaling linearly with n and communicating over Gaussian fading channels with power pathloss exponent α, the per-node capacity per unit energy scales essentially as Θ(n1-α/2) in the low path-loss regime (2 ≤ α ≤ 3) and essentially as Θ(n-1/2) in the high path-loss regime (α ≥ 3); while if the area is held constant, it scales essentially as Θ(n) and Θ(n(α-1)/2) in the low and high path-loss regimes, respectively. We propose a novel communication scheme, phase-aligned amplify-and-forward, which is shown to be order-optimal in the low path-loss regime-no other known scheme achieves the same scaling. We show that the well-known multi-hop scheme is order-optimal in the high path-loss regime.

We investigate the two unicast flow problem over layered linear deterministic networks with arbitrary number of nodes. When the minimum cut value between each source-destination pair is constrained to be 1, it is obvious that the triangular rate region {(R1, R2) : R1, R2≥ 0, R1+ R2≤ 1} can be achieved, and that one cannot achieve beyond the square rate region {(R1, R2) : R1, R2≥ 0, R1≤ 1, R2≤ 1}. Analogous to the work by Wang and Shroff for wired networks [1], we provide the necessary and sufficient conditions for the capacity region to be the triangular region and the necessary and sufficient conditions for it to be the square region. Moreover, we completely characterize the capacity region and conclude that there are exactly three more possible capacity regions of this class of networks, in contrast to the result in wired networks where only two rate regions are possible. Our achievability scheme is based on linear coding over an extension field with at most four nodes performing special linear coding operations, namely interference neutralization and zero forcing, while all other nodes perform random linear coding.

We consider in-network computation of MAX in a structure-free random multihop wireless network. Nodes do not know their relative or absolute locations and use the Aloha MAC protocol. For one-shot computation, we describe a protocol in which the MAX value becomes available at the origin in O(radicn/ log n) slots with high probability. This is within a constant factor of that required by the best coordinated protocol. A minimal structure (knowledge of hop-distance from the sink) is imposed on the network and with this structure, we describe a protocol for pipelined computation of MAX that achieves a rate of Omega(1/(log2n)).