*********************************
There is now a CONTENT FREEZE for Mercury while we switch to a new platform. It began on Friday, March 10 at 6pm and will end on Wednesday, March 15 at noon. No new content can be created during this time, but all material in the system as of the beginning of the freeze will be migrated to the new platform, including users and groups. Functionally the new site is identical to the old one. webteam@gatech.edu
*********************************
Algorithms & Randomness Center (ARC)
Yin Tat Lee
Friday, March 16, 2018
MiRC Pettit Rm 102A&B – 11:00 am
Title: l_p regression beyond self-concordance
Abstract: We consider the problem of linear regression where the l_2 norm loss (i.e., the usual least squares loss) is replaced by the l_p norm. We show how to solve such problems up to machine precision in O*(n^|1/2−1/p|) (dense) matrix-vector products and O*(1) matrix inversions, or alternatively in O*(n^|1/2−1/p|) calls to a (sparse) linear system solver. This improves the state of the art for any p not in {1,2,inf}. Furthermore we also propose a randomized algorithm solving such problems in input sparsity time, i.e., O*(Z+poly(d)) where Z is the size of the input and d is the number of variables. Such a result was only known for p=2. Finally we prove that these results lie outside the scope of the Nesterov-Nemirovski's theory of interior point methods by showing that any symmetric self-concordant barrier on the l_p unit ball has self-concordance parameter Ω~(n).
Joint work with Sébastien Bubeck, Michael B. Cohen, Yin Tat Lee, Yuanzhi Li
----------------------------------
Videos of recent talks are available at: https://smartech.gatech.edu/handle/1853/46836
Click here to subscribe to the seminar email list: arc-colloq@cc.gatech.edu
