- Madeleine Udell, Stanford University
- ZOOM TALK (Passcode: the smallest prime > 100 ): Low rank approximation for faster optimization
- 01/19/2023
- 2:30 PM - 3:30 PM
- C304 Wells Hall
(Virtual Meeting Link)
- Mark A Iwen ()
Low rank structure is pervasive in real-world datasets. This talk shows how to accelerate the solution of fundamental computational problems, including eigenvalue decomposition, linear system solves, composite convex optimization, and stochastic optimization (including deep learning), by exploiting this low rank structure. We present a simple method based on randomized numerical linear algebra for efficiently computing approximate top eigendecompositions, which can be used to replace large matrices (such as Hessians and constraint matrices) with low rank surrogates that are faster to apply and invert. The resulting solvers for linear systems (NystromPCG), composite convex optimization (NysADMM), and deep learning (SketchySGD) demonstrate strong theoretical and numerical support, outperforming state-of-the-art methods in terms of speed and robustness to hyperparameters.
