Colloquium - Michał Dereziński - October 3, 2024

Speaker: Michał Dereziński, University of Michigan
Title: Solving Large Linear Systems Without Constructing a Preconditioner
Date/Time: Thursday, October 3, 2024, 10:20 AM - 11:10 AM ET

Abstract:
Solving systems of linear equations has numerous applications across many areas, from data science and machine learning, to scientific computing, engineering and more. When these systems are too large to solve directly, iterative refinement methods such as conjugate gradient have proven to be a powerful alternative. The computational cost of these methods can be significantly affected by a problem-dependent condition number, which is often addressed by combining the iterative solver with a preconditioner, i.e., an easy to invert approximation of the original system. However, constructing a good preconditioner can still be very expensive, which leads to an undesirable trade-off between the cost of preconditioning and the cost of solving the linear system.
In this talk, I will present new stochastic iterative methods for solving linear systems based on the so-called Sketch-and-Project paradigm, which can reduce the condition number of the system without having to precondition it. This approach is based on the following phenomenon: Whenever the spectral structure of a linear system is amenable to constructing a strong preconditioner via low-rank matrix approximation, we can design a Sketch-and-Project solver that will implicitly take advantage of this to find the solution faster. In particular, I will show how this leads to solving an n x n linear system with at most k large (outlying) singular values in ~O( n^2 + nk^2 ) arithmetic operations, which is faster than the ~O( n^2 k ) cost of constructing a good preconditioner for this system.

Bio:
Michał Dereziński is an Assistant Professor of Computer Science and Engineering at the University of Michigan. Previously, he was a postdoctoral fellow in the Department of Statistics at the University of California, Berkeley, and a research fellow at the Simons Institute for the Theory of Computing. Michał obtained his Ph.D. in Computer Science at the University of California, Santa Cruz, where he received the Best Dissertation Award for his work on sampling methods in statistical learning. Michał's current research is focused on theoretical foundations of randomized algorithms for machine learning, optimization, and applied mathematics. In particular, his work in the area of Randomized Numerical Linear Algebra was funded by an NSF CAREER Award, and received the Best Paper Award at the 34th Conference on Neural Information Processing Systems (NeurIPS).
https://web.eecs.umich.edu/~derezin/