Concentration of polynomial random matrices via Efron-Stein inequalities

Goutham Rajendran University of Chicago


Analyzing concentration of polynomial random matrices is a common task in a wide variety of fields, for example in the analysis of spectral algorithms (e.g. Hopkins et al. [STOC 16], Moitra and Wein [STOC ‘19]) and in the analysis of semidefinite programs (e.g. Barak et al. [FOCS 16], Jones et al. [FOCS 21]). For analyzing matrix concentration, a commonly used tool is the trace power method. While it obtains strong bounds, it usually requires delicate combinatorial arguments. In this work, we present an alternate framework based on the beautiful matrix Efron-Stein inequalities by Paulin, Mackey and Tropp. This is based on joint work with Madhur Tulsiani from TTIC.

Apr 13, 2022 12:30 PM — 1:30 PM
Theory Lunch
JCL 390