PAC-Bayesian Inequalities for Martingales

ARTINGALES 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 [1], [2], [3]. We present a comparison inequality that bounds the expectation of a convex function of a martingale difference sequence shifted to the [0, 1] 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 Figure 1 for an illustration).