Efficient non-convex algorithms for large-scale learning problems

dc.contributor.advisorSanghavi, Sujay Rajendra, 1979-
dc.contributor.advisorCaramanis, Constantine
dc.contributor.committeeMemberGhosh, Joydeep
dc.contributor.committeeMemberDimakis, Alexandros G
dc.contributor.committeeMemberPrice, Eric
dc.creatorPark, Dohyung
dc.date.accessioned2017-04-25T20:15:30Z
dc.date.available2017-04-25T20:15:30Z
dc.date.issued2016-12
dc.date.submittedDecember 2016
dc.date.updated2017-04-25T20:15:30Z
dc.description.abstractThe emergence of modern large-scale datasets has led to a huge interest in the problem of learning hidden complex structures. Not only can models from such structures fit the datasets, they also have good generalization performance in the regime where the number of samples are limited compared to the dimensionality. However, one of the main issues is finding computationally efficient algorithms to learn the models. While convex relaxation provides polynomial-time algorithms with strong theoretical guarantees, there are demands for even faster algorithms with competitive performances, due to the large volume of the practical datasets. In this dissertation, we consider three types of algorithms, greedy methods, alternating minimization, and non-convex gradient descent, that have been key non-convex approaches to tackle the large-scale learning problems. For each theme, we focus on a specific problem and design an algorithm based on the designing ideas. We begin with the problem of subspace clustering, where one needs to learn underlying unions of subspaces from a set of data points around the subspaces. We develop two greedy algorithms that can perfectly cluster the points and recover the subspaces. The next problem of interest is collaborative ranking, where underlying low-rank preference matrices are to be learned from pairwise comparisons of the entries. We present an alternating minimization based algorithm. Finally, we develop a non-convex gradient descent algorithm for general low-rank matrix optimization problems. All of these algorithms exhibit low computational complexities as well as competitive statistical performances, which make them scalable and suitable for a variety of practical applications of the problems. Analysis of the algorithms provides theoretical guarantees of their performances.
dc.description.departmentElectrical and Computer Engineering
dc.embargo.lift2017-12-01
dc.embargo.terms2017-12-01
dc.format.mimetypeapplication/pdf
dc.identifierdoi:10.15781/T2R49GF66
dc.identifier.urihttp://hdl.handle.net/2152/46581
dc.language.isoen
dc.subjectMachine learning
dc.subjectNon-convex optimization
dc.titleEfficient non-convex algorithms for large-scale learning problems
dc.typeThesis
dc.type.materialtext
thesis.degree.departmentElectrical and Computer Engineering
thesis.degree.disciplineElectrical and Computer engineering
thesis.degree.grantorThe University of Texas at Austin
thesis.degree.levelDoctoral
thesis.degree.nameDoctor of Philosophy

Access full-text files

Original bundle

Now showing 1 - 1 of 1
Loading...
Thumbnail Image
Name:
PARK-DISSERTATION-2016.pdf
Size:
5.6 MB
Format:
Adobe Portable Document Format

License bundle

Now showing 1 - 1 of 1
No Thumbnail Available
Name:
LICENSE.txt
Size:
1.84 KB
Format:
Plain Text
Description: