Login
Talks & Seminars
Title: Faster Algorithms for p-norm Regression
Prof. Sushant Sachdeva, University of Toronto
Date & Time: September 6, 2019 14:00
Venue: Department of Computer Science and Engineering, Room No. 109, 01st Floor, New CSE/CC Building
Abstract:
Linear regression in L_p-norm is a canonical optimization problem that arises in several applications, including sparse recovery, semi-supervised learning, and signal processing. Standard linear regression corresponds to p=2, and p=1 or infinity is equivalent to linear programming. In this talk, we will discuss new algorithms for obtaining high-accuracy (1+1/poly(n))-approximate solutions to such problems. Our algorithms are based on an 'iterative refinement' approach for p-norms, where an algorithm for computing an approximate solution can be converted into a high-accuracy algorithm. Previously, iterative refinement was known only for L_2-regression (or equivalently, solving linear systems). Based on this approach, we give several new high-accuracy algorithms, including 1) an algorithm for p-norm regression by solving only m^{1/3} linear systems, 2) a provably convergent and fast iterative reweighted least squares (IRLS) algorithm for p-norm regression, and 3) an algorithm for p-norm flows 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.
Speaker Profile:
Sushant Sachdeva is a faculty member at the CS dept. at the University of Toronto. He is interested in Algorithms, and its connections to optimization, machine learning, and statistics. His recent research focus has been the design of fast algorithms for graph problems. Before joining UofT, he was a research scientist at Google. He completed his postdoc at Yale with Dan Spielman (2016), his PhD from Princeton (2013) under Sanjeev Arora, and his BTech from IIT Bombay (2008). He is the recipient of Google Faculty Research Award (2017), Simons Berkeley Research Fellowship (2013), and the IITB President of India Gold Medal (2008).
List of Talks

Webmail

Username:
Password:
Faculty CSE IT
Forgot Password
    [+] Sitemap     Feedback