## IMA Data Science Seminar: Quantile-based Iterative Methods for Corrupted Systems of Linear Equations

**Tuesday, April 13, 2021, 1:25 p.m.** through **Tuesday, April 13, 2021, 2:25 p.m.**

Online

Data science seminars hosted by the The Institute for Mathematics and Its Applications (IMA) take place on Tuesdays from 1:25 p.m. - 2:25 p.m.

This week, Elizaveta Rebrova (University of California, Los Angeles), will be giving a lecture titled "Quantile-based Iterative Methods for Corrupted Systems of Linear Equations".

Registration is required to access the Zoom webinar.

## 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, light and scalable iterative methods can be used instead, such as, Randomized Kaczmarz (RK) algorithm, or Stochastic Gradient Descent (SGD). The classical extensions of RK/SGD to noisy (inconsistent) systems work by showing that the iterations of the method still approach the least squares solution of the system until a certain convergence horizon (that depends on the noise size). However, in order to handle large, sparse, potentially adversarial corruptions, one needs to modify the algorithms to avoid corruptions rather than try to tolerate them -- and quantiles of the residual provide a natural way to do so. In this talk, I present QuantileRK and QuantileSGD, the versions of two classical iterative algorithms aimed at linear systems with adversarially corrupted vector b. 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). Our theoretical analysis shows that 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. Based on the joint work with Jamie Haddock, Deanna Needell, and Will Swartworth.

## Biography

Liza Rebrova is currently a postdoctoral scholar at the Computational Research Division of the Lawrence Berkeley National Lab. From 2018 to the end of 2020, she worked as an Assistant Adjunct Professor at the UCLA Department of Mathematics (Computational and Applied Math Group, mentored by Professors Deanna Needell and Terence Tao). She received a Ph.D. in Mathematics from the University of Michigan in 2018 (advised by Prof. Roman Vershynin) and a Specialist degree from Moscow State University in 2012. Her research involves interactions with high-dimensional probability, random matrix theory, mathematical data science, and numerical linear algebra, with the main goal to study large high-dimensional data objects in the presence of randomness and to develop randomized algorithms that efficiently process complex data. She is a recipient of the Allen Shields Memorial Fellowship (UofMichigan, 2018) and postdoctoral sponsorship by Capital Fund Management (UCLA, 2018-2020).

## IMA Data Science Seminar

**Tuesday, April 20, 2021, 1:25 p.m.** through **Tuesday, April 20, 2021, 2:25 p.m.**

Online

Data science seminars hosted by the The Institute for Mathematics and Its Applications (IMA) take place on Tuesdays from 1:25 p.m. - 2:25 p.m.

This week, Lars Ruthotto (Emory University), will be giving the lecture.

## Data Science Poster Fair

**Friday, April 23, 2021, 11:30 a.m.** through **Friday, April 23, 2021, 1 p.m.**

Online

We invite you to attend the annual Data Science Poster Fair! This year's event will be held virtually via Zoom on Friday, April 23 from 11:30 a.m. - 1:00 p.m.

Every year, data science M.S. students present their capstone projects during this event. This year, research preview videos will be posted to this page a week in advance, so attendees can view and plan their participation during the virtual event.

The poster fair is open to the public and all interested undergraduate and graduate students, alumni, staff, faculty, and industry professionals are encouraged to attend.

Stay tuned for more details! Any questions may be directed to Allison Small at csgradmn@umn.edu.

## IMA Data Science Seminar

**Tuesday, April 27, 2021, 1:25 p.m.** through **Tuesday, April 27, 2021, 2:25 p.m.**

Online

Data science seminars hosted by the The Institute for Mathematics and Its Applications (IMA) take place on Tuesdays from 1:25 p.m. - 2:25 p.m.

This week, Diego Cifuentes (Massachusetts Institute of Technology), will be giving the lecture.

## Last day of instruction

**Monday, May 3, 2021, Midnight** through **Monday, May 3, 2021, 11:59 p.m.**

Online

The last day of instruction for the fall 2020 semester is Monday, May 3.

View the full academic schedule on One Stop.

## Final exams begin

**Thursday, May 6, 2021, Midnight** through **Thursday, May 6, 2021, 11:59 p.m.**

University of Minnesota

Final exams for spring 2021 will be held between Thursday, May 6 and Wednesday, May 12.

View the full academic schedule on One Stop.

## End of spring semester

**Wednesday, May 12, 2021, Midnight** through **Wednesday, May 12, 2021, 11:59 p.m.**

University of Minnesota

The last day of the spring 2021 semester is Wednesday, May 12.

View the full academic schedule on One Stop.

## Graduate Programs Information Session

**Thursday, May 20, 2021, 9:30 a.m.** through **Thursday, May 20, 2021, 10:30 a.m.**

Online - link provided after registration

Prospective students can RSVP for an information session to learn about the following graduate programs:

- Computer Science M.S.
- Computer Science MCS
- Computer Science Ph.D.
- Data Science M.S.
- Data Science Post-Baccalaureate Certificate

During the information session, we will go over the following:

- Requirements (general)
- Applying
- Prerequisite requirements
- What makes a strong applicant
- Funding
- Resources
- Common questions
- Questions from attendees

## University closed

**Monday, May 31, 2021, Midnight** through **Monday, May 31, 2021, 11:59 p.m.**

University of Minnesota

The University of Minnesota will be closed in observance of Memorial Day.

## Graduate Programs Information Session

**Tuesday, July 27, 2021, 9:30 a.m.** through **Tuesday, July 27, 2021, 10:30 a.m.**

Online - link provided after registration

Prospective students can RSVP for an information session to learn about the following graduate programs:

- Computer Science M.S.
- Computer Science MCS
- Computer Science Ph.D.
- Data Science M.S.
- Data Science Post-Baccalaureate Certificate

During the information session, we will go over the following:

- Requirements (general)
- Applying
- Prerequisite requirements
- What makes a strong applicant
- Funding
- Resources
- Common questions
- Questions from attendees

The University of Minnesota and the greater Twin Cities area hosts many activities related to data science in a wide variety of specializations. Visit the following sites for more information on these activities.