[Colloquium] 2/26 Research at TTIC: Dan Garber, TTIC

[Mary Marre]

When:     Friday, February 26th at noon

Where:    TTIC, 6045 S Kenwood Avenue, 5th Floor, Room 526

Who:      Dan Garber, TTIC


Title: Fast and Simple PCA via Convex Optimization

Abstract:

Computing the leading eigenvector of a real symmetric matrix is a
fundamental problem in numerical linear algebra with numerous important
applications, the most notable one probably being  principal component
analysis. Thus, in face of the ever increasing size of modern datasets,
designing faster algorithms for this problem is an important challenge.
Unfortunately, this problem is inherently non-convex, which makes it very
difficult
to adapt to it powerful techniques that were developed for convex problems,
such as Nesterov's acceleration and various stochastic gradient methods,
that proved highly useful for handling large scale convex problems.

In this talk I will show that the leading eigenvector problem, though not
convex, is reducible to solving a short (i.e. only poly-logarithmic in the
important parameters of the problem) sequence of well-conditioned
unconstrained convex optimization problems. This in turn, allows us to
apply state-of-the-art stochastic gradient methods for solving this
sequence of problems. As a result we derive algorithms for computing the
leading principal component which are the fastest to date in a wide regime
of parameters.


********************************************************************

*Research at TTIC Seminar Series*

TTIC is hosting a weekly seminar series presenting the research currently
underway at the Institute. Every week a different TTIC faculty member will
present their research.  The lectures are intended both for students
seeking research topics and adviser, and for the general TTIC and
University of Chicago communities interested in hearing what their
colleagues are up to.

To receive announcements about the seminar series, please subscribe to the
mailing list: https://groups.google.com/a/ttic.edu/group/talks/subscribe

Speaker details can be found at: http://www.ttic.edu/tticseminar.php.

For additional questions, please contact David McAllester at
mcallester at ttic.edu

Mary C. Marre
Administrative Assistant
*Toyota Technological Institute*
*6045 S. Kenwood Avenue*
*Room 504*
*Chicago, IL  60637*
*p:(773) 834-1757*
*f: (773) 357-6970*
*mmarre at ttic.edu <mmarre at ttic.edu>*
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20160219/e6ebf110/attachment.htm