← List all talks ...

The Well Tempered Lasso

Yoram Singer – Professor, Princeton University

Thu, 28-Jan-2021 / 4:30pm / Zoom: https://stanford.zoom.us/meeting/register/tJckfuCurzkvEtKKOBvDCrPv3McapgP6HygJ

Talk

• Video

Abstract

We study the complexity of the entire regularization path for least squares regression with 1-norm penalty, known as the Lasso. Every regression parameter in the Lasso changes linearly as a function of the regularization value. The number of changes is regarded as the Lasso’s complexity. Experimental results using exact path following exhibit polynomial complexity of the Lasso in the problem size. Alas, the path complexity of the Lasso on artificially designed regression problems is exponential. We use smoothed analysis as a mechanism for bridging the gap between worst case settings and the de facto low complexity. Our analysis assumes that the observed data has a tiny amount of intrinsic noise. We then prove that the Lasso’s complexity is polynomial in the problem size. While building upon the seminal work of Spielman and Teng on smoothed complexity, our analysis is morally different as it is divorced from specific path following algorithms. We verify the validity of our analysis in experiments with both worst case settings and real datasets. The empirical results we obtain closely match our analysis.

Joint work with Prof. Yuanzhi Li (CMU).

Bio

Yoram Singer is a professor of Computer Science at Princeton University. He obtained his BSc and MSc from the Technion and PhD from the Hebrew University. He was a member of the technical staff at AT&T Research 1995-1999, an associate professor of Computer Science at the Hebrew University 1999-2007, and a Principal Scientist at Google 2005-2019. At Google he implemented and launched Google’s Domain Spam classifier used for all search queries 2004-2017, co-founded the Sibyl system which which served YouTube multiple prediction tasks 2008-2018, and founded the Principles Of Effective Machine-learning group as well as Google’s AI Lab at Princeton. He co-chaired COLT’04 and NIPS’04. He is a fellow of AAAI. His work on error correcting output code for machine learning received the Test of Time Award. With his former PhD students he received several best paper awards. Prior to pursuing a PhD he served at unit 8200 of IDF and retired from service at the rank of a captain. He was a member of a 12 people team from the unit which received Israel Security Award given by the President of Israel.