Information measures can be constructed from Rényi divergences much like mutual information from Kullback-Leibler divergence. One such information measure is known as Sibson α-mutual information and has received renewed attention recently in several contexts: concentration of measure under dependence, statistical learning, hypothesis testing, and estimation theory. In this paper, we survey and extend the state of the art. In particular, we introduce variational representations for Sibson α-mutual information and employ them in each described context to derive novel results. Namely, we produce generalized Transportation-Cost inequalities and Fano-type inequalities. We also present an overview of known applications, spanning from learning theory and Bayesian risk to universal prediction.

A generalized notion of “relative entropy typicality” is introduced. The new definition accommodates non-i.i.d. scenarios and is parameterized by two families of parameters,$\left\{\delta^{[n]}\right\}_{n}$and$\left\{\epsilon^{[n]}\right\}_{n}$: the choice of$\left\{\delta^{[n]}\right\}_{n}$(the allowed “deviation” in the relative entropy typical set) can be optimized as a function of$\left\{\epsilon^{[n]}\right\}_{n}$, where ($1-\epsilon^{[n]}$) is the desired probability of the set. This generalized definition is shown to yield an extension of the Chernoff-Stein lemma, which characterizes the rate of decay of the type II error in hypothesis testing (under a fixed type I error constraint) as the KL divergence. In particular, the generalization accommodates both discrete and continuous random variables, non-i.i.d. settings, in addition to cases where the KL divergence grows non-linearly. Several example applications are discussed, including testing two correlated Gaussian distributions.

Hyperspectral imaging is an important tool used in plant health assessment. It allows for early detection of plant stress prior to the onset of visual symptoms, which allows for timely intervention and improved conservation efforts. However, the high cost and complexity of hyperspectral cameras has limited their usage. To mitigate this issue, the problem of reconstructing plant hyperspectral data from RGB images is investigated. The proposed model reconstructs the visual and near-infrared range (400 - 1000 nm) while being trained solely on images of vegetation, in contrast with existing "generic" models. It is hypothesized that training a less complex model on a specific material (i.e., vegetation) will achieve good accuracy even with a relatively small training dataset. The HSCNN-D model (winner of NTIRE 2018 competition) is adopted with a simplified architecture. Despite training a much smaller version of the original model, it achieves comparable performance to state-of-the-art models on images of vegetation.

Given two random variables$X$and$Y$, the maximal leakage$\mathcal{L}(X\rightarrow Y)$from$X$to$Y$was recently proposed as an operational privacy measure. Maximal leakage quantifies the multiplicative increase of the probability of correctly guessing any randomized function of$X$- after observing$\mathrm{Y}$-. This work investigates the properties of maximal leakage in the situation where only certain functions of$X$- are assumed to be of interest to the adversary; specifically, the focus is on measuring maximal leakage with respect to all binary functions of$X$. A definition for binary leakage$\mathcal{L}_{2}^{\ast }(X\rightarrow Y)$is proposed and a characterization theorem for this new measure is derived. The new privacy measure is shown to satisfy standard properties, such as composition theorems and the data processing inequalities. Many of the stated results naturally extend to$C_{k}^{\ast }(X\rightarrow Y)$which assumes the function of interest is$k$-valued. Finally, a relation between the binary leakage and the Dobrushin coefficient is established, and possible applications of this relation are explored.

Sibson's$\alpha$-mutual information has received renewed attention recently in several contexts: concentration of measure under dependence, statistical learning, hypothesis testing, and estimation theory. In this work, we introduce several variational representations of Sibson's$\alpha$-mutual information: 1) as a supremum over joint distributions of (a combination of) KL divergences; and 2) as a supremum over functions of opportune expected values. Leveraging them, we produce a variety of novel and known results, including a generalization of transportation-cost inequalities and Fano's inequality.

We characterize the growth of the Sibson and Arimoto mutual informations and$\alpha $-maximal leakage, of any order that is at least unity, between a random variable and a growing set of noisy, conditionally independent and identically-distributed observations of the random variable. Each of these measures increases exponentially fast to a limit that is order- and measure-dependent, with an exponent that is order- and measure-independent.

The framework of approximate differential privacy is considered, and augmented by introducing the notion of "the total variation of a (privacy-preserving) mechanism" (denoted by η-TV). With this refinement, an exact composition result is derived, and shown to be significantly tighter than the optimal bounds for differential privacy (which do not consider the total variation). Furthermore, it is shown that (ε, δ)-DP with η-TV is closed under subsampling. Finally, the induced total variation of commonly used mechanisms are computed.

Given a binary random variable X representing sensitive information and n noisy observations Y1, Y2, … , Ynavailable to an adversary, we analyze the maximal leakage $\mathcal{L}\left( {X \to {Y^n}} \right)$ in the following setting modeling adaptive attacks. At each stage i, the adversary may choose an action to interact with the system containing X to obtain Yi. The action may depend on previous realizations of the observations, but the leakage at each stage is limited. We derive an adaptive composition theorem wherein $\mathcal{L}\left( {X \to {Y^n}} \right)$ is bounded in terms of the leakage of each stage. Furthermore, we show that the bound is achieved for $\mathcal{L}\left( {X \to {Z^n}} \right)$ where (Z1, Z2, … , Zn) are conditionally independent given X and each Zicorresponds to the output of a binary erasure channel with the appropriate parameter; moreover, X −Zn−Yncan be coupled as a Markov chain for any feasible Yn. As a corollary of this result and the asymptotic analysis of composition by Wu et al., we show that the binary erasure channel maximizes the Chernoff information between the "rows" of binary-input channels given a maximal leakage constraint. On the other hand, we show that the binary symmetric channel minimizes the Chernoff information for a given maximal leakage constraint.

We study the probability distribution of age of information (AoI) in arbitrary networks with memoryless service times. A source node generates packets following a Poisson process, and then the packets are forwarded across the network in such a way that newer updates preempt older ones. This model is equivalent to gossip networks that were recently studied by Yates, and for which he obtained a recursive formula allowing the computation for the average AoI. In this paper, we obtain a very simple characterization of the stationary distribution of AoI at every node in the network. This allows for the computation of the average of an arbitrary function of the age, such as the age-violation probabilities. Furthermore, we show how our simple characterization can yield substantial reductions in the computation time of average AoIs in some structured networks. Finally, we describe how it can yield faster and more accurate Monte Carlo simulations estimating the average AoI, or the average of an arbitrary function of the age.

In this work, the probability of an event under some joint distribution is bounded by measuring it with the product of the marginals instead (which is typically easier to analyze) together with a measure of the dependence between the two random variables. These results find applications in adaptive data analysis, where multiple dependencies are introduced and in learning theory, where they can be employed to bound the generalization error of a learning algorithm. Bounds are given in terms of Sibson's Mutual Information, α-Divergences, Hellinger Divergences, and f-Divergences. A case of particular interest is the Maximal Leakage (or Sibson's Mutual Information of order infinity), since this measure is robust to post-processing and composes adaptively. The corresponding bound can be seen as a generalization of classical bounds, such as Hoeffding's and McDiarmid's inequalities, to the case of dependent random variables.

Given two probability measures P and Q and an event E, we provide bounds on P(E) in terms of Q(E) and f-divergences. In particular, the bounds are instantiated when the measures considered are a joint distribution and the corresponding product of marginals. This allows us to control the measure of an event under the joint, using the product of the marginals (typically easier to compute) and a measure of how much the two distributions differ, i.e., an f-divergence between the joint and the product of the marginals, also known in the literature as f-Mutual Information. The result is general enough to induce, as special cases, bounds involving χ2-divergence, Hellinger distance, Total Variation, etc. Moreover, it also recovers a result involving Rényi's α-divergence. As an application, we provide bounds on the generalization error of learning algorithms via f-divergences.

We characterize the growth of the Sibson mutual information, of any order that is at least unity, between a random variable and an increasing set of noisy, conditionally independent observations of the random variable. The Sibson mutual information increases to an order-dependent limit exponentially fast, with an exponent that is order-independent. The result is contrasted with composition theorems in differential privacy.

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.

The entropy of a quantum system is a measure of its randomness and is useful in quantifying entanglement. We study the problem of measuring the von Neumann and Rényi entropies of an unknown mixed quantum state given access to independent copies of the state. For Rényi entropy of integral order exceeding one, we determine the order-optimal copy complexity and show that it is strictly lower than the number of copies required to learn the underlying state. The main technical innovation is a concentration result for certain polynomials that arise in the Kerov algebra of Young diagrams, which is proven using the cycle structure of compositions of certain types of permutations. For von Neumann entropy and Rényi entropy of non-integral orders, we provide upper and lower bounds on the sample complexity of the Empirical Young Diagram (EYD) algorithm, which is the analogue of the empirical plug-in estimator in classical estimation.

The following problem is considered: given a joint distribution PXYand an event E, bound PXY(E) in terms of PXPY(E) (where PXPYis the product of the marginals of PXY) and a measure of dependence of X and Y. Such bounds have direct applications in the analysis of the generalization error of learning algorithms, where E represents a large error event and the measure of dependence controls the degree of overfitting. Herein, bounds are demonstrated using several information-theoretic metrics, in particular: mutual information, lautum information, maximal leakage, and J∞. The mutual information bound can outperform comparable bounds in the literature by an arbitrarily large factor.

There has been growing interest in studying connections between generalization error of learning algorithms and information measures. In this work, we generalize a result that employs the maximal leakage, a measure of leakage of information, and explore how this bound can be applied in different scenarios. The main application can be found in bounding the generalization error. Rather than analyzing the expected error, we provide a concentration inequality. In this work, we do not require the assumption of σ-sub gaussianity and show how our results can be used to retrieve a generalization of the classical bounds in adaptive scenarios (e.g., McDiarmid's inequality for c-sensitive functions, false discovery error control via significance level, etc.).

Adaptive data analysis is known to introduce bias in reported measurements. Russo and Zou [1] recently introduced an information-theoretic framework to study this problem. Herein, this framework is adopted and new dependence measures are introduced to bound the exploration bias. When the measurements have bounded L1- or L2-norms, or when the selection procedure is symmetric, the new bounds are such that the contribution of the selection procedure to the bias is decoupled from the effects of the underlying distribution generating the data, thus enabling direct comparisons between different selection procedures.

Maximal leakage from a random variable X to a random variable Y is defined as the multiplicative increase, upon observing Y, of the probability of correctly guessing a randomized function of X, maximized over all such functions [1]. Herein, this guessing framework is used to give operational definitions to common information leakage metrics, including Shannon capacity, maximal correlation, and local differential privacy. Shannon capacity is shown to capture the multiplicative increase of the probability of correct guessing over the restricted set of functions of X that can be reliably reconstructed from Y, hence underestimating leakage. Maximal correlation is shown to capture the multiplicative change in the variance of functions of X, rather than the guessing probability. Local differential privacy is shown to capture the multiplicative increase of the guessing probability of functions of X, maximized over realizations of Y and over distributions Px. Moreover, maximizing over realizations of Y for a fixed Pxis shown to yield a valid leakage measure, which is equal to the maximum information rate.

The secrecy of a communication system in which both the legitimate receiver and an eavesdropper are allowed some distortion is investigated. The secrecy metric considered is the exponent of the probability that the eavesdropper estimates the source sequence successfully within an acceptable distortion level. The problem is first studied when the transmitter and the legitimate receiver do not share any key and the transmitter is not subject to a rate constraint, which corresponds to a stylized model of a side channel and reveals connections to source coding with side information. The setting is then generalized to include a shared secret key between the transmitter and the legitimate receiver and a rate constraint on the transmitter, which corresponds to the Shannon cipher system. A single-letter characterization of the highest achievable exponent is provided, and asymptotically optimal strategies for both the primary user and the eavesdropper are demonstrated.

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.

We consider the two-hop interference channel (IC), which consists of two source-destination pairs communicating with each other via two relays. We analyze the degrees of freedom (DoF) of this network when the relays are restricted to perform linear schemes, and the channel gains are constant (i.e., slow fading). We show that, somewhat surprisingly, by using vector-linear strategies at the relays, it is possible to achieve 4/3 sum-DoF when the channel gains are real. The key achievability idea is to alternate relaying coefficients across time, to create different end-to-end interference structures (or topologies) at different times. Although each of these topologies has only 1 sum-DoF, we manage to achieve 4/3 by coding across them. Furthermore, we develop a novel outer bound that matches our achievability, hence characterizing the sum-DoF of two-hop ICs with linear schemes. We also generalize the result to the multi-antenna setting, where each node has M antennas, and the relays are restricted to one-shot linear schemes. We further extend the result to the case of complex channel gains, by intuitively viewing each complex node with M antennas as a real node with 2M antennas, and characterize the sum-DoF to be 2M - 1/3.

We consider the two-hop interference channel (IC) with constant real channel coefficients, which consists of two source-destination pairs, separated by two relays. We analyze the achievable degrees of freedom (DoF) of such network when relays are restricted to perform scalar amplify-forward (AF) operations, with possibly time-varying coefficients. We show that, somewhat surprisingly, by providing the flexibility of choosing time-varying AF coefficients at the relays, it is possible to achieve 4/3 sum-DoF. We also develop a novel outer bound that matches our achievability, hence characterizing the sum-DoF of two-hop interference channels with time-varying AF relaying strategies.