skip to main content

H.B. Keller Colloquium

Monday, April 15, 2024
3:00pm to 4:00pm
Add to Cal
Gates-Thomas 135
Low rank approximation for faster optimization
Madeleine Udell, Assistant Professor of Management Science and Engineering, Stanford University,

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 eigen decompositions, 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 stochastic optimization (SketchySGD and PROMISE) demonstrate strong theoretical and numerical support, outperforming state-of-the-art methods in terms of speed and robustness to hyperparameters.

For more information, please contact Sumaia Abedin by phone at 6263956704 or by email at [email protected] or visit