Least Squares Optimization with L1 Norm Regularization

Mark Schmidt

Description

Niveau: Supérieur, Doctorat, Bac+8
Least Squares Optimization with L1-Norm Regularization Mark Schmidt CS542B Project Report December 2005 Abstract This project surveys and examines optimization ap- proaches proposed for parameter estimation in Least Squares linear regression models with an L1 penalty on the regression coefficients. We first review linear regres- sion and regularization, and both motivate and formalize this problem. We then give a detailed analysis of 8 of the varied approaches that have been proposed for optimiz- ing this objective, 4 focusing on constrained formulations and 4 focusing on the unconstrained formulation. We then briefly survey closely related work on the orthogonal design case, approximate optimization, regularization parameter estimation, other loss functions, active application areas, and properties of L1 regularization. Illustrative implemen- tations of each of these 8 methods are included with this document as a web resource. 1 Introduction This report focuses on optimizing on the Least Squares objective function with an L1 penalty on the parameters. There is currently significant interest in this and related problems in a wide variety of fields, due to the appealing idea of creating accurate predictive models that also have interpretable or parsimonious representations. Rather than focus on applications or properties of this model, the main contribution of this project is an examination of a variety of the approaches that have been proposed for parameter esti- mation in this model. The bulk of this document focuses on surveying 8 differ- ent optimization strategies proposed in the literature for this problem.

• negative variable


• denois- ing works


• problem


• least squares


• variable


• l1 regularization


• while l2


• highly negative


• kkt con


• linear regression

Sujets

• Schmidt
• Problem
• Least squares
• Variable
• Linear regression

Informations

• Publié par: profil-zyak-2012
• Nombre de lectures: 64
• Langue: English

Extrait

LeastSquaresOptimizationwithL1-NormRegularization MarkSchmidt CS542BProjectReport December2005 Abstract Thisprojectsurveysandexaminesoptimizationap- proachesproposedforparameterestimationinLeast SquareslinearregressionmodelswithanL1penaltyon theregressioncoefcients.Werstreviewlinearregres- sionandregularization,andbothmotivateandformalize thisproblem.Wethengiveadetailedanalysisof8ofthe variedapproachesthathavebeenproposedforoptimiz- ingthisobjective,4focusingonconstrainedformulations and4focusingontheunconstrainedformulation.Wethen brieysurveycloselyrelatedworkontheorthogonaldesign case,approximateoptimization,regularizationparameter estimation,otherlossfunctions,activeapplicationareas, andpropertiesofL1regularization.Illustrativeimplemen- tationsofeachofthese8methodsareincludedwiththis documentasawebresource. 1Introduction ThisreportfocusesonoptimizingontheLeastSquares objectivefunctionwithanL1penaltyontheparameters. Thereiscurrentlysignicantinterestinthisandrelated problemsinawidevarietyofelds,duetotheappealing ideaofcreatingaccuratepredictivemodelsthatalsohave interpretableorparsimoniousrepresentations.Ratherthan focusonapplicationsorpropertiesofthismodel,themain contributionofthisprojectisanexaminationofavarietyof theapproachesthathavebeenproposedforparameteresti- mationinthismodel. Thebulkofthisdocumentfocusesonsurveying8differ- entoptimizationstrategiesproposedintheliteratureforthis problem.Eachwillbeexaminedindetail,focusingontheir comparativestrengthsandweaknesses,andhoweachdeals withafunctionthathasnon-differentiablepoints.Afterex- aminingthesemethodsindetail,wewillbrieydiscusssev- eralcloselyrelatedissues.Theseincludeoptimizationinthe specialcaseofanorthogonaldesignmatrix,approximate optimizationforlargeproblems,selectingappropriateval- uesfortheregularizationparameter,optimizingotherloss functionssubjecttoanL1penalty,severalactiveapplica- tionareas,andnallywediscussseveralinterestingproper- tiesofL1regularization. However,wewillrstbrieyreviewthelinearregression problem,theLeastSquaresapproach,L2andL1penalties, andnallyformalizetheproblembeingexamined.Wedo thisreviewinordertomotivatetheinterestinthismodel, andtointroducethenotationthatwillbeusedconsistently throughoutthereport.Weemphasizethelatterpointbe- causemuchoftherelatedworkwasproducedindifferent areas,andthenotationusedisnotconsistentacrossworks. 1.1LinearRegression Inthetypicalunivariatelinearregressionscenario,the inputis n instancesofaprocessdescribedby p+1 vari- ables,andweseektondalinearcombinationofaselected p variables(thefeatures)thatbestpredictstheremaining variable(thetarget).Wetypicallydenethedesignmatrix X asamatrixhaving n rowsand p columns,representing the p variablesfor n instances.Similarly,wedenethetar- getvector y asacolumnvectoroflength n containingthe correspondingvaluesofthetargetvariable.Theproblem canthenbeformulatedasndinga‘good’valueforthe length p coefcientvector w andthescalarbiasterm w 0 in thefollowingmodel(takenover i from 1 to n ): p X y i =w 0 +x ij w j +² i (1) 1=j ² i denotesthenoise(orerror)termforinstance i ,anditis typicallyassumedthatthevaluesof ² i havezeromean,and arebothindependentlyandidenticallydistributed.Thus, wetypicallydonotmodel ² directly.However,wecannot solvefor w and w 0 directlygivenonly X and y ,because ² isunknown.Inaddition,thenoisetermmaycausethesame orsimilarvaluesof x i toyielddifferentvalues.Wethus denea‘loss’functionthatassesseshowwellagivensetof parameters w predicts y from X .