Skip to main content

The Well-Tempered Lasso

Author(s): Li, Yuanzhi; Singer, Yoram

Download
To refer to this page use: http://arks.princeton.edu/ark:/88435/pr1655r
Full metadata record
DC FieldValueLanguage
dc.contributor.authorLi, Yuanzhi-
dc.contributor.authorSinger, Yoram-
dc.date.accessioned2021-10-08T19:50:15Z-
dc.date.available2021-10-08T19:50:15Z-
dc.date.issued2018en_US
dc.identifier.citationLi, Yuanzhi, and Yoram Singer. "The Well-Tempered Lasso." In Proceedings of the 35th International Conference on Machine Learning 80 (2018): pp. 3024-3032.en_US
dc.identifier.issn2640-3498-
dc.identifier.urihttp://proceedings.mlr.press/v80/li18f/li18f.pdf-
dc.identifier.urihttp://arks.princeton.edu/ark:/88435/pr1655r-
dc.description.abstractWe 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.en_US
dc.format.extent3024 - 3032en_US
dc.language.isoen_USen_US
dc.relation.ispartofProceedings of the 35th International Conference on Machine Learningen_US
dc.rightsFinal published version. Article is made available in OAR by the publisher's permission or policy.en_US
dc.titleThe Well-Tempered Lassoen_US
dc.typeConference Articleen_US
pu.type.symplectichttp://www.symplectic.co.uk/publications/atom-terms/1.0/conference-proceedingen_US

Files in This Item:
File Description SizeFormat 
Lasso.pdf335.92 kBAdobe PDFView/Download


Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.