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

**2016-02-01**

1602.00721 | math.PR

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.

**Login to like/save this paper, take notes and configure your recommendations**

# Related Articles

**2016-08-16**

1608.04481 | cs.DS

These are lecture notes that are based on the lectures from a class I taught
on the topic of Randomi… show more

**2012-02-14**

1202.3775 | cs.LG

Conditional independence testing is an important problem, especially in
Bayesian network learning an… show more

**2019-01-06**

1901.01624 | math.OC

The blind deconvolution problem seeks to recover a pair of vectors from a set
of rank one bilinear m… show more

**2017-01-23**

1701.06347 | cs.IT

The aim of this work is to establish that two recently published projection
theorems, one dealing wi… show more

**2018-02-17**

1802.06292 | stat.ML

Let $A:[0,1]\rightarrow\mathbb{H}_m$ (the space of Hermitian matrices) be a
matrix valued function w… show more

**2019-05-21**

1905.08707 | math.PR

We develop a systematic information-theoretic framework for quantification
and mitigation of error i… show more

**2019-04-18**

1904.08576 | cs.LG

A growing number of modern statistical learning problems involve estimating a
large number of parame… show more

**2018-12-05**

1812.02108 | stat.ML

In this paper we study some concentration properties of the kernel matrix
associated with a kernel f… show more

**2018-01-10**

1801.03365 | cs.DM

We discuss five ways of proving Chernoff's bound and show how they lead to
different extensions of t… show more

**2018-07-02**

Real-world data such as digital images, MRI scans and electroencephalography
signals are naturally r… show more

**2018-07-13**

1807.05152 | math-ph

While Shannon entropy is related to the growth rate of multinomial
coefficients, we show that the qu… show more

**2019-04-11**

1904.05510 | cs.LG

Matrices satisfying the Restricted Isometry Property (RIP) play an important
role in the areas of co… show more

**2018-10-17**

1810.07793 | cs.LG

We introduce the Wasserstein transform, a method for enhancing and denoising
datasets defined on gen… show more

**2018-09-04**

1809.00781 | cs.IT

In this paper, we study tail inequalities of the largest eigenvalue of a
matrix infinitely divisible… show more

**2017-02-20**

1702.05985 | math.ST

We extend Fano's inequality, which controls the average probability of events
in terms of the averag… show more

**2018-09-27**

1809.10272 | math.PR

Total correlation (`TC') and dual total correlation (`DTC') are two classical
way to quantify the co… show more

**2015-09-10**

1509.03258 | math.PR

We consider high dimensional Wishart matrices $\mathbb{X} \mathbb{X}^{\top}$
where the entries of $\… show more