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

DOI10.1007/978-1-4939-7005-6_6zbMATH Open1387.60037arXiv1602.00721OpenAlexW2253472364MaRDI QIDQ2406342FDOQ2406342

Authors: Maxim Raginsky, Aryeh Kontorovich 

Publication date: 27 September 2017

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.

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

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

zbMATH Keywords

martingale methodtransportation inequalitiesAzuma-Hoeffding concentration inequalityWasserstein matrices

Mathematics Subject Classification ID

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

Cited In (9)

• Concentration inequalities for empirical processes of linear time series
• Random geometric graph: some recent developments and perspectives
• Concentration inequalities for dependent random variables via the martingale method
• Phase transitions for detecting latent geometry in random graphs
• On concentration inequalities and their applications for Gibbs measures in lattice systems
• When Janson meets McDiarmid: Bounded difference inequalities under graph-dependence
• Measure concentration for Euclidean distance in the case of dependent random variables.
• Quantum concentration inequalities
• 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)