Instructor: Yizhe Zhu, yizhezhu@usc.edu
Class schedule: MWF 1:00-1:50 pm at GFS 112
Office Hours: Friday 12:00-12:50 pm KAP 464B
Course Description: This course provides an introduction to the fundamental methods, concepts, and tools of random matrix theory, with an emphasis on its modern applications in machine learning. We will explore both the asymptotic and non-asymptotic perspectives of random matrices and discuss how these theoretical foundations inform applications in network analysis, signal processing, and deep learning theory.
Homework: Homework will be posted on Brightspace
Course Schedule: Below is a tentative schedule, to be updated as the semester progresses.
Week 1
Jan 12: Wigner matrices, semicircle law, moment method proof
Jan 14: moment method proof continued
Jan 16: Marchenko-Pastur law
Week 2
Jan 19: No class
Jan 21: Marchenko-Pastur law, spectral norm bound via high moment method
Jan 23: high moment method, Stieltjes transform
Week 3
Jan 26: Stieltjes transform
Jan 28: Marchenko-Pastur law via Stieltjes transform
Jan 30: Semicircle law via Stieltjes transform, local law
Week 4
February 2: Eigenvector delocalization
February 4: Stochastic block model
February 6: Matrix Bernstein's inequality
Week 5
February 9: Davis-Kahan inequality
February 11: Weak and partial recovery
February 13: Exact recovery
Week 6
February 16: No class
February 18: Leave-one-out analysis
February 20: spectral method for exact recovery
Week 7
February 23: Kesten-Stigum detection threshold
February 25: non-backtracking operator, Ihara-Bass formula
February 27: Spectral clustering with the non-backtracking operator
Week 8
March 2: Spiked matrix models, GOE
March 4: BBP phase transition: eigenvalue
March 6: Eigenvector overlap
Week 9
March 9: Spiked sample covariance model
March 11: Tensor PCA, information-theoretical threshold
March 13: Tensor PCA, algorithmic threshold with tensor unfolding
Week 10
March 16: No class
March 18: No class
March 20: No class
Week 11
March 23: the Kikuchi spectral method for Tensor PCA
March 25: Two-layer neural networks, conjugate kernel, random feature regression
March 27: Concentration of conjugate kernel
Week 12
March 30: Concentration by matrix Bernstein's inequality with truncation
April 1: The limiting spectrum of the conjugate kernel for multiple layers
April 3: Overparametrization and minimum norm interpolator
Week 13
April 6: Benign overfitting: effective rank
April 8: benign overfitting: bias and variance decomposition, covariance estimation with stable rank
April 10: benign overfitting: head and tail decomposition
Week 14
April 13: Double descent
April 15: Double descent in random feature models
April 17: Neural tangent kernel
Week 15
April 20: Neural tangent kernel, high-dimensional learning dynamics on least squares
April 22: Scaling limit for isotropic least squares
April 24: Scaling limit for anisotropic least squares
Week 16
April 27: Final presentation
April 29: Final presentation
May 1: Final presentation
A list of papers for the final project.
Concentration inequalities
Afonso Bandeira, Kevin Lucca, Petar Nizić-Nikolac, Ramon van Handel. Matrix Chaos Inequalities and Chaos of Combinatorial Type
March T. Boedihardjo. Injective norm of random tensors with independent entries
Danil Akhtiamov, David Bosch, Reza Ghane, K Nithin Varma, Babak Hassibi. A novel Gaussian min-max theorem and its applications (Benjamin Sionit)
Aicke Hinrichs, David Krieg, Erich Novak, Joscha Prochno, Mario Ullrich. Random sections of ellipsoids and the power of random information
Afonso S. Bandeira, Giorgio Cipolloni, Dominik Schröder, Ramon van Handel. Matrix Concentration Inequalities and Free Probability II. Two-sided Bounds and Applications
Tatiana Brailovskaya, Ramon van Handel. Extremal random matrices with independent entries and matrix superconcentration inequalities
Spectral clustering and community detection
Anderson Ye Zhang. Fundamental Limits of Spectral Clustering in Stochastic Block Models
Alexandra Carpentier, Christophe Giraud, Nicolas Verzelen. Phase Transition for Stochastic Block Model with more than √n Communities
Phuc Tran, Van Vu. New perturbation bounds for low rank approximation of matrices via contour analysis
Spiked model
Alice Guionnet, Justin Ko, Florent Krzakala, Pierre Mergny, Lenka Zdeborová. Spectral Phase Transitions in Non-Linear Wigner Spiked Models
Michael J. Feldman. Spectral Properties of Elementwise-Transformed Spiked Matrices
Zhangsong Li. The Algorithmic Phase Transition in Correlated Spiked Models
Pravesh K. Kothari, Jeff Xu. Smooth Trade-off for Tensor PCA via Sharp Bounds for Kikuchi Matrices
Jingqiu Ding, Samuel B.Hopkins, David Steurer. Estimating Rank-One Spikes from Heavy-Tailed Noise via Self-Avoiding Walks
Nonlinear random matrix model
Lucas Benigni, Elliot Paquette. Eigenvalue distribution of the Neural Tangent Kernel in the quadratic scaling
Chiraag Kaushik, Justin Romberg, Vidya Muthukumar. A general technique for approximating high-dimensional empirical kernel matrices
Zhichao Wang, Denny Wu, Zhou Fan. Nonlinear spiked covariance matrices and signal propagation in deep neural networks
Deep learning theory
Nikhil Ghosh, Mikhail Belkin. A Universal Trade-off Between the Model Size, Test Loss, and Training Loss of Linear Predictors (Sophie Uluatam)
Licong Lin, Jingfeng Wu, Sham Kakade, Peter Bartlett, Jason Lee. Scaling Laws in Linear Regression: Compute, Parameters, and Data
Jimmy Ba, Murat A Erdogdu, Taiji Suzuki, Zhichao Wang, Denny Wu. Learning in the presence of low-dimensional structure: a spiked random matrix perspective (Peng Wang)
Yatin Dandi, Florent Krzakala, Bruno Loureiro, Luca Pesce, Ludovic Stephan, How two-layer neural networks learn, one (giant) step at a time (Sampad Mohanty)
Binxu Wang, Jacob Zavatone-Veth, Cengiz Pehlevan. A Random Matrix Theory Perspective on the Consistency of Diffusion Models
Jimmy Ba, Murat A Erdogdu, Taiji Suzuki, Zhichao Wang, Denny Wu, Greg Yang. High-dimensional Asymptotics of Feature Learning: How One Gradient Step Improves the Representation (Jacob Fein-Ashley)
Yue M. Lu, Mary I. Letey, Jacob A. Zavatone-Veth, Anindita Maiti, Cengiz Pehlevan. Asymptotic theory of in-context learning by linear attention
High-dimensional statistics
Zhidong Bai, Wang Zhou. Large sample covariance matrices without independence structures in columns (Pengtao Li)
Parham Rezaei, Filip Kovacevic, Francesco Locatello, Marco Mondelli. High-dimensional Analysis of Synthetic Data Selection (Frank Gao)
Alden Green, Elad Romanov. The High-Dimensional Asymptotics of Principal Component Regression (Letian Yang)
Youngjoo Yun, Rishabh Dudeja. High-Dimensional Asymptotics of Differentially Private PCA (Rundong Ding)