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
]]>