Information-theoretic analysis of generalization capability of learning algorithms

Introduction

A learning algorithm can be viewed as a randomized mapping, or a channel in the information-theoretic language, which takes a training dataset as input and generates a hypothesis as output. The generalization error is the difference between the population risk of the output hypothesis and its empirical risk on the training data. It measures how much the learned hypothesis suffers from overfitting. The traditional way of analyzing the generalization error relies either on certain complexity measures of the hypothesis space, e.g. the VC dimension and the Rademacher complexity , or on certain properties of the learning algorithm, e.g., uniform stability . Recently, motivated by improving the accuracy of adaptive data analysis, Russo and Zou showed that the mutual information between the collection of empirical risks of the available hypotheses and the final output of the algorithm can be used effectively to analyze and control the bias in data analysis, which is equivalent to the generalization error in learning problems. Compared to the methods of analysis based on differential privacy, e.g., by Dwork et al. and Bassily et al. , the method proposed in is simpler and can handle unbounded loss functions; moreover, it provides elegant information-theoretic insights into improving the generalization capability of learning algorithms. In a similar information-theoretic spirit, Alabdulmohsin proposed to bound the generalization error in learning problems using the total-variation information between a random instance in the dataset and the output hypothesis, but the analysis apply only to bounded loss functions.

In this paper, we follow the information-theoretic framework proposed by Russo and Zou to derive upper bounds on the generalization error of learning algorithms. We extend the results in to the situation where the hypothesis space is uncountably infinite, and provide improved upper bounds on the expected absolute generalization error. We also obtain concentration inequalities for the generalization error, which were not given in . While the main quantity examined in is the mutual information between the collection of empirical risks of the hypotheses and the output of the algorithm, we mainly focus on relating the generalization error to the mutual information between the input dataset and the output of the algorithm, which formalizes the intuition that the less information a learning algorithm can extract from the input dataset, the less it will overfit. This viewpoint provides theoretical guidelines for striking the right balance between data fit and generalization by controlling the algorithm’s input-output mutual information. For example, we show that regularizing the empirical risk minimization (ERM) algorithm with the input-output mutual information leads to the well-known Gibbs algorithm. As another example, regularizing the ERM algorithm with random noise can also control the input-output mutual information. For both the Gibbs algorithm and the noisy ERM algorithm, we also discuss how to calibrate the regularization in order to incorporate any prior knowledge of the population risks of the hypotheses into algorithm design. Additionally, we discuss adaptive composition of learning algorithms, and show that the generalization capability of the overall algorithm can be analyzed by examining the input-output mutual information of the constituent algorithms.

Another advantage of relating the generalization error to the input-output mutual information is that the latter quantity depends on all ingredients of the learning problem, including the distribution of the dataset, the hypothesis space, the learning algorithm itself, and potentially the loss function, in contrast to the VC dimension or the uniform stability, which only depend on the hypothesis space or on the learning algorithm. As the generalization error can strongly depend on the input dataset , the input-output mutual information can be more tightly coupled to the generalization error than the traditional generalization-guaranteeing quantities of interest. We hope that our work can provide some information-theoretic understanding of generalization in modern learning problems, which may not be sufficiently addressed by the traditional analysis tools .

of i.i.d. random elements of ${\mathsf{Z}}$ with some unknown distribution $\mu$, and picks a random element $W$ of ${\mathsf{W}}$ as the output hypothesis according to $P_{W|S}$. The population risk of a hypothesis $w\in{\mathsf{W}}$ on $\mu$ is

The goal of learning is to ensure that the population risk of the output hypothesis $W$ is small, either in expectation or with high probability, under any data generating distribution $\mu$. The excess risk of $W$ is the difference $L_{\mu}(W)-\inf_{w\in{\mathsf{W}}}L_{\mu}(w)$, and its expected value is denoted as $R_{\rm excess}(\mu,P_{W|S})$. Since $\mu$ is unknown, the learning algorithm cannot directly compute $L_{\mu}(w)$ for any $w\in{\mathsf{W}}$, but can instead compute the empirical risk of $w$ on the dataset $S$ as a proxy, defined as

For a learning algorithm characterized by $P_{W|S}$, the generalization error on $\mu$ is the difference $L_{\mu}(W)-L_{S}(W)$, and its expected value is denoted as

where the expectation is taken with respect to the joint distribution $P_{S,W}=\mu^{\otimes n}\otimes P_{W|S}$. The expected population risk can then be decomposed as

Algorithmic stability in input-output mutual information

As discussed above, having a small generalization error is crucial for a learning algorithm to produce an output hypothesis with a small population risk. It turns out that the generalization error of a learning algorithm can be determined by its stability properties. Traditionally, a learning algorithm is said to be stable if a small change of the input to the algorithm does not change the output of the algorithm much. Examples include uniform stability defined by Bousquet and Elisseeff and on-average stability defined by Shalev-Shwartz et al. . In recent years, information-theoretic stability notions, such as those measured by differential privacy , KL divergence , total-variation information , and erasure mutual information , have been proposed. All existing notions of stability show that the generalization capability of a learning algorithm hinges on how sensitive the output of the algorithm is to local modifications of the input dataset. It implies that the less dependent the output hypothesis $W$ is on the input dataset $S$, the better the learning algorithm generalizes. From an information-theoretic point of view, the dependence between $S$ and $W$ can be naturally measured by the mutual information between them, which prompts the following information-theoretic definition of stability. We say that a learning algorithm is $(\varepsilon,\mu)$-stable in input-output mutual information if, under the data-generating distribution $\mu$,

Further, we say that a learning algorithm is $\varepsilon$-stable in input-output mutual information if

According to the definitions in (6) and (7), the less information the output of a learning algorithm can provide about its input dataset, the more stable it is. Interestingly, if we view the learning algorithm $P_{W|S}$ as a channel from ${\mathsf{Z}}^{n}$ to ${\mathsf{W}}$, the quantity $\sup_{\mu}I(S;W)$ can be viewed as the information capacity of the channel, under the constraint that the input distribution is of a product form. The definition in (7) means that a learning algorithm is more stable if its information capacity is smaller. The advantage of the weaker definition in (6) is that $I(S;W)$ depends on both the algorithm and the distribution of the dataset. Therefore, it can be more tightly coupled with the generalization error, which itself depends on the dataset. We mainly focus on studying the consequence of this notion of $(\varepsilon,\mu)$-stability in input-output mutual information for the rest of this paper.

Upper-bounding generalization error via I​(S;W)𝐼𝑆𝑊I(S;W)

In this section, we derive various generalization guarantees for learning algorithms that are stable in input-output mutual information.

2 Upper bound on expected generalization error

Russo and Zou considered the same problem setup with the restriction that the hypothesis space ${\mathsf{W}}$ is finite, and showed that $|{\rm gen}(\mu,P_{W|S})|$ can be upper-bounded in terms of $I(\Lambda_{{\mathsf{W}}}(S);W)$, where

is the collection of empirical risks of the hypotheses in ${\mathsf{W}}$. Using Lemma 1 by setting $X=\Lambda_{\mathsf{W}}(S)$, $Y=W$, and $f(\Lambda_{\mathsf{W}}(s),w)=L_{s}(w)$, we immediately recover the result by Russo and Zou even when ${\mathsf{W}}$ is uncountably infinite:

It should be noted that Theorem 1 can be obtained as a consequence of Theorem 2 because

which is due to the Markov chain $\Lambda_{{\mathsf{W}}}(S)-S-W$, as for each $w\in{\mathsf{W}}$, $L_{S}(w)$ is a function of $S$. However, if the output $W$ depends on $S$ only through the empirical risks $\Lambda_{{\mathsf{W}}}(S)$, in other words, when the Markov chain $S-\Lambda_{{\mathsf{W}}}(S)-W$ holds, then Theorem 1 and Theorem 2 are equivalent. The advantage of Theorem 1 is that $I(S;W)$ can be much easier to evaluate than $I(\Lambda_{\mathsf{W}}(S);W)$, and can provide better insights to guide the algorithm design. We will elaborate on this when we discuss the Gibbs algorithm and the adaptive composition of learning algorithms.

Theorem 1 and Theorem 2 only provide upper bounds on the expected generalization error. We are often interested in analyzing the absolute generalization error $|L_{\mu}(W)-L_{S}(W)|$, e.g., its expected value or the probability for it to be small. We need to develop stronger tools to tackle these problems, which is the subject of the next two subsections.

The following results show that, when $W$ is dependent on $S$, as long as $I(S;W)$ is sufficiently small, a sample complexity polynomial in $1/\alpha$ and logarithmic in $1/\beta$ still suffices to guarantee (15), where the probability now is taken with respect to the joint distribution $P_{S,W}=\mu^{\otimes n}\otimes P_{W|S}$.

Under the conditions in Theorem 3, if for some function $g(n)\geq 1$, $\varepsilon\leq(g(n)-1)\beta\log\frac{2}{\beta},$ then a sample complexity that satisfies ${n}/{g(n)}\geq\frac{8\sigma^{2}}{\alpha^{2}}\log\frac{2}{\beta}$ guarantees (15).

For example, taking $g(n)=2$, Corollary 1 implies that if $\varepsilon\leq\beta\log({2}/{\beta}),$ then (15) can be guaranteed by a sample complexity of $n=({16\sigma^{2}}/{\alpha^{2}})\log({2}/{\beta}),$ which is on the same order of the sample complexity when $S$ and $W$ are independent as in (14). As another example, taking $g(n)=\sqrt{n}$, Corollary 1 implies that if $\varepsilon\leq(\sqrt{n}-1)\beta\log({2}/{\beta}),$ then a sample complexity of $n=({64\sigma^{4}}/{\alpha^{4}})\left(\log({2}/{\beta})\right)^{2}$ guarantees (15).

A byproduct of the proof of Theorem 3 (setting $m=1$ in the proof) is an upper bound on the expected absolute generalization error.

Learning algorithms with input-output mutual information stability

In this section, we discuss several learning problems and algorithms from the viewpoint of input-output mutual information stability. We first consider two cases where the input-output mutual information can be upper-bounded via the properties of the hypothesis space. Then we propose two learning algorithms with controlled input-output mutual information by regularizing the ERM algorithm. We also discuss other methods to induce input-output mutual information stability, and the stability of learning algorithms obtained from adaptive composition of constituent algorithms.

For the ERM algorithm, the upper bounds for the expected generalization error also hold for the expected excess risk, since the empirical risk of the ERM algorithm satisfies

2 Binary Classification

where the second expectation is taken with respect to ${\mathsf{W}}_{1}$ which depends on $S_{1}$, and $c$ is a constant. Combining (22) and (23) and setting $n_{1}=n_{2}=n/2$, we have for some constant $c$,

From an information-theoretic point of view, the above two-stage algorithm effectively controls the conditional mutual information $I(S_{2};W|S_{1})$ by extracting an empirical cover of ${\mathsf{W}}$ using $S_{1}$, while maintaining a small empirical risk using $S_{2}$.

3 Gibbs algorithm

As Theorem 1 shows that the generalization error can be upper-bounded in terms of $I(S;W)$, it is natural to consider an algorithm that minimizes the empirical risk regularized by $I(S;W)$:

where $\beta>0$ is a parameter that balances fitting and generalization. To deal with the issue that $\mu$ is unknown to the learning algorithm, we can relax the above optimization problem by replacing $I(S;W)$ with an upper bound $D(P_{W|S}\|Q|P_{S})=I(S;W)+D(P_{W}\|Q),$ where $Q$ is an arbitrary distribution on ${\mathsf{W}}$ and $D(P_{W|S}\|Q|P_{S})=\int_{{\mathsf{Z}}^{n}}D(P_{W|S=s}\|Q)\mu^{\otimes n}({\rm d}s)$, so that the solution of the relaxed optimization problem does not depend on $\mu$. It turns out that the well-known Gibbs algorithm solves the relaxed optimization problem.

With the guarantee on the generalization error, we can analyze the population risk of the Gibbs algorithm. We first present a result for countable hypothesis spaces.

The distribution $Q$ in the Gibbs algorithm can be used to express our preference, or our prior knowledge of the population risks, of the hypotheses in ${\mathsf{W}}$, in a way that a higher probability under $Q$ is assigned to a hypothesis that we prefer. For example, we can order the hypotheses according to our prior knowledge of their population risks, and set $Q(w_{i})={6}/{\pi^{2}i^{2}}$ for the $i$th hypothesis in the order, then, setting $\beta=\sqrt{n}$, (29) becomes

For uncountable hypothesis spaces, we can do a similar analysis for the population risk under a Lipschitz assumption on the loss function.

Again, we can use the distribution $Q$ to express our preference of the hypotheses in ${\mathsf{W}}$. For example, we can choose $Q={\mathcal{N}}(w_{Q},b^{2}{\mathbf{I}}_{d})$ with $b=n^{-1/4}d^{-1/4}\rho^{-1/2}$ and choose $\beta=n^{3/4}d^{1/4}\rho^{1/2}$. Then, setting $a=b$ in (31), we have

4 Noisy empirical risk minimization

Another algorithm with controlled input-output mutual information is the noisy empirical risk minimization algorithm, where independent noise $N_{w}$, $w\in{\mathsf{W}}$, is added to the empirical risk of each hypothesis, and the algorithm outputs a hypothesis that minimizes the noisy empirical risks:

Similar to the Gibbs algorithm, we can express our preference of the hypotheses by controlling the amount of noise added to each hypothesis, such that our preferred hypotheses will be more likely to be selected when they have similar empirical risks as other hypotheses. The following result formalizes this idea.

where $i_{\rm o}=\operatorname*{arg\,min}_{i}L_{\mu}(w_{i})$. In particular, choosing $b_{i}={i^{1.1}}/{n^{1/3}}$, we have

5 Other methods to induce input-output mutual information stability

6 Adaptive composition of learning algorithms

Beyond analyzing the generalization error of individual learning algorithms, examining the input-output mutual information is also useful for analyzing the generalization capability of complex learning algorithms obtained by adaptively composing simple constituent algorithms. Under a $k$-fold adaptive composition, the dataset $S$ is shared by $k$ learning algorithms that are sequentially executed. For $j=1,\ldots,k$, the output $W_{j}$ of the $j$th algorithm may be drawn from a different hypothesis space ${\mathsf{W}}_{j}$ based on $S$ and the outputs $W^{j-1}$ of the previously executed algorithms, according to $P_{W_{j}|S,W^{j-1}}$. An example with $k=2$ is model selection followed by a learning algorithm using the same dataset. Various boosting techniques in machine learning can also be viewed as instances of adaptive composition. From the data processing inequality and the chain rule of mutual information,

If the Markov chain $S-\Lambda_{{\mathsf{W}}_{j}}(S)-W_{j}$ holds conditional on $W^{j-1}$ for $j=1,\ldots,k$, then the upper bound in (36) can be sharpened to $\sum_{j=1}^{k}I(\Lambda_{{\mathsf{W}}_{j}}(S);W_{j}|W^{j-1})$. We can thus control the generalization error of the final output by controlling the conditional mutual information at each step of the composition. This also gives us a way to analyze the generalization error of the composed learning algorithm using the knowledge of local generalization guarantees of the constituent algorithms.

Acknowledgement

We would like to thank Vitaly Feldman and Vivek Bagaria for pointing out errors in the earlier version of this paper. We also would like to thank Peng Guan for helpful discussions.

References

Appendix A Proof of Lemma 1

Just like Russo and Zou , we exploit the Donsker–Varadhan variational representation of the relative entropy [20, Corollary 4.15]: for any two probability measures $\pi,\rho$ on a common measurable space $(\Omega,{\mathcal{F}})$,

where the second step follows from the subgaussian assumption on $f(\bar{X},\bar{Y})$:

Inequality (A.2) gives a nonnegative parabola in $\lambda$, whose discriminant must be nonpositive, which implies

The result follows by noting that $I(X;Y)=D(P_{X,Y}\|P_{X}\otimes P_{Y})$.

Appendix B Proof of Theorem 3

To prove Theorem 3, we need the following two lemmas.

Consider the parallel execution of $m$ independent copies of $P_{W|S}$ on independent datasets $S_{1},\ldots,S_{m}$: for $t=1,\ldots,m$, an independent copy of $P_{W|S}$ takes $S_{t}\sim\mu^{\otimes n}$ as input and outputs $W_{t}$. Define $S^{m}\triangleq(S_{1},\ldots,S_{m})$. If under $\mu$, $P_{W|S}$ satisfies that $I(\Lambda_{\mathsf{W}}(S);W)\leq\varepsilon$, then the overall algorithm $P_{W^{m}|S^{m}}$ satisfies $I(\Lambda_{\mathsf{W}}(S_{1}),\ldots,\Lambda_{\mathsf{W}}(S_{m});W^{m})\leq m\varepsilon$.

The proof is based on the independence among $(S_{t},W_{t})$, $t=1,\ldots,m$, and the chain rule of mutual information. ∎

The proof is based on Lemma 1. Let $X=(\Lambda_{\mathsf{W}}(S_{1}),\ldots,\Lambda_{\mathsf{W}}(S_{m}))$, $Y=(W,T,R)$, and

Note that the upper bound in Lemma B.2 does not depend on $m$. With these lemmas, we can prove Theorem 3.

The proof is an adaptation of a “monitor technique” proposed by Bassily et al. . First, let $P_{W^{m}|S^{m}}$ be the parallel execution of $m$ independent copies of $P_{W|S}$: for $t=1,\ldots,m$, an independent copy of $P_{W|S}$ takes an independent $S_{t}\sim\mu^{\otimes n}$ as input and outputs $W_{t}$. Given $S^{m}$ and $W^{m}$, let the output of the “monitor” be a sample $(W^{*},T^{*},R^{*})$ drawn from ${\mathsf{W}}\times[m]\times\{\pm 1\}$ according to

Taking expectation on both sides, we have

Note that conditional on $W^{m}$, the tuple $(W^{*},T^{*},R^{*})$ can take only $2m$ values, which means that

In addition, since $P_{W|S}$ is assumed to satisfy $I(\Lambda_{\mathsf{W}}(S);W)\leq\varepsilon$, Lemma B.1 implies that

Therefore, by the chain rule of mutual information and the data processing inequality, we have

The rest of the proof is by contradiction. Choose $m=\lfloor 1/\beta\rfloor$. Suppose the algorithm $P_{W|S}$ does not satisfy the claimed generalization property, namely,

Then by the independence among the pairs $(S_{t},W_{t})$, $t=1,\ldots,m$,

which contradicts the condition in (16). Therefore, under the condition in (16), the assumption in (B.8) cannot hold. This completes the proof. ∎

Appendix C Proof of Theorem 5

To solve the relaxed optimization problem in (26), first note that

It follows that for each $s\in{\mathsf{Z}}^{n}$, the algorithm $P^{*}_{W|S}$ that minimizes (26) satisfies

This is a simple convex optimization problem. The solution to (C.12) for each $s\in{\mathsf{Z}}^{n}$ turns out to be the Gibbs algorithm as described in (27), which does not depend on $\mu$.

Appendix D Proof of Corollary 2

We can bound the expected empirical risk of the Gibbs algorithm $P^{*}_{W|S}$ as

This leads to (29), as $D(\delta_{w_{\rm o}}\|Q)=-\log{Q(w_{\rm o})}$ when ${\mathsf{W}}$ is countable.

Appendix E Proof of Corollary 3

Similar to the proof of Corollary 2, we first bound the expected empirical risk of the Gibbs algorithm $P^{*}_{W|S}$. For any $a>0$, ${\mathcal{N}}(w_{\rm o},a^{2}{\mathbf{I}}_{d})$ can be viewed as a learning algorithm that ignores the dataset and always draws a hypothesis from this distribution. The nonnegativity of relative entropy and Theorem 5 imply that

Combining with the upper bound on the expected generalization error (28), we obtain

Substituting this into (E.19), we obtain (31).

Appendix F Proof of Corollary 4

We prove the result assuming $|{\mathsf{W}}|=k$. When ${\mathsf{W}}$ is countably infinite, the proof carries over by replacing $k$ with $\infty$.

First, we upper-bound the expected generalization error via $I(S;W)$. We have the following chain of inequalities:

Then, we upper-bound the expected empirical risk. From the definition of the algorithm, we have that with probability one,

which leads to (34) with the fact that $\log(1+x)\leq x$.

When $b_{i}={i^{1.1}}/{n^{1/3}}$, using the fact that

and upper-bounding $L_{\mu}(w_{i})$’s by $1$, we get