We introduce a new information-theoretic complexity measure @math for 2-party functions which is a lower-bound on communication complexity, and has the two leading lower-bounds on communication complexity as its natural relaxations: (external) information complexity ( @math ) and logarithm of partition complexity ( @math ), which have so far appeared conceptually quite different from each other. @math is an external information complexity measure based on R 'enyi mutual information of order infinity. In the definition of @math , relaxing the order of R 'enyi mutual information from infinity to 1 yields @math , while @math is obtained by replacing protocol transcripts with what we term "pseudotranscripts," which omits the interactive nature of a protocol, but only requires that the probability of any transcript given the inputs @math and @math to the two parties, factorizes into two terms which depend on @math and @math separately. Further understanding @math might have consequences for important direct-sum problems in communication complexity, as it lies between communication complexity and information complexity. We also show that applying both the above relaxations simultaneously to @math gives a complexity measure that is lower-bounded by the (log of) relaxed partition complexity, a complexity measure introduced by (FOCS 2012). We obtain a sharper connection between (external) information complexity and relaxed partition complexity than , using an arguably more direct proof.
Recently, the authors of this work proposed a distributional complexity measure, Wyner tension (or more generally, tension gap) which is a lower bound for information complexity @cite_24 . We leave it for future work to explore the exact connections between these bounds and the ones in the current work. We mention that for the case when the inputs are independent, Wyner tension is identical to (defined in extensions ), and a result in @cite_24 is subsumed by the results in this work.
@cite_24
1793958621 2553864996 2962961444 2411019220
The main contribution of this work is to relate information complexity to "tension" [Prabhakaran and Prabhakaran, 2014] - an information-theoretic quantity defined with no reference to protocols - and to illustrate that it allows deriving strong lower-bounds on information complexity. In particular, we use a very special case of this connection to give a quantitatively tighter connection between information complexity and discrepancy than the one in the work of Braverman and Weinstein (2012) (albeit, restricted to independent inputs). Further, as tension is in fact a multi-dimensional notion, it enables us to bound the 2-dimensional region that represents the trade-off between the amounts of communication in the two directions in a 2-party protocol. This work is also intended to highlight tension as a fundamental measure of correlation between a pair of random variables, with rich connections to a variety of questions in computer science and information theory. Wyner defined the notion of common information of two discrete random variables as the minimum of I(W; X, Y) where W induces conditional independence between X and Y. Its generalization to multiple dependent random variables revealed a surprising monotone property in the number of variables. Motivated by this monotonicity property, this paper explores the application of Wyner's common information to inference problems and its connection with other performance metrics. A central question is that under what conditions Wyner's common information captures the entire information contained in the observations about the inference object under a simple Bayesian model. For infinitely exchangeable random variables, it is shown using the de Finetti-Hewitt-Savage theorem that the common information is asymptotically equal to the information of the inference object. For finite exchangeable random variables, such conclusion is no longer true even for infinitely extendable sequences. However, for some special cases, including both the binary and the Gaussian cases, concrete connection between common information and inference performance metrics can be established even for finite samples. We present an information-theoretic approach to lower bound the oracle complexity of nonsmooth black box convex optimization, unifying previous lower bounding techniques by identifying a combinatorial problem, namely string guessing, as a single source of hardness. As a measure of complexity, we use distributional oracle complexity, which subsumes randomized oracle complexity as well as worst case oracle complexity. We obtain strong lower bounds on distributional oracle complexity for the box @math , as well as for the @math -ball for @math (for both low-scale and large-scale regimes), matching worst case upper bounds, and hence we close the gap between distributional complexity, and in particular, randomized complexity and worst case complexity. Furthermore, the bounds remain essentially the same for high-probability and bounded-error oracle complexity, and even for combination of the two, i.e., bounded-error high-probability oracle complexity. This considerably extends the applicability of known bounds. We show an exponential gap between communication complexity and external information complexity, by analyzing a communication task suggested as a candidate by Braverman. Previously, only a separation of communication complexity and internal information complexity was known. More precisely, we obtain an explicit example of a search problem with external information complexity ≤ O(k), with respect to any input distribution, and distributional communication complexity ≥ 2k, with respect to some input distribution. In particular, this shows that a communication protocol cannot always be compressed to its external information. By a result of Braverman, our gap is the largest possible. Moreover, since the upper bound of O(k) on the external information complexity of the problem is obtained with respect to any input distribution, our result implies an exponential gap between communication complexity and information complexity (both internal and external) in the non-distributional setting of Braverman. In this setting, no gap was previously known, even for internal information complexity.