Concentration of polynomial random matrices via Efron-Stein inequalities

Analyzing concentration of large random matrices is a common task in a wide variety of fields. Given independent random variables, several tools are available to bound the norms of random matrices whose entries are linear in the variables, such as the matrix-Bernstein inequality. However, for many recent applications, we need to bound the norms of random matrices whose entries are polynomials in the variables. Such matrices arise naturally in the analysis of spectral algorithms (e.g., Hopkins et al. [STOC 2016], Moitra and Wein [STOC 2019]), and in lower bounds for semidefinite programs based on the Sum-of-Squares (SoS) hierarchy (e.g. Barak et al. [FOCS 2016], Jones et al. [FOCS 2021]).

In this work, we present a general framework to obtain such bounds, based on the beautiful matrix Efron-Stein inequalities developed by Paulin, Mackey and Tropp [Annals of Probability 2016]. The Efron-Stein inequality bounds the norm of a random matrix by the norm of another potentially simpler (but still random) matrix. We view the latter matrix as arising by "differentiating" the starting matrix. By recursively differentiating, our framework reduces the main task to bounding the norms of far simpler matrices. These simpler matrices are in fact deterministic matrices in the case of Rademacher random variables and hence, bounding their norm is a far easier task. In general for non-Rademacher random variables, the task reduces to the much easier task of scalar concentration. Moreover, in the setting of polynomial matrices, our main result also generalizes the work of Paulin, Mackey and Tropp.

As applications of our basic framework, we recover known bounds in the literature, especially for simple "tensor networks" and "dense graph matrices". As applications of our general framework, we derive bounds for "sparse graph matrices". The sparse graph matrix bounds were obtained only recently by Jones et al. [FOCS 2021] using a nontrivial application of the trace power method, and was a core component in their work. We expect this framework will also be helpful for other applications involving concentration phenomena for nonlinear random matrices.