ML p(r)ior | Concentration of measure without independence: a unified approach via the martingale method

### 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.

Highlights - Most important sentences from the article

# 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

Highlights - Most important sentences from the article

2012-02-14
1202.3775 | cs.LG

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

Highlights - Most important sentences from the article

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

Highlights - Most important sentences from the article

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

Highlights - Most important sentences from the article

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

Highlights - Most important sentences from the article

2019-05-21
1905.08707 | math.PR

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

Highlights - Most important sentences from the article

2019-04-18
1904.08576 | cs.LG

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

Highlights - Most important sentences from the article

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

Highlights - Most important sentences from the article

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

Highlights - Most important sentences from the article

2018-07-02
1807.00451 | stat.ML

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

Highlights - Most important sentences from the article

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

Highlights - Most important sentences from the article

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

Highlights - Most important sentences from the article

2018-10-17
1810.07793 | cs.LG

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

Highlights - Most important sentences from the article

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

Highlights - Most important sentences from the article

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

Highlights - Most important sentences from the article

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

Highlights - Most important sentences from the article

2015-09-10
1509.03258 | math.PR

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

Highlights - Most important sentences from the article