Date & Time:
February 12, 2019 3:30 pm – 4:30 pm
Ryerson 251, 1100 E. 58th St., Chicago, IL,
02/12/2019 03:30 PM 02/12/2019 04:30 PM America/Chicago Sushant Sachdeva (Toronto) – Iterative Refinement for p-norms Ryerson 251, 1100 E. 58th St., Chicago, IL,

Iterative Refinement for p-norms

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: Madhur Tulsiani

Sushant Sachdeva

Assistant Professor, University of Toronto

Research Interests

Algorithms, and its connections to optimization, machine learning, and statistics.

Focus areas: Design of fast algorithms, particularly for graph problems; Approximation algorithms; Numerical Linear Algebra; Hardness of approximation

Related News & Events

Students posing at competition
UChicago CS News

UChicago Undergrad Team Places Second Overall In Regionals For World’s Largest Programming Competition

Mar 17, 2023
Haifeng Xu
UChicago CS News

New CS and DSI Faculty Haifeng Xu Brings Strategic Intelligence to NeurIPS 2022

Nov 28, 2022
UChicago CS News

UChicago CS Research Finds New Angle on Database Query Processing with Geometry

Nov 08, 2022
UChicago CS News

Asst. Prof. Aloni Cohen Receives Award For Revealing Flaws in Deidentifying Data

Sep 09, 2022
UChicago CS News

UChicago Hosts NSF Workshop on Frontiers of Quantum Advantage

Aug 15, 2022
UChicago CS News

New 2022-23 Faculty Add Expertise in Linguistics, Visualization, Economics, and Data Science Education

Aug 11, 2022
In the News

UChicago Co-Leads $10 Million NSF Institute on Foundations of Data Science

Aug 09, 2022
In the News

Bill Fefferman Comments on New Standards for Quantum-Proof Cryptography

Jul 07, 2022
UChicago CS News

UChicago London Colloquium Features Data Science, Quantum Research

Jul 01, 2022
UChicago CS News

Faculty Bill Fefferman and Chenhao Tan Receive Google Research Scholar Awards

Jun 21, 2022
UChicago CS News

First-Year PhD Student Co-Authors Outstanding Paper Award Winner at TQC 2022

Apr 28, 2022
In the News

Quanta Magazine Features Prof. Bill Fefferman’s Work on Quantum Algorithms

Jan 20, 2022
arrow-down-largearrow-left-largearrow-right-large-greyarrow-right-large-yellowarrow-right-largearrow-right-smallbutton-arrowclosedocumentfacebookfacet-arrow-down-whitefacet-arrow-downPage 1CheckedCheckedicon-apple-t5backgroundLayer 1icon-google-t5icon-office365-t5icon-outlook-t5backgroundLayer 1icon-outlookcom-t5backgroundLayer 1icon-yahoo-t5backgroundLayer 1internal-yellowinternalintranetlinkedinlinkoutpauseplaypresentationsearch-bluesearchshareslider-arrow-nextslider-arrow-prevtwittervideoyoutube