PAC-Bayesian Inequalities for Martingales

I Introduction

Martingales are one of the fundamental tools in probability theory and statistics for modeling and studying sequences of random variables. Some of the most well-known and widely used concentration inequalities for individual martingales are Hoeffding-Azuma’s and Bernstein’s inequalities . We present a comparison inequality that bounds the expectation of a convex function of a martingale difference sequence shifted to the $$ interval by the expectation of the same function of independent Bernoulli variables. We apply this inequality in order to derive a tighter analog of Hoeffding-Azuma’s inequality for martingales.

More importantly, we present a set of inequalities that make it possible to control weighted averages of multiple simultaneously evolving and interdependent martingales (see Fig. 1 for an illustration). The inequalities are especially interesting when the number of martingales is uncountably infinite and the standard union bound over the individual martingales cannot be applied. The inequalities hold with high probability simultaneously for a large class of averaging laws $\rho$. In particular, $\rho$ can depend on the sample.

One possible application of our inequalities is an analysis of importance-weighted sampling. Importance-weighted sampling is a general and widely used technique for estimating properties of a distribution by drawing samples from a different distribution. Via proper reweighting of the samples, the expectation of the desired statistics based on the reweighted samples from the controlled distribution can be made identical to the expectation of the same statistics based on unweighted samples from the desired distribution. Thus, the difference between the observed statistics and its expected value forms a martingale difference sequence. Our inequalities can be applied in order to control the deviation of the observed statistics from its expected value. Furthermore, since the averaging law $\rho$ can depend on the sample, the controlled distribution can be adapted based on its outcomes from the preceding rounds, for example, for denser sampling in the data-dependent regions of interest. See for an example of an application of this technique in reinforcement learning.

Our concentration inequalities for weighted averages of martingales are based on a combination of Donsker-Varadhan’s variational formula for relative entropy with bounds on certain moment generating functions of martingales, including Hoeffding-Azuma’s and Bernstein’s inequalities, as well as the new inequality derived in this paper.

The weighted averages $\langle\phi,\rho\rangle$ on the left hand side of (2) are the quantities of interest and the inequality allows us to relate all possible averaging laws $\rho$ to a single “reference” distribution $\pi$. (Sometimes, $\pi$ is also called a “prior” distribution, since it has to be selected before observing the sample.) We emphasize that inequality (2) is a deterministic relation. Thus, by a single application of Markov’s inequality to $\langle e^{\phi},\pi\rangle$ we obtain a statement that holds with high probability for all $\rho$ simultaneously. The quantity $\ln\langle e^{\phi},\pi\rangle$, known as the cumulant-generating function of $\phi$, is closely related to the moment-generating function of $\phi$. The bound on $\ln\langle e^{\phi},\pi\rangle$, after some manipulations, is achieved via the bounds on moment-generating functions, which are identical to those used in the proofs of Hoeffding-Azuma’s, Bernstein’s, or our new inequality, depending on the choice of $\phi$.

Donsker-Varadhan’s variational formula for relative entropy laid the basis for PAC-Bayesian analysis in statistical learning theory , where PAC is an abbreviation for the Probably Approximately Correct learning model introduced by Valiant . PAC-Bayesian analysis provides high probability bounds on the deviation of weighted averages of empirical means of sets of independent random variables from their expectations. In the learning theory setting, the space ${\cal H}$ usually corresponds to a hypothesis space; the function $\phi(h)$ is related to the difference between the expected and empirical error of a hypothesis $h$; the distribution $\pi$ is a prior distribution over the hypothesis space; and the distribution $\rho$ defines a randomized classifier. The randomized classifier draws a hypothesis $h$ from ${\cal H}$ according to $\rho$ at each round of the game and applies it to make the prediction on the next sample. PAC-Bayesian analysis supplied generalization guarantees for many influential machine learning algorithms, including support vector machines , linear classifiers , and clustering-based models , to name just a few of them.

We show that PAC-Bayesian analysis can be extended to martingales. A combination of PAC-Bayesian analysis with Hoeffding-Azuma’s inequality was applied by Lever et. al in the analysis of U-statistics. The results presented here are both tighter and more general, and make it possible to apply PAC-Bayesian analysis in new domains, such as, for example, reinforcement learning .

II Main Results

We first present our new inequalities for individual martingales, and then present the inequalities for weighted averages of martingales. All the proofs are provided in the appendix.

Our first lemma is a comparison inequality that bounds expectations of convex functions of martingale difference sequences shifted to the $$interval by expectations of the same functions of independent Bernoulli random variables. The lemma generalizes a previous result by Maurer for independent random variables . The lemma uses the following notation: for a sequence of random variables$X_{1},\dots,X_{n}$we use$X_{1}^{i}:=X_{1},\dots,X_{i}$to denote the first$i$ elements of the sequence.

We apply Lemma 1 in order to derive the following inequality, which is an interesting generalization of an analogous result for i.i.d. variables. The result is based on the method of types in information theory .

Let $X_{1},\dots,X_{n}$ be as in Lemma 2. Then, for any $\delta\in(0,1)$, with probability greater than $1-\delta$:

II-B PAC-Bayesian Inequalities for Weighted Averages of Martingales

Next, we present several inequalities that control the concentration of weighted averages of multiple simultaneously evolving and interdependent martingales. The first result shows that the classical PAC-Bayesian theorem for independent random variables holds in the same form for martingales. The result is based on combination of Donsker-Varadhan’s variational formula for relative entropy with Lemma 2. In order to state the theorem we need a few definitions.

Let $\bar{S}_{n}:=\sum_{i=1}^{n}\bar{X}_{i}$. In the following theorem we are bounding the mean of $\bar{S}_{n}$ with respect to any probability measure $\rho$ over ${\cal H}$.

Fix a reference distribution $\pi$ over ${\cal H}$. Then, for any $\delta\in(0,1)$, with probability greater than $1-\delta$ over $\bar{X}_{1},\dots,\bar{X}_{n}$, for all distributions $\rho$ over ${\cal H}$ simultaneously:

By Pinsker’s inequality, Theorem 4 implies that

however, if $\left\langle\frac{1}{n}\bar{S}_{n},\rho\right\rangle$ is close to zero or one, inequality (5) is significantly tighter than (6).

Let $\bar{M}_{i}:=\sum_{j=1}^{i}\bar{Z}_{j}$. Then, for each $h\in{\cal H}$ the sequence $\bar{M}_{1}(h),\dots,\bar{M}_{n}(h)$ is a martingale. In the following theorems we bound the mean of $\bar{M}_{n}$ with respect to any probability measure $\rho$ on ${\cal H}$.

Assume that $\bar{Z}_{i}:{\cal H}\rightarrow[\alpha_{i},\beta_{i}]$. Fix a reference distribution $\pi$ over ${\cal H}$ and $\lambda>0$. Then, for any $\delta\in(0,1)$, with probability greater than $1-\delta$ over $\bar{Z}_{1}^{n}$, for all distributions $\rho$ over ${\cal H}$ simultaneously:

Assume that $\bar{Z}_{1}^{n}$ is as in Theorem 5. Fix a reference distribution $\pi$ over ${\cal H}$. Take an arbitrary number $c>1$. Then, for any $\delta\in(0,1)$, with probability greater than $1-\delta$ over $\bar{Z}_{1}^{n}$, for all distributions $\rho$ over ${\cal H}$ simultaneously:

Assume that $\|\bar{Z}_{i}\|_{\infty}\leq K$ for all $i$ with probability 1 and pick $\lambda$, such that $\lambda\leq 1/K$. Fix a reference distribution $\pi$ over ${\cal H}$. Then, for any $\delta\in(0,1)$, with probability greater than $1-\delta$ over $\bar{Z}_{1}^{n}$, for all distributions $\rho$ over ${\cal H}$ simultaneously:

As in the previous case, the right hand side of (9) cannot be minimized for all $\rho$ simultaneously by a single value of $\lambda$. Furthermore, $\bar{V}_{n}$ is a random function. In the following theorem we take a similar grid of $\lambda$-s, as we did in Theorem 6, and a union bound over the grid. Picking a value of $\lambda$ from the grid closest to the value of $\lambda$ that minimizes the right hand side of (9) yields almost as good result as we would get if we would minimize (9) for a single choice of $\rho$. In this approach the variance $\bar{V}_{n}$ can be replaced by a sample-dependent upper bound. For example, in importance-weighted sampling such an upper bound is derived from the reciprocal of the sampling distribution at each round .

Assume that $\|\bar{Z}_{i}\|_{\infty}\leq K$ for all $i$ with probability 1. Fix a reference distribution $\pi$ over ${\cal H}$. Pick an arbitrary number $c>1$. Then, for any $\delta\in(0,1)$, with probability greater than $1-\delta$ over $\bar{Z}_{1}^{n}$, simultaneously for all distributions $\rho$ over ${\cal H}$ that satisfy

($\lceil x\rceil$ is the smallest integer value that is larger than $x$.)

III Comparison of the Inequalities

We first recall Hoeffding-Azuma’s inequality . For a sequence of random variables $Z_{1},\dots,Z_{n}$ we use $Z_{1}^{i}:=Z_{1},\dots,Z_{i}$ to denote the first $i$ elements of the sequence.

By combining Hoeffding-Azuma’s inequality with Markov’s inequality and taking $\lambda=\sqrt{\frac{8\ln\frac{2}{\delta}}{\sum_{i=1}^{n}(\beta_{i}-\alpha_{i})^{2}}}$ it is easy to obtain the following corollary.

For $M_{n}$ defined in Lemma 9 and $\delta\in(0,1)$, with probability greater than $1-\delta$:

The next lemma is a Bernstein-type inequality . We provide the proof of this inequality in Appendix C, the proof is a part of the proof of [21, Theorem 1].

By combining Lemma 11 with Markov’s inequality we obtain that for any $\lambda\in[0,\frac{1}{K}]$ and $\delta\in(0,1)$, with probability greater than $1-\delta$:

$V_{n}$ is a random variable and can be replaced by an upper bound. Inequality (14) is minimized by $\lambda^{*}=\sqrt{\frac{\ln\frac{2}{\delta}}{(e-2)V_{n}}}$. Note that $\lambda^{*}$ depends on $V_{n}$ and is not accessible until we observe the entire sample. We can bypass this problem by constructing the same grid of $\lambda$-s, as the one used in the proof of Theorem 8, and taking a union bound over it. Picking a value of $\lambda$ closest to $\lambda^{*}$ from the grid leads to the following corollary. In this bounding technique the upper bound on $V_{n}$ can be sample-dependent, since the bound holds simultaneously for all $\lambda$-s in the grid. Despite being a relatively simple consequence of Lemma 11, we have not seen this result in the literature. The corollary is tighter than an analogous result by Beygelzimer et. al. [21, Theorem 1].

For $M_{n}$ and $V_{n}$ as defined in Lemma 11, $c>1$ and $\delta\in(0,1)$, with probability greater than $1-\delta$, if

where $\nu$ is defined in (12), and otherwise

The technical condition (15) follows from the requirement of Lemma 11 that $\lambda\in[0,\frac{1}{K}]$.

III-B Comparison

We first compare inequalities for individual martingales in Corollaries 3, 10, and 12.

IV Discussion

We presented a comparison inequality that bounds expectation of a convex function of martingale difference type variables by expectation of the same function of independent Bernoulli variables. This inequality enables to reduce a problem of studying continuous dependent random variables on a bounded interval to a much simpler problem of studying independent Bernoulli random variables.

As an example of an application of our lemma we derived an analog of Hoeffding-Azuma’s inequality for martingales. Our result is always comparable to Hoeffding-Azuma’s inequality up to a logarithmic factor and in cases, where the empirical drift of a corresponding random walk is close to the region boundaries it is tighter than Hoeffding-Azuma’s inequality by an order of magnitude. It can also be tighter than Bernstein’s inequality for martingales, unless there is a tight bound on the martingale variance.

Finally, but most importantly, we presented a set of inequalities on concentration of weighted averages of multiple simultaneously evolving and interdependent martingales. These inequalities are especially useful for controlling uncountably many martingales, where standard union bounds cannot be applied. Martingales are one of the most basic and important tools for studying time-evolving processes and we believe that our results will be useful for multiple domains. One such application in analysis of importance weighted sampling in reinforcement learning was already presented in .

Appendix A Proofs of the Results for Individual Martingales

The proof follows the lines of the proof of Maurer [19, Lemma 3]. Any point $\bar{x}=(x_{1},\dots,x_{n})\in^{n}$ can be written as a convex combination of the extreme points $\bar{\eta}=(\eta_{1},\dots,\eta_{n})\in\{0,1\}^{n}$ in the following way:

with equality if $\bar{x}\in\{0,1\}^{n}$. Let $X_{1}^{i}:=X_{1},\dots,X_{i}$ be the first $i$ elements of the sequence $X_{1},\dots,X_{n}$. Let $W_{i}(\eta_{i})=(1-X_{i})(1-\eta_{i})+X_{i}\eta_{i}$ and let $w_{i}(\eta_{i})=(1-b_{i})(1-\eta_{i})+b_{i}\eta_{i}$. Note that by the assumption of the lemma:

By taking expectation of both sides of (16) we obtain:

In (17) we apply induction in order to replace $X_{i}$ by $b_{i}$, one-by-one from the last to the first, same way we did it for $X_{n}$. ∎

Lemma 2 follows from the following concentration result for independent Bernoulli variables that is based on the method of types in information theory . Its proof can be found in .

Corollary 3 follows from Lemma 2 by Markov’s inequality.

For $\delta\in(0,1)$ and a random variable $X\geq 0$, with probability greater than $1-\delta$$:$

By Markov’s inequality and Lemma 2, with probability greater than $1-\delta$:

Taking logarithm of both sides of the inequality and normalizing by $n$ completes the proof. ∎

Appendix B Proofs of PAC-Bayesian Theorems for Martingales

In this appendix we provide the proofs of Theorems 4, 7, and 8. The proof of Theorem 5 is very similar to the proof of Theorem 7 and, therefore, omitted. The proof of Theorem 6 is very similar to the proof of Theorem 8, so we only provide the way of how to choose the grid of $\lambda$-s in this theorem.

The proofs of all PAC-Bayesian theorems are based on the following lemma, which is obtained by changing sides in Donsker-Varadhan’s variational definition of relative entropy. The lemma takes roots back in information theory and statistical physics . The lemma provides a deterministic relation between averages of $\phi$ with respect to all possible distributions $\rho$ and the cumulant generating function $\ln\langle e^{\phi},\pi\rangle$ with respect to a single reference distribution $\pi$. A single application of Markov’s inequality combined with the bounds on moment generating functions in Lemmas 2, 9, and 11 is then used in order to bound the last term in (20) in the proofs of Theorems 4, 5, and 7, respectively.

Since the KL-divergence is infinite when the support of $\rho$ exceeds the support of $\pi$, inequality (20) is interesting when $\pi\gg\rho$. For a similar reason, it is interesting only when $\langle e^{\phi},\pi\rangle$ is finite. We note that the inequality is tight in the same sense as Jensen’s inequality is tight: for $\phi(h)=\ln\frac{\rho(h)}{\pi(h)}$ it becomes an equality.

For the proof of Theorem 7 we take $\phi(h):=\lambda\bar{M}_{n}(h)-(e-2)\lambda^{2}\bar{V}_{n}(h)$. Or, more compactly, $\phi=\lambda\bar{M}_{n}-(e-2)\lambda^{2}\bar{V}_{n}$. Then with probability greater than $1-\frac{\delta}{2}$ for all $\rho$:

where (27) is by Lemma 11 and other steps are justified in the same way as in the previous proof.

By applying the same argument to $-\bar{M}_{n}$, taking a union bound over the two results, taking $(e-2)\lambda^{2}\langle\bar{V}_{n},\rho\rangle$ to the other side of the inequality, and normalizing by $\lambda$, we obtain the statement of the theorem. ∎

The value of $\lambda$ that minimizes (9) depends on $\rho$, whereas we would like to have a result that holds for all possible distributions $\rho$ simultaneously. This requires considering multiple values of $\lambda$ simultaneously and we have to take a union bound over $\lambda$-s in step (26) of the proof of Theorem 7. We cannot take all possible values of $\lambda$, since there are uncountably many possibilities. Instead we determine the relevant range of $\lambda$ and take a union bound over a grid of $\lambda$-s that forms a geometric sequence over this range. Since the range is finite, the grid is also finite.

We cover the above range with a grid of $\lambda_{i}$-s, such that $\lambda_{i}:=c^{i}\frac{1}{K}\sqrt{\frac{\ln\frac{2}{\delta}}{(e-2)n}}$ for $i=0,\dots,m-1$. It is easy to see that in order to cover the interval of relevant $\lambda$ we need

($\lambda_{m-1}$ is the last value that is strictly less than $1/K$ and we take $\lambda_{m}:=1/K$ for the case when the technical condition (10) is not satisfied). This defines the value of $\nu$ in (12).

Finally, we note that (9) has the form $g(\lambda)=\frac{U}{\lambda}+\lambda V$. For the relevant range of $\lambda$, there is $\lambda_{i^{*}}$ that satisfies $\sqrt{U/V}\leq\lambda_{i^{*}}<c\sqrt{U/V}$. For this value of $\lambda$ we have $g(\lambda_{i^{*}})\leq(1+c)\sqrt{UV}$.

Therefore, whenever (10) is satisfied we pick the highest value of $\lambda_{i}$ that does not exceed the left hand side of (10), substitute it into (9), and obtain (11), where the $\ln\nu$ factor comes from the union bound over $\lambda_{i}$-s. If (10) is not satisfied, we know that $\langle\bar{V}_{n},\rho\rangle<K^{2}\left(KL(\rho\|\pi)+\ln\frac{2\nu}{\delta}\right)/(e-2)$ and by taking $\lambda=1/K$ and substituting into (9) we obtain (13). ∎

hence, we are interested in $\lambda$ that is larger or equal to this value. We take a grid of $\lambda_{i}$-s of the form

where $\lfloor x\rfloor$ is the largest integer value that is smaller than $x$. Taking a weighted union bound over $\lambda_{i}$-s with weights $2^{-(i+1)}$ completes the proof. (In the weighted union bound we take $\delta_{i}=\delta 2^{-(i+1)}$. Then by substitution of $\delta$ with $\delta_{i}$, (7) holds with probability greater than $1-\delta_{i}$ for each $\lambda_{i}$ individually, and with probability greater than $1-\sum_{i=0}^{\infty}\delta_{i}=1-\delta$ for all $\lambda_{i}$ simultaneously.) ∎

Appendix C Background

In this section we provide a proof of Lemma 11. The proof reproduces an intermediate step in the proof of [21, Theorem 1].

We apply inequality (30) in the following way:

Inequality (32) applies inequality (30) and inequality (34) recursively proceeds with $Z_{n-1},\dots,Z_{1}$ (in reverse order). ∎

Note that conditioning on additional variables in the proof of the lemma does not change the result. This fact is exploited in the proof of Theorem 7, when we allow interdependence between multiple martingales.

Acknowledgments

The authors would like to thank Andreas Maurer for his comments on Lemma 1. We are also very grateful to the anonymous reviewers for their valuable comments that helped to improve the presentation of our work. This work was supported in part by the IST Programme of the European Community, under the PASCAL2 Network of Excellence, IST-2007-216886, and by the European Community’s Seventh Framework Programme (FP7/2007-2013), under grant agreement $N^{o}$270327. This publication only reflects the authors’ views.

References