Concentration Inequalities for Dependent Random Variables via the Martingale Method

By L. Kontorovich, Kavita Ramanan. 2006

213 citations recorded by the source corpus.

The martingale method is used to establish concentration inequalities for a class of dependent random sequences on a countable state space, with the constants in the inequalities expressed in terms of certain mixing coecien ts. Along the way, bounds are obtained on mar- tingale dierences associated with the random sequences, which may be of independent interest. As applications of the main result, concentra- tion inequalities are also derived for inhomogeneous Markov chains and hidden Markov chains, and an extremal property associated with their martingale dierence bounds is established. This work complements and generalizes certain concentration inequalities obtained by Marton and Samson, while also providing a dieren t proof of some known results.

Subfields: Management Science and Operations Research, Mathematical Physics, Statistics and Probability

View Paper: https://www.semanticscholar.org/paper/32b7a9f1c04acb4e777c4b4c6194825d11c0276b

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Management Science and Operations Research

In Mathematical Physics

In Statistics and Probability

Citations in the corpus

A tail inequality for suprema of unbounded empirical processes with applications to Markov chains (2007, methodology): “metric ergodicity of the chain. Concentration of measure inequalities for general functions of Markov chains were investigated by Marton [13], Samson [23] and more recently by Kontorovich and Ramanan [8]. They actually consider more general mixing processes and give estimates on the deviation of a r”
Reinforcement Learning of POMDPs using Spectral Methods (2016, methodology): “The problem of planning in general POMDPs is intractable (PSPACE-complete for finite horizon (Papadimitriou and Tsitsiklis, 1987) and uncomputable for infinite horizon (Madani, 1998)).Many exact, approximate, and heuristic methods have been proposed to compute the optimal policy (see Spaan (2012) fo”
Hoeffding's inequality for sums of weakly dependent random variables (2015, background): “k at the works of Azuma [3], Bentkus[6],Delyon[7],Fanetal. [10],Gavinskyetal. [11],Gradwohletal. [14],Hazla et al. [15], Impagliazzo et al. [19], Janson [20], Kallabis et al. [23], Kontorovich et al. [25], Linial et al. [26], McDiarmid [27], Ramon et al. [31], Rio [32], Schmidt et al. [33], Siegel [”
PAC-Bayesian Collective Stability (2014, methodology): “Our analysis uses concentration inequalities for Lipschitz functions of dependent random variables, similar to those presented by Chazottes et al. (2007) and Kontorovich and Ramanan (2008).”
Bernstein's inequalities for general Markov chains (2018, unknown): “…research includes Marton’s work on the concentration of measure phenomenon for contracting Markov chains (Marton, 1996a,b, 1998, 2003, 2004) and further progresses under various dependence structures (Samson, 2000; Chazottes et al., 2007; Kontorovich and Ramanan, 2008; Redig and Chazottes, 2009).”
Collective Stability in Structured Prediction: Generalization from One Example (2013, background): “Leveraging recent results in the concentration of dependent random variables (Chazottes et al., 2007; Kontorovich & Ramanan, 2008), we show that, if the data exhibits weak dependence within each structure, and the hypothesis class has suitable collective stability, then the empirical error estimate…”
Stability and Generalization in Structured Prediction (2016, methodology): “Proposition 1 builds on work by Samson (2000), Chazottes et al. (2007) and Kontorovich and Ramanan (2008).”
Concentration inequalities for Markov chains by Marton couplings and spectral methods (2012, methodology): “to show McDiarmid-type inequalities for dependent random variables were developed in [4] (using an elementary martingale-type argument) and [23] (using martingales and linear algebraic inequalities).”