# Concentration of polynomial random matrices via Efron-Stein inequalities

arXiv: https://arxiv.org/abs/2209.02655 · HTML: https://mlsanity.com/paper/2209.02655/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 14 of its 54 references that are in the map.
- First posted on arXiv 6 Sep 2022.

## Builds on (most cited first, 14 of 14)

- [An Introduction to Matrix Concentration Inequalities](https://mlsanity.com/paper/1501.01571/) (2015)
- [Fast spectral algorithms from sum-of-squares proofs: tensor decomposition and planted sparse vectors](https://mlsanity.com/paper/1512.02337/) (2015)
- [Tensor principal component analysis via sum-of-squares proofs](https://mlsanity.com/paper/1507.03269/) (2015)
- [Fast and robust tensor decomposition with applications to dictionary learning](https://mlsanity.com/paper/1706.08672/) (2017)
- [Sum-of-squares lower bounds for planted clique](https://mlsanity.com/paper/1503.06447/) (2015)
- [Decomposing Overcomplete 3rd Order Tensors using Sum-of-Squares Algorithms](https://mlsanity.com/paper/1504.05287/) (2015)
- [Improved Sum-of-Squares Lower Bounds for Hidden Clique and Hidden Submatrix Problems](https://mlsanity.com/paper/1502.06590/) (2015)
- [Lifting Sum-of-Squares Lower Bounds: Degree-2 to Degree-4](https://mlsanity.com/paper/1911.01411/) (2019)
- [A Robust Spectral Algorithm for Overcomplete Tensor Decomposition](https://mlsanity.com/paper/2203.02790/) (2022)
- [Spectral Methods from Tensor Networks](https://mlsanity.com/paper/1811.00944/) (2018)
- [Exact nuclear norm, completion and decomposition for random overcomplete tensors via degree-4 SOS](https://mlsanity.com/paper/2011.09416/) (2020)
- [Polynomial-Time Power-Sum Decomposition of Polynomials](https://mlsanity.com/paper/2208.00122/) (2022)
- [Tight Lower Bounds for Planted Clique in the Degree-4 SOS Program](https://mlsanity.com/paper/1507.05136/) (2015)
- [Combinatorial Optimization via the Sum of Squares Hierarchy](https://mlsanity.com/paper/2208.04374/) (2022)

## Abstract (arXiv)

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.