[Theory] 12/21 Talks at TTIC: Deeksha Adil, University of Toronto

[Mary Marre]

*When:*      Tuesday, December 21st at* 10:30 am CT*



*Where:*     Zoom Virtual Talk (*register in advance here
<https://uchicagogroup.zoom.us/webinar/register/WN_C8n20ztvQ5eu_LPFBY1nuw>*)


*Who: *       Deeksha Adil, University of Toronto



*Title:*        Fast Algorithms for $\ell_p$-Regression and Other Problems

*Abstract:*
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

*Host*: *Nathan Srebro* <nati at ttic.edu>




Mary C. Marre
Faculty Administrative Support
*Toyota Technological Institute*
*6045 S. Kenwood Avenue*
*Chicago, IL  60637*
*mmarre at ttic.edu <mmarre at ttic.edu>*
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.uchicago.edu/pipermail/theory/attachments/20211217/4bf88972/attachment.html>