This work investigates binary hypothesis testing between $H_0\sim P_0$ and $H_1\sim P_1$ in the finite-sample regime under asymmetric error constraints. By employing the ``reverse" Rényi divergence, we derive novel non-asymptotic bounds on the Type II error probability which naturally establish a strong converse result. Furthermore, when the Type I error is constrained to decay exponentially with a rate $c$, we show that the Type II error converges to 1 exponentially fast if $c$ exceeds the Kullback-Leibler divergence $D(P_1\|P_0)$, and vanishes exponentially fast if $c$ is smaller. Finally, we present numerical examples demonstrating that the proposed converse bounds strictly improve upon existing finite-sample results in the literature.

This work explores properties of Strong Data-Processing constants for Rényi Divergences. Parallels are made with the well-studied $φ$-Divergences, and it is shown that the order $α$ of Rényi Divergences dictates whether certain properties of the contraction of $φ$-Divergences are mirrored or not. In particular, we demonstrate that when $α>1$, the contraction properties can deviate quite strikingly from those of $φ$-Divergences. We also uncover specific characteristics of contraction for the $\infty$-Rényi Divergence and relate it to $\varepsilon$-Local Differential Privacy. The results are then applied to bound the speed of convergence of Markov chains, where we argue that the contraction of Rényi Divergences offers a new perspective on the contraction of $L^α$-norms commonly studied in the literature.

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.

We introduce a novel concept of convergence for Markovian processes within Orlicz spaces, extending beyond the conventional approach associated with $L_p$ spaces. After showing that Markovian operators are contractive in Orlicz spaces, our technical contribution is an upper bound on their contraction coefficient, which admits a closed-form expression. The bound is tight in some settings, and it recovers well-known results, such as the connection between contraction and ergodicity, ultra-mixing and Doeblin’s minorisation. Moreover, we can define a notion of convergence of Markov processes in Orlicz spaces, which depends on the corresponding contraction coefficient. The key novelty comes from duality considerations: the convergence of a Markovian process determined by $K$ depends on the contraction coefficient of its dual $K^\star$, which can in turn be bounded by considering appropriate nested norms of densities of $K^\star$ with respect to the stationary measure. Our approach stands out as the first of its kind, as it does not rely on the existence of a spectral gap. Specialising our approach to $L_p$ spaces leads to a significant improvement upon classical Riesz-Thorin’s interpolation methods. We present the following applications of the proposed framework: \begin{enumerate} \item Tighter bounds on the mixing time of Markovian processes: one can relate the contraction coefficient of the dual operator to the mixing time of the corresponding Markov chain regardless of the norm chosen. Consequently, our tighter bound on the contraction coefficient implies a tighter bound on the mixing time. We offer a result that provides an intuitive understanding of what it means to be close in a specific norm (relating the probability of any event with the probability of the same event under the stationary measure $\pi$ and a $\psi$-Orlicz/Amemiya-norm). We then focus on $L_p$ norms and show that asking for a bounded norm with larger $p$ guarantees a faster decay in the probability. This is particularly relevant for exponentially decaying probabilities under $\pi$. Moreover, by exploiting the flexibility offered by Orlicz spaces, we can tackle settings where the stationary distribution is heavy-tailed, a severely under-studied setup. \item Improved concentration bounds for MCMC methods leading to improved lower bounds on the burn-in period: by leveraging $L_p$-norms with large $p$ and our results on the contraction coefficient, similar to the approach undertaken for the mixing times, we can provide improved exponential concentration bounds for MCMC methods. \item Improved concentration bounds for sequences of Markovian random variables: we show how our results can be used to outperform existing bounds based on a change of measure technique for random variables with a Markovian dependence. In particular, we can prove exponential concentration in new settings (inaccessible to earlier approaches) and improve the rate in others. \end{enumerate}

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.

Strong data processing inequalities (SDPI) are an important object of study in Information Theory and have been well studied for$f$-divergences. Universal upper and lower bounds have been provided along with several applications, connecting them to impossibility (converse) results, concentration of measure, hypercontractivity, and so on. In this paper, we study Renyi divergence and the corresponding SDPI constant whose behavior seems to deviate from that of ordinary-divergences. In particular, one can find examples showing that the universal upper bound relating its SDPI constant to the one of Total Variation does not hold in general. In this work, we prove, however, that the universal lower bound involving the SDPI constant of the Chi-square divergence does indeed hold. Furthermore, we also provide a characterization of the distribution that achieves the supremum when is equal to 2 and consequently compute the SDPI constant for Renyi divergence of the general binary channel.

This paper focuses on parameter estimation and introduces a new method for lower bounding the Bayesian risk. The method allows for the use of virtually any information measure, including Rényi's $\alpha$, $\varphi$-divergences, and Sibson's $\alpha$-Mutual Information. The approach considers divergences as functionals of measures and exploits the duality between spaces of measures and spaces of functions. In particular, we show that one can lower bound the risk with any information measure by upper bounding its dual via Markov's inequality. We are thus able to provide estimator-independent impossibility results thanks to the Data-Processing Inequalities that divergences satisfy. The results are then applied to settings of interest involving both discrete and continuous parameters, including the “Hide-and-Seek” problem, and compared to the state-of-the-art techniques. An important observation is that the behaviour of the lower bound in the number of samples is influenced by the choice of the information measure. We leverage this by introducing a new divergence inspired by the “Hockey-Stick” divergence, which is demonstrated empirically to provide the largest lower bound across all considered settings. If the observations are subject to privatisation, stronger impossibility results can be obtained via Strong Data-Processing Inequalities. The paper also discusses some generalisations and alternative directions.

We propose a novel approach to concentration for non-independent random variables. The main idea is to “pretend” that the random variables are independent and pay a multiplicative price measuring how far they are from actually being independent. This price is encapsulated in the Hellinger integral between the joint and the product of the marginals, which is then upper bounded leveraging tensorisation properties. Our bounds represent a natural generalisation of concentration inequalities in the presence of dependence: we recover exactly the classical bounds (McDiarmid’s inequality) when the random variables are independent. Furthermore, in a “large deviations” regime, we obtain the same decay in the probability as for the independent case, even when the random variables display non-trivial dependencies. To show this, we consider a number of applications of interest. First, we provide a bound for Markov chains with finite state space. Then, we consider the Simple Symmetric Random Walk, which is a non-contracting Markov chain, and a non-Markovian setting in which the stochastic process depends on its entire past. To conclude, we propose an application to Markov Chain Monte Carlo methods, where our approach leads to an improved lower bound on the minimum burn-in period required to reach a certain accuracy. In all of these settings, we provide a regime of parameters in which our bound fares better than what the state of the art can provide.

We propose a novel approach to concentration for non-independent random variables. The main idea is to "pretend" that the random variables are independent and pay a multiplicative price measuring how far they are from actually being independent. This price is encapsulated in the Hellinger integral between the joint and the product of the marginals, which is then upper-bounded by leveraging tensorisation properties. Our method improves upon existing results in a number of applications: a contracting Markov chain; the Simple Symmetric Random Walk, which is non-contracting; and also a non-Markovian setting. The bounds represent a natural generalisation of concentration inequalities in the presence of dependence: we recover exactly the classical bounds (McDiarmid’s inequality) when the random variables are independent. Furthermore, in a "large deviations" regime, we obtain the same decay in the probability as for the independent case, even when the random variables display non-trivial dependencies.

In this work, we connect the problem of bounding the expected generalisation error with transportation-cost inequalities. Exposing the underlying pattern behind both approaches we are able to generalise them and go beyond Kullback- Leibler Divergences/Mutual Information and sub-Gaussian measures. In particular, we are able to provide a result showing the equivalence between two families of inequalities: one involving functionals and one involving measures. This result generalises the one proposed by Bobkov and Götze that connects transportation-cost inequalities with concentration of measure. Moreover, it allows us to recover all standard generalisation error bounds involving mutual information and to introduce new, more general bounds, that involve arbitrary divergence measures.

We explore a family of information measures that stems from Rényi’s α-Divergences with α < 0. In particular, we extend the definition of Sibson’s α-Mutual Information to negative values of α and show several properties of these objects. Moreover, we highlight how this family of information measures is related to functional inequalities that can be employed in a variety of fields, including lower-bounds on the Risk in Bayesian Estimation Procedures.

We consider the problem of parameter estimation in a Bayesian setting and propose a general lower-bound that includes part of the family of f-Divergences. The results are then applied to specific settings of interest and compared to other notable results in the literature. In particular, we show that the known bounds using Mutual Information can be improved by using, for example, Maximal Leakage, Hellinger divergence, or generalizations of the Hockey-Stick divergence.

In this work, we consider the problem of parameter estimation in a Bayesian setting. We propose a new approach to lower-bounding the Bayesian risk, based on Sibson's$\alpha$-Mutual Information. The results are then applied to specific settings of interest. As an example, we provide a lower-bound on the risk of the so-called “Hide-and-Seek” problem. Generalisations of the results and alternative directions are also briefly presented.

In this work, we analyse how to define a conditional version of Sibson's$\alpha$-Mutual Information. Several such definitions can be advanced and they all lead to different information measures with different (but similar) operational meanings. We will analyse in detail one such definition, compute a closed-form expression for it and endorse it with an operational meaning while also considering some applications. The alternative definitions will also be mentioned and compared.

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.

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