#### Theory Seminar

# Deeksha Adil: Fast Algorithms for l_p-Regression and Other Problems

Deeksha AdilUniversity of Toronto

WHERE:

3725 Beyster BuildingMap

WHEN:

Friday, March 11, 2022 @ 3:00 pm - 4:00 pm

This event is free and open to the publicAdd to Google Calendar

This event is free and open to the publicAdd to Google Calendar

WEB: Event Website

SHARE:

Regression in $\ell_p$-norms is a canonical problem in optimization, machine learning, and theoretical computer science. In this talk, I will describe our recent advances in developing fast, high-accuracy algorithms both in theory and practice. Our algorithms are based on a few novel techniques which I will go over briefly and are the fastest available both in theory and practice. Our algorithms for $\ell_p$-regression also imply fast algorithms for the p-norm flow problem and an $m^{1+o(1)}\epsilon^{-1}$ time algorithm for the maximum flow problem on unit capacity graphs, matching the best-known bounds for this problem.

I will further show how our techniques extend to obtain fast algorithms for a broader class, quasi-self-concordant functions which capture several important loss functions such as soft-max and logistic regression. As a result, we obtain the first unified

*width reduced multiplicative weights algorithm.*Our rates match the ones obtained by explicit acceleration schemes for these problems thus suggesting a deeper connection between our techniques and standard acceleration schemes. I would finally end with some open directions.