[Theory] NOW: 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 Tue, Dec 21, 2021 at 10:00 AM 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>*
>
>
> On Mon, Dec 20, 2021 at 4:21 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>*
>>
>>
>> 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/theory/attachments/20211221/d429c590/attachment-0001.html>