AMS Seminar w/ Liza Rebrova (University of California, Los Angeles) on Zoom

Title: Quantile-based Iterative Methods for Corrupted Systems of Linear Equations
Abstract: One of the most ubiquitous problems arising across the sciences is that of solving large-scale systems of linear equations Ax = b. When it is infeasible to solve the system directly by inversion, scalable and efficient projection-based iterative methods can be used instead, such as, Randomized Kaczmarz (RK) algorithm, or SGD (optimizing ||Ax – b|| in some norm).
The main goal of my talk is to present versions of these two algorithms aimed at linear systems with adversarially corrupted vector b, QuantileRK and QuantileSGD. While the classical approach for noisy (inconsistent) systems is to show that the iterations approach the least squares solution until a certain convergence horizon that depends on the noise size, in order to handle large, sparse, potentially adversarial corruptions, one needs to modify the algorithm to avoid corruptions rather than try to tolerate them — and quantiles of the residual provide a natural way to do so. Our methods work on up to 50% of incoherent corruptions, and up to 20% of adversarial corruptions (that consistently create an “alternative” solution of the system). Theoretically, under some standard assumptions on the measurement model, despite corruptions of any size both methods converge to the true solution with exactly the same rate as RK on an uncorrupted system up to an absolute constant. Our theoretical analysis is based on probabilistic concentration of measure results, and as an auxiliary random matrix theory result, we prove a non-trivial uniform bound for the smallest singular values of all submatrices of a given matrix. Based on the joint work with Jamie Haddock, Deanna Needell, and Will Swartworth.

The cloud recording is now available.
Topic: AMS Department Seminar (Spring 2021)
Date: Feb 11, 2021 12:49 PM Eastern Time (US and Canada)
Share recording with viewers:
https://wse.zoom.us/rec/share/Dn4mMX4n4CMPKWUQfXql6Trt4yurYBxPe37OkFowp0Fcxp3MfNEsnczBxr68roig.90xVqiC1mKI-98wl Passcode: Jx*#6Lko
Enjoy.