Concentration Inequalities and Martingale Inequalities: A Survey

By Fan Chung Graham, Lincoln Lu. Internet Mathematics, 2006

529 citations recorded by the source corpus.

Subfields: Geometry and Topology, Mathematical Physics, Statistics and Probability

View Paper: https://www.semanticscholar.org/paper/70e5445e9b57b14b1796686f546f073d196bb166

How researchers see this paper

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

In Geometry and Topology

In Mathematical Physics

In Statistics and Probability

Citations in the corpus

Exponential inequalities for martingales and asymptotic properties of the free energy of directed polymers in a random environment (2008, unknown): “: the classical works of Bernstein [3,4], Cramér [16], Hoeffding [24], Azuma [1] and Chernoff [9]; the well-known books of Chow and Teicher [10] and Petrov [32]; and the recent papers by de la Peña, [17], Lesigne and Volný [28], Bentkus [2] and Chung and Lu [11].”
Time-uniform Chernoff bounds via nonnegative supermartingales (2018, methodology): “…condition for a process (St) to be 1-sub-ψ with variance process (Vt) is that Et−1 exp {λΔSt − ψ(λ)ΔVt} ≤ 1, ∀t, (4.1) which is the standard assumption for a martingale-method Cramér-Chernoff inequality, typically with (Vt) predictable (McDiarmid, 1998; Chung and Lu, 2006; Boucheron et al., 2013).”
Random Graphs and Complex Networks (2016, unknown): “24, see [80].”
Martingale posterior distributions (2021, background): “This predictive invariance is particularly natural as a minimal predictive coherence condition, and serves as an analogue to de Finetti’s exchangeability assumption in the predictive framework. In fact, as shown in Kallenberg (1988), the c.”
Sample Complexity of Episodic Fixed-Horizon Reinforcement Learning (2015, methodology): “Further, since ν + i ∈ [0 , H ] and Equation (6), we have we can apply Theorem 22 by Chung and Lu [21] and obtain We can further simplify the bound to We are now ready to prove Lemma 2 by combining the bound in the previous lemma for all κ and ι .”
Influence Maximization in Near-Linear Time: A Martingale Approach (2015, methodology): “The following lemma from [10] shows two concentration results for martingales that have similar ﬂavor to the Chernoff bounds.”