[Colloquium] REMINDER: 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>*


On Fri, Dec 17, 2021 at 12:49 PM Mary Marre <mmarre at ttic.edu> wrote:

> *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/colloquium/attachments/20211220/aec1ab38/attachment.html>