Matrix concentration inequalities via the method of exchangeable pairs

By Lester W. Mackey, Michael I. Jordan, Richard Y. Chen, Brendan Farrell, Joel A. Tropp. 2012

177 citations recorded by the source corpus.

This paper derives exponential concentration inequalities and polynomial moment inequalities for the spectral norm of a random matrix. The analysis requires a matrix extension of the scalar concentration theory developed by Sourav Chatterjee using Stein’s method of exchangeable pairs. When applied to a sum of independent random matrices, this approach yields matrix generalizations of the classical inequalities due to Hoeffding, Bernstein, Khintchine and Rosenthal. The same technique delivers bounds for sums of dependent random matrices and more general matrix-valued functions of dependent random variables.

Subfields: Applied Mathematics, Mathematical Physics, Statistics and Probability

View Paper: https://www.semanticscholar.org/paper/0b37625a90a891b7692fb0e8ffb8131739d7d8d3

How researchers see this paper

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

In Applied Mathematics

In Mathematical Physics

In Statistics and Probability

Citations in the corpus

A short survey of Stein's method (2014, methodology): “In 2012, Mackey and coauthors [56] extended the method to the domain of matrix concentration inequalities, thereby solving some problems in theoretical machine learning.”
Better Agnostic Clustering Via Relaxed Tensor Norms (2017, background): “We must instead appeal to the Matrix Rosenthal inequality (Corollary 7.4 of [MJC + 14]).”
Local Privacy and Minimax Bounds: Sharp Rates for Probability Estimation (2013, methodology): “Along the way, we use matrix Bernstein inequalities [23] and some approximation-theoretic ideas developed by K¨uhn [22].”
Structured Random Matrices (2016, methodology): “For simplicity, we will restrict our attention to matrices w ith Gaussian entries, though extensions to other distributions are easily obtain ed (for example, see [14]).”
Per-instance Differential Privacy (2017, unknown): “Let E be the event that | (θ)| > t. Pp(θ ∈ S) = Pp(θ ∈ S ∪ Ec) + Pp(θ ∈ S ∪ E) ≤ Pp′(θ ∈ S ∪ E)et + Pp(θ ∈ E) ≤ etPp′(θ ∈ S) + δ. Lemma 26 (Matrix Hoeffding inequality (Mackey et al., 2014)).”
Communication-Efficient Distributed Optimization of Self-Concordant Empirical Loss (2015, unknown): “,m} and for any vector w in an ℓ 2-ball. Thus, if the number of samples n is large, the Hessian matrix of f can be approximated well by that of fi. The proof uses random matrix concentration theories [30]. We defer the proof to Appendix E. Lemma 6. Suppose Assumption B holds. For any r > 0 and an”
Randomized Nonlinear Component Analysis (2014, methodology): “Second, McWilliams et al. (2013) used the Nyström method to define a randomized feature map and performed CCA to achieve state-of-the-art semi-supervised learning.”