Source-linked AI summary
PAC-Bayesian Inequalities for Martingales
Yevgeny Seldin, François Laviolette, Nicolò Cesa-Bianchi, John Shawe-Taylor, Peter Auer
TL;DR
PAC-Bayesian concentration analysis has traditionally addressed weighted averages of independent random variables, while martingale settings include interdependent processes and can involve uncountably many martingales. This paper extends the analysis to martingales, derives a Bernoulli comparison inequality, and reports bounds comparable to or tighter than existing inequalities in specified cases.
Problem
PAC-Bayesian analysis provides high-probability bounds for weighted averages of independent random variables, while the paper addresses concentration for multiple, possibly uncountably many, interdependent martingales.
Source: §I · p. 1Method
The paper combines Donsker-Varadhan’s variational formula with martingale moment-generating-function bounds and compares convex functions of bounded martingale differences with independent Bernoulli variables.
Source: §IV · p. 5Results
The martingale kl bound is comparable to Hoeffding-Azuma’s up to a logarithmic factor, can be tighter near random-walk drift boundaries, and can be tighter than Bernstein’s absent a tight variance bound.
Source: §IV · p. 5Takeaways & Limitations
The weighted-average inequalities are especially useful for uncountably many martingales and have an application to importance-weighted sampling in reinforcement learning.
Source: §IV · p. 5
Abstract
from arXiv · showhide
We present a set of high-probability inequalities that control the concentration of weighted averages of multiple (possibly uncountably many) simultaneously evolving and interdependent martingales. Our results extend the PAC-Bayesian analysis in learning theory from the i.i.d. setting to martingales opening the way for its application to importance weighted sampling, reinforcement learning, and other interactive learning domains, as well as many other domains in probability theory and statistics, where martingales are encountered. We also 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. This inequality is applied to derive a tighter analog of Hoeffding-Azuma's inequality.
I. INTRODUCTION
The introduction extends PAC-Bayesian analysis from independent samples to martingales, presenting high-probability bounds for weighted averages of multiple interdependent martingales. It also introduces a Bernoulli comparison inequality and describes importance-weighted sampling as an application.
I. INTRODUCTION
- A comparison inequality bounds expectations of convex functions of [0,1]-shifted martingale differences by expectations for independent Bernoulli variables, and is used to derive a tighter Hoeffding-Azuma analog.Source: §I · p. 1
- The inequalities control weighted averages of simultaneously evolving, interdependent martingales, including uncountably many, with high probability for a large class of averaging laws ρ that may depend on the sample.This is useful where a standard union bound over individual martingales cannot be applied.Source: §I · p. 1
- Importance-weighted sampling can produce martingale differences between observed statistics and their expectations; sample-dependent ρ permits adapting the controlled distribution to preceding outcomes.The text gives denser sampling in data-dependent regions as an example and points to a reinforcement-learning application.Source: §I · p. 1
- Donsker-Varadhan’s variational formula relates weighted averages under possible distributions ρ to a reference distribution π, yielding a high-probability statement for all ρ simultaneously via Markov’s inequality.The bound on the cumulant-generating function is obtained using moment-generating-function bounds, including those for martingales.Source: §I · pp. 1–2
- The paper extends PAC-Bayesian analysis to martingales, making it possible to apply it in domains such as reinforcement learning.Earlier PAC-Bayesian analysis provided high-probability deviation bounds for weighted averages of empirical means of independent random variables.Source: §I · p. 2
II. MAIN RESULTS
The section presents results for individual martingales before results for their weighted averages, with proofs in the appendix.
II. MAIN RESULTS
- The section first presents inequalities for individual martingales.Source: §II · p. 2
- It then presents inequalities for weighted averages of martingales.Source: §II · p. 2
- The proofs are provided in the appendix.Source: §II · p. 2
A. Inequalities for Individual Martingales
The section compares bounded martingale differences with independent Bernoulli variables, then uses that comparison to derive a Hoeffding-Azuma analog. The resulting bound is comparable to Hoeffding-Azuma’s and can be tighter in specified cases.
A. Inequalities for Individual Martingales
- The comparison inequality bounds expectations of convex functions of [0,1]-valued martingale differences by expectations for independent Bernoulli variables with matching conditional means, generalizing Maurer’s result for independent variables.Source: A. Inequalities for Individual… · p. 2
- The comparison result generalizes an analogous i.i.d. result using the method of types in information theory.Source: A. Inequalities for Individual… · p. 2
- The paper applies the comparison inequality to derive an analog of Hoeffding-Azuma’s inequality for martingales.The derivation combines Lemma 2 with Markov’s inequality.Source: A. Inequalities for Individual… · p. 2
- The kl bound is at least as tight as Hoeffding-Azuma’s up to a factor of n/(n+1), and its Pinsker-based deviation form is similar to Hoeffding-Azuma’s.The less explicit kl bound can be tighter in certain situations.Source: A. Inequalities for Individual… · p. 3
- In certain situations, the less explicit bound in kl form is significantly tighter than Hoeffding-Azuma’s inequality and can also be tighter than Bernstein’s inequality; a detailed comparison appears in Section III.Source: A. Inequalities for Individual… · p. 3
B. PAC-Bayesian Inequalities for Weighted Averages of Martingales
The section extends PAC-Bayesian inequalities to weighted averages of martingales, giving high-probability bounds that hold simultaneously across averaging distributions. It presents bounds based on Hoeffding-Azuma and Bernstein inequalities, with tuning procedures for distribution-dependent bounds.
B. PAC-Bayesian Inequalities for Weighted Averages of Martingales
- The classical PAC-Bayesian theorem for independent random variables holds in the same form for martingales.The result combines the Donsker-Varadhan variational formula with a martingale moment-generating-function bound.Source: B. PAC-Bayesian Inequalities for… · p. 3
- With probability greater than 1−δ, the theorem bounds hold for all distributions ρ over H simultaneously.The passage introduces random functions in [0,1] whose conditional expectations equal a deterministic function.Source: B. PAC-Bayesian Inequalities for… · p. 3
- A geometric grid of λ values approximates the value that minimizes the bound for each ρ, since one λ cannot minimize it for all ρ.The result is described as almost as good as minimizing the bound for a single ρ.Source: B. PAC-Bayesian Inequalities for… · p. 3
- The Bernstein-based result requires ∥Z̄_i∥∞ ≤ K and λ ≤ 1/K, and combines a martingale Bernstein inequality with the variational formula.The result is stated for simultaneous bounds over distributions ρ.Source: B. PAC-Bayesian Inequalities for… · p. 3
- For the variance-based bound, a geometric λ grid gives an almost single-ρ-optimal result and permits replacing the variance with a sample-dependent upper bound.For importance-weighted sampling, the text gives an upper bound derived from the reciprocal of the sampling distribution at each round.Source: B. PAC-Bayesian Inequalities for… · p. 3
III. COMPARISON OF THE INEQUALITIES
This section compares the paper’s inequalities with bounds for individual martingales and with one another.
III. COMPARISON OF THE INEQUALITIES
- The section compares inequalities for weighted averages of martingales with inequalities for individual martingales.It also recalls Hoeffding-Azuma and Bernstein inequalities for individual martingales and compares them with the new kl-form inequality.Source: §III · p. 4
A. Background
The background section recalls Hoeffding-Azuma and Bernstein inequalities for individual martingales and introduces a corollary based on a grid of λ values.
A. Background
- The section recalls Hoeffding-Azuma’s inequality for martingale difference sequences with bounded increments.It also recalls a Bernstein-type inequality for bounded martingale differences,.Source: A. Background · p. 4
- The grid-based corollary is tighter than an analogous result by Beygelzimer et al. [21, Theorem 1].The grid lets the bound use a λ value close to the optimum, and its upper bound on V_n may be sample-dependent.Source: A. Background · p. 4
B. Comparison
The comparison section begins by comparing inequalities for individual martingales.
B. Comparison
- The section first compares individual-martingale inequalities in Corollaries 3, 10, and 12.Source: B. Comparison · p. 4
Comparison of Inequalities for Individual Martingales:
For individual martingales, the kl inequality is at least as tight as Hoeffding-Azuma’s up to a factor, and can be tighter near the boundaries of a random walk’s drift. Its comparison with Bernstein depends on the variance bound.
Comparison of Inequalities for Individual Martingales:
- Corollary 12 matches Corollary 10 up to minor constants and logarithmic factors generally, and can be much tighter when variance is small.Corollary 12 is derived from Bernstein’s inequality; Corollary 10 is derived from Hoeffding-Azuma’s inequality.Source: Comparison of Inequalities for… · p. 4
- Corollary 3 is at least as tight as Hoeffding-Azuma’s inequality, up to a factor of √(2 ln((n+1)/δ)).Here Sn − bn is the martingale corresponding to differences Zi = Xi − b.Source: Comparison of Inequalities for… · p. 4
- The stated projection-based extension to Xi ∈ [αi, βi] requires simultaneously projecting all Xi to [0, 1] without losing too much.Source: Comparison of Inequalities for… · p. 4
- When 1/nSn < 1/8, the kl inequality is tighter than Hoeffding-Azuma; tighter bounds also apply when Sn is close to n.The kl inequality can be inverted numerically without approximation.Source: Comparison of Inequalities for… · p. 5
- When the variance bound is significantly tighter than n, Bernstein can be significantly tighter than the kl inequality; otherwise, the kl inequality can be tighter.For random-walk drift near zero or n, the kl inequality is tighter and comparable to empirical Bernstein bounds.Source: Comparison of Inequalities for… · p. 5
- The weighted-average PAC-Bayesian bounds incur KL(ρ∥π), which vanishes when ρ = π; the Hoeffding-Azuma version also has a minor grid-of-λ term.Source: Comparison of Inequalities for… · p. 5
IV. DISCUSSION
The discussion presents a comparison inequality for martingale differences and uses it to derive a Hoeffding-Azuma analog. It also highlights concentration bounds for weighted averages of multiple interdependent martingales, including uncountable families.
IV. DISCUSSION
- The comparison inequality bounds convex-function expectations for martingale-difference-type variables by those for independent Bernoulli variables, reducing the study of bounded dependent variables to a simpler independent-variable problem.Source: §IV · p. 5
- The Hoeffding-Azuma analog is comparable up to a logarithmic factor and can be tighter by an order of magnitude when random-walk drift is near region boundaries.It can also be tighter than Bernstein’s inequality unless there is a tight bound on martingale variance.Source: §IV · p. 5
- The inequalities control weighted averages of multiple simultaneously evolving and interdependent martingales, including uncountable families for which standard union bounds cannot be applied.Source: §IV · p. 5
- The bounds have a stated application in importance-weighted sampling in reinforcement learning.Source: §IV · p. 5
APPENDIX A PROOFS OF THE RESULTS FOR INDIVIDUAL MARTINGALES
The appendix proves the comparison and concentration results for individual martingales by reducing bounded-variable arguments to Bernoulli variables and applying convexity and Markov’s inequality.
APPENDIX A PROOFS OF THE RESULTS FOR INDIVIDUAL MARTINGALES
- The comparison-lemma proof writes points in [0, 1]^n as convex combinations of the extreme points in {0, 1}^n.Source: Appendix A · p. 5
- The proof replaces Xi by Bernoulli variables bi one at a time, in reverse order, using induction.Source: Appendix A · pp. 5–6
- Lemma 2 uses a concentration result for i.i.d. Bernoulli variables based on the method of types; convexity of KL divergence and the exponent function then transfers the bound.Source: Appendix A · p. 6
- The factorial approximation uses a slightly weaker bound, and results based on Lemma 2 could be slightly improved with the tighter bound.Source: Appendix A · p. 6
- The proof applies Markov’s inequality to obtain a high-probability statement, then takes logarithms and normalizes by n.Source: Appendix A · p. 6
APPENDIX B PROOFS OF PAC-BAYESIAN THEOREMS FOR
The appendix derives PAC-Bayesian bounds by combining a change-of-measure relation with moment-generating-function bounds and Markov’s inequality. Its proofs also address simultaneous choices of λ and interdependent martingales.
APPENDIX B PROOFS OF PAC-BAYESIAN THEOREMS FOR
- The change-of-measure lemma relates averages under every ρ to the cumulant-generating function under a single reference distribution π; Markov’s inequality and moment-generating-function bounds then yield high-probability results.Source: Appendix B · p. 6
- Theorem 4’s proof uses the change-of-measure inequality at (22), Markov’s inequality at (23), and Lemma 2.2 at (25); Theorem 5’s similar proof is omitted, while Theorem 6’s grid-selection method is given.Source: Appendix B · p. 6
- Theorem 7’s proof uses φ = λM̄n − (e − 2)λ²V̄n and applies the moment-generating-function bound to obtain the PAC-Bayesian statement.Source: Appendix B · p. 6
- For Theorem 8, the proof covers a finite relevant range of λ with a geometric grid, since the minimizing λ depends on ρ and cannot be union-bounded over continuously.A weighted union bound is used for the unbounded λ range in Theorem 6.Source: Appendix B · p. 7
APPENDIX C BACKGROUND
- In the background proof, the exponential bound restricts λ to λ ≤ 1/K; conditioning on additional variables preserves the result, allowing interdependence between martingales.Source: Appendix C · p. 7