ARC Colloquium: Yin Tat Lee (UW)

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


Speaker's Webpage

Videos of recent talks are available at:

Click here to subscribe to the seminar email list:

Event Details


  • Friday, March 16, 2018
    11:00 am - 12:00 pm