B0742
Title: Spectral universality in regularized linear regression with nearly deterministic design matrices
Authors: Rishabh Dudeja - Harvard University (United States) [presenting]
Subhabrata Sen - Harvard University (United States)
Yue M Lu - Harvard University (United States)
Abstract: Statistical properties of many high-dimensional estimation tasks empirically exhibit universality with respect to the underlying design matrices. Specifically, matrices with very different constructions seem to behave identically if they share the same spectrum and have ``generic'' singular vectors. We prove this universality phenomenon for the performance of convex regularized least squares (RLS) estimators for linear regression. The contributions are two-fold: (1) We introduce a notion of universality classes for design matrices, defined through deterministic conditions that fix the spectrum of the matrix and formalize the heuristic notion of generic singular vectors; (2) We show that for all matrices in the same universality class, the dynamics of the proximal gradient algorithm for the regression problem, and the performance of RLS estimators themselves (under additional strong convexity conditions) are asymptotically identical. In addition to including i.i.d. Gaussian and rotational invariant matrices as special cases, our universality class also contains highly structured, strongly correlated, and even nearly deterministic matrices. Examples include randomly signed incoherent tight frames, and randomly subsampled Hadamard transforms. Due to this universality result, the performance of RLS estimators on many structured matrices with limited randomness can be characterized using the rotationally invariant ensemble as an equivalent yet mathematically tractable surrogate.
