  Analyzing concentration of large random matrices is a common task in a wide
variety of fields. Given independent random variables, many tools are available
to analyze random matrices whose entries are linear in the variables, e.g. the
matrix-Bernstein inequality. However, in many applications, we need to analyze
random matrices whose entries are polynomials in the variables. These arise
naturally in the analysis of spectral algorithms, e.g., Hopkins et al. [STOC
2016], Moitra-Wein [STOC 2019]; and in lower bounds for semidefinite programs
based on the Sum of Squares 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 matrix Efron-Stein inequalities developed by
Paulin-Mackey-Tropp [Annals of Probability 2016]. The Efron-Stein inequality
bounds the norm of a random matrix by the norm of another simpler (but still
random) matrix, which we view as arising by "differentiating" the starting
matrix. By recursively differentiating, our framework reduces the main task to
analyzing far simpler matrices. For Rademacher variables, these simpler
matrices are in fact deterministic and hence, analyzing them is far easier. For
general non-Rademacher variables, the task reduces to scalar concentration,
which is much easier. Moreover, in the setting of polynomial matrices, our
results generalize the work of Paulin-Mackey-Tropp. Using our basic framework,
we recover known bounds in the literature for simple "tensor networks" and
"dense graph matrices". Using our general framework, we derive bounds for
"sparse graph matrices", which 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 our framework to be helpful for other
applications involving concentration phenomena for nonlinear random matrices.
