[Colloquium] Todays Theory Speaker

[Donna Brooms via Colloquium]

The University of Chicago

Department of Computer Science & Mathematics

Combinatorics & Theory Seminar

 

  PRESENTS:

 

 

                                                            
 

                                                               Sushant Sachdeva

                                                   University of Toronto

                                         http://www.cs.toronto.edu/~sachdeva/

 

Title: “Iterative Refinement for p-norms”

 

Abstract: In the current optimization literature, for several convex programs, it is significantly faster to obtain O(1)-approximate solutions as compared to high accuracy (1+1/poly(n))-approximate solutions. This gap is reflected in the differences between interior point methods vs. (accelerated) gradient descent for regression problems, and between exact vs. approximate undirected max-flow. One exception has been L2-regression, where an algorithm for computing an approximate solution can be converted into a high-accuracy solution via iterative refinement. In this talk, we will present generalizations of iterative refinement to p-norms. This leads to algorithms that produce high accuracy solutions by crudely solving only a polylogarithmic number of residual problems. I will also discuss several results that build on this new approach to high-accuracy algorithms, including p-norm regression using m^{1/3} linear system solves, and p-norm flow in undirected unweighted graphs in almost-linear time.

 

This talk will be based on joint works with Deeksha Adil, Richard Peng, Rasmus Kyng, and Di Wang.

 

Host: Prof. Madhur Tulsiani

     

Tuesday, February 12, 2019

                                               Ry. 251 @ 3:30 pm

(Refreshments will be served prior to the talk in Ry. 255 @ 3:15pm)

 

 

Donna Brooms-Blue




Department Secretary
Computer Science Department
John Crerar Library Building
5730 So. Ellis Ave.
Chicago, IL. 60637
(773) 702-6614 - Office
(773) 702-8487 - Fax
donna at cs.uchicago.edu

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20190212/13f5e5c3/attachment-0001.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: clip_image001.jpg
Type: image/jpeg
Size: 35984 bytes
Desc: not available
URL: <http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20190212/13f5e5c3/attachment-0001.jpg>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: image001.gif
Type: image/gif
Size: 2340 bytes
Desc: not available
URL: <http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20190212/13f5e5c3/attachment-0001.gif>