Sushant Sachdeva (Toronto) - Iterative Refinement for p-norms

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