Seminar - Michał Derezinski

Event Date: 

Wednesday, December 9, 2020 - 3:30pm to 4:30pm

Title: Determinantal Point Processes in Randomized Numerical Linear Algebra

Abstract:

Randomized Numerical Linear Algebra (RandNLA) is an area which uses randomness to develop improved algorithms for ubiquitous matrix problems. A seemingly different topic, but one which has a long history in pure and applied mathematics, is that of Determinantal Point Processes (DPPs). DPPs form a class of stochastic point processes, characterized by sub-determinants of a kernel matrix, which provide a tractable probabilistic model of negative dependence. Recent work has uncovered deep connections between DPPs and RandNLA which lead to new guarantees and improved algorithms that are of interest to both areas. My talk will provide an overview of this exciting new line of research, starting with a brief introduction to DPPs. The covered topics will include our recent work on constructing new kinds of unbiased estimators for least squares regression as well as applications to low-rank approximation and distributed Newton's method. I will also highlight the connections between DPPs and popular i.i.d. sampling methods in RandNLA, such as leverage scores, which helped us develop new efficient algorithms for sampling from a DPP. This talk is based on a survey paper with the same title (https://arxiv.org/abs/2005.03185).
 
Bio:
 
Michał Dereziński is a postdoctoral researcher in the Department of Statistics at UC Berkeley. Previously, he was a research fellow at the Simons Institute for the Theory of Computing. He obtained his Ph.D. in Computer Science at UC Santa Cruz, advised by professor Manfred Warmuth. Michał's research is focused on developing scalable randomized algorithms with robust statistical guarantees for machine learning, data science and optimization.
Michał Dereziński