User-Friendly Tail Bounds for Sums of Random Matrices

By Joel A. Tropp. 2010

1,921 citations recorded by the source corpus.

This paper presents new probability inequalities for sums of independent, random, self-adjoint matrices. These results place simple and easily verifiable hypotheses on the summands, and they deliver strong conclusions about the large-deviation behavior of the maximum eigenvalue of the sum. Tail bounds for the norm of a sum of random rectangular matrices follow as an immediate corollary. The proof techniques also yield some information about matrix-valued martingales.In other words, this paper provides noncommutative generalizations of the classical bounds associated with the names Azuma, Bennett, Bernstein, Chernoff, Hoeffding, and McDiarmid. The matrix inequalities promise the same diversity of application, ease of use, and strength of conclusion that have made the scalar inequalities so valuable.

Subfields: Applied Mathematics, Statistics and Probability, Statistical Learning Theory

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 Statistics and Probability

In Statistical Learning Theory

Citations in the corpus

Communication-Efficient Distributed Optimization using an Approximate Newton-type Method (2013, background): “By a matrix Hoeffding’s inequality (Tropp, 2012), we have that for each i , with probability 1 − δ over the samples received by machine i , By a union bound, we get that with probability 1 − δ ,”
Additive models with trend filtering (2017, methodology): “Part (c) is an application of a matrix Chernoff bound from Tropp [2012]. In order to apply this result, we must obtain an almost sure upper bound R on λmax(V (V ) ), with V i as in (61) and λmax(·) denoting the maximum eigenvalue of its argument.”
Sharp analysis of low-rank kernel matrix approximations (2012, positive): “By construction, we have E ∆ = 0 , and, as shown by Tropp (2011, 2012) and Gittens (2011), we have E tr exp( s ∆) 6 E tr exp( s Ξ) , where Ξ is obtained by sampling independently p rows with replacement, i.e., is equal to where z j ∈ R n is a random element of the canonical basis of R n such that P…”
DeltaGrad: Rapid retraining of machine learning models (2020, methodology): “CLASSICAL RESULTS FOR RANDOM VARIABLES To analyze DeltaGrad with SGD, Bernsteins inequality (Oliveira, 2009; Tropp, 2012; 2016) is necessary.”
Agnostic Estimation of Mean and Covariance (2016, methodology): “mates computed from samples are close to their expectations. We will use the following two results. Firstly, as an immediate corollary of matrix Bernstien for rectangular matrices (see Theorem 1.6 in [Tro12]), we get the following concentration result for the sample mean and sample covariance. Lemma”
A PAC-Bayesian Approach to Spectrally-Normalized Margin Bounds for Neural Networks (2017, neutral): “…a ﬁxed ˜ β and the w for which | β − ˜ β ≤ 1 d β , and hence Since u ∼ N (0 , σ 2 I ) , we get the following bound for the spectral norm of U i [13]: Taking a union bond over the layers, we get that, with probability ≥ , the spectral norm of the perturbation U i in each layer is bounded by σ 2…”
Introduction to the non-asymptotic analysis of random matrices (2010, neutral): “29 (Non-commutative Bernstein-type inequality [77]).”
Generalization in Deep Learning (2017, background): “(Matrix Bernstein inequality: corollary to theorem 1.4 in Tropp 2012) Consider a finite sequence { M i } of independent, random, self-adjoint matrices with dimension d .”
Excess risk bounds for multitask learning with trace norm regularization (2012, methodology): “We will use the following important result of Tropp (Lemma 3.4 in [27]), derived from Lieb’s concavity theorem (see [10], Section IX.6): Theorem 5 Consider a ﬁnite sequence A k of independent, random, self-adjoint operators and a ﬁnite dimensional subspace A corollary suited to our applications is…”
Aggregating crowdsourced binary ratings (2013, background): “The underlying intuition behind this concentration result from [17] is that a random matrix is close to its expectation in terms of the spectral norm, if it can be expressed as the output of a function having bounded sensitivity over its input variables.”
Explaining Landscape Connectivity of Low-cost Solutions for Multilayer Nets (2019, neutral): “Lemma 7 (Matrix Bernstein; Theorem 1.6 in (Tropp, 2012)) .”
Tighter Low-rank Approximation via Sampling the Leveraged Element (2014, neutral): “[29] J.”
Implicit Regularization in Deep Learning (2017, positive): “The following inequality holds on the spectral norm of Ui [57]: PUi∼N(0,σq) [‖Ui‖2 > t] ≤ 2he−t (2)/2hσ(2) q .”
Subsampled inexact Newton methods for minimizing large sums of convex functions (2018, methodology): “Assumption C2 For every x ∈ R n and every i ∈ N there holds E ( ∇ This assumption allows us to use the Matrix Chernoff result (see [39]) and to obtain the bound presented in Lemma 1 of [36].”
Fast Randomized Kernel Ridge Regression with Statistical Guarantees (2015, background): “The proof relies on a matrix Bernstein inequality (see e.g. [16]) and is presented at the end of the paper (Appendix B).”
Provable Inductive Matrix Completion (2013, methodology): “To this end, we use Theorem 8 by [14] given below.”