Show simple item record

dc.contributor.advisorSanghavi, Sujay Rajendra, 1979-
dc.creatorNetrapalli, Praneeth Kumaren
dc.date.accessioned2014-09-17T19:15:20Zen
dc.date.issued2014-08en
dc.date.submittedAugust 2014en
dc.identifier.urihttp://hdl.handle.net/2152/25931en
dc.descriptiontexten
dc.description.abstractAlternating minimization (AltMin) is a generic term for a widely popular approach in non-convex learning: often, it is possible to partition the variables into two (or more) sets, so that the problem is convex/tractable in one set if the other is held fixed (and vice versa). This allows for alternating between optimally updating one set of variables, and then the other. AltMin methods typically do not have associated global consistency guarantees; even though they are empirically observed to perform better than methods (e.g. based on convex optimization) that do have guarantees. In this thesis, we obtain rigorous performance guarantees for AltMin in three statistical learning settings: low rank matrix completion, phase retrieval and learning sparsely-used dictionaries. The overarching theme behind our results consists of two parts: (i) devising new initialization procedures (as opposed to doing so randomly, as is typical), and (ii) establishing exponential local convergence from this initialization. Our work shows that the pursuit of statistical guarantees can yield algorithmic improvements (initialization in our case) that perform better in practice.en
dc.format.mimetypeapplication/pdfen
dc.language.isoenen
dc.subjectAlternating minimizationen
dc.subjectAlternating least squaresen
dc.subjectMatrix completionen
dc.subjectPhase retrievalen
dc.subjectDictionary learningen
dc.subjectSparse dictionariesen
dc.subjectIterative methodsen
dc.subjectNon-convex optimizationen
dc.titleProvable alternating minimization for non-convex learning problemsen
dc.typeThesisen
dc.date.updated2014-09-17T19:15:21Zen
dc.description.departmentElectrical and Computer Engineeringen
thesis.degree.departmentElectrical and Computer Engineeringen
thesis.degree.disciplineElectrical and Computer Engineeringen
thesis.degree.grantorThe University of Texas at Austinen
thesis.degree.levelDoctoralen
thesis.degree.nameDoctor of Philosophyen


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record