Concentration of measure without independence: a unified approach via the martingale method

DOI10.1007/978-1-4939-7005-6_6MaRDI QIDQ2406342zbMATHOpenAlexFDO

Authors Maxim Raginsky, Aryeh Kontorovich

Publication date 27 September 2017

Full work available at URL https://arxiv.org/abs/1602.00721

zbMATH Keywords

martingale methodtransportation inequalitiesAzuma-Hoeffding concentration inequalityWasserstein matrices

Mathematics Subject Classification ID

Inequalities; stochastic orderings (60E15) Martingales with discrete parameter (60G42)

Abstract: The concentration of measure phenomenon may be summarized as follows: a function of many weakly dependent random variables that is not too sensitive to any of its individual arguments will tend to take values very close to its expectation. This phenomenon is most completely understood when the arguments are mutually independent random variables, and there exist several powerful complementary methods for proving concentration inequalities, such as the martingale method, the entropy method, and the method of transportation inequalities. The setting of dependent arguments is much less well understood. This chapter focuses on the martingale method for deriving concentration inequalities without independence assumptions. In particular, we use the machinery of so-called Wasserstein matrices to show that the Azuma-Hoeffding concentration inequality for martingales with almost surely bounded differences, when applied in a sufficiently abstract setting, is powerful enough to recover and sharpen several known concentration results for nonproduct measures. Wasserstein matrices provide a natural formalism for capturing the interplay between the metric and the probabilistic structures, which is fundamental to the concentration phenomenon.

Recommendations

• Concentration inequalities for dependent random variables via the martingale method
• Concentration Inequalities and Martingale Inequalities: A Survey
• Concentration inequalities. A nonasymptotic theory of independence
• Concentration inequalities. A nonasymptotic theory of independence
• The concentration inequalities of functions of independent random variables
• Concentration inequalities for sums and martingales
• Concentration inequalities for semi-bounded martingales
• Measure concentration for a class of random processes
• Unbounded order convergence and application to martingales without probability

Cited in

(9)

• Random geometric graph: some recent developments and perspectives
• Phase transitions for detecting latent geometry in random graphs
• Measure concentration for Euclidean distance in the case of dependent random variables.
• Quantum concentration inequalities
• On concentration inequalities and their applications for Gibbs measures in lattice systems
• When Janson meets McDiarmid: Bounded difference inequalities under graph-dependence
• Concentration inequalities for dependent random variables via the martingale method
• Concentration inequalities for empirical processes of linear time series
• Spectral telescope: convergence rate bounds for random-scan Gibbs samplers based on a hierarchical structure

This page was built for publication: Concentration of measure without independence: a unified approach via the martingale method

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2406342)