[Colloquium] REMINDER: 10/23 Research at TTIC: Srinadh Bhojanapalli, TTIC

[Mary Marre]

*When: *    Friday, October 23th at noon

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

*Who: *       Srinadh Bhojanapalli, TTIC

*Title*: Dropping Convexity for Faster Semi-definite Optimization


*Abstract:*
A matrix X ∈ Rn×n is positive semi-definite (PSD) if and only if it can be
written as the product UU⊤, for some matrix U. In this talk we explore the
use of this observation for optimization: specifically, we consider the
minimization of a convex function f over the positive semi-definite cone X
≽ 0, but via gradient descent on f(UU⊤), which is a non-convex function of
U.

We focus on the (empirically quite popular) approach where, for
computational or statistical reasons, U is set to be an n × r matrix for
some r ≤ n, and correspondingly f satisfies restricted strong convexity
(setting r = n recovers the exact case with global strong convexity).

We develop a special choice of step size, and show that updating U via
gradient descent with this choice results in linear convergence to the
top-r components of the optimum of f; provided we start from a point which
has constant relative distance to the optimum. We also develop an
initialization scheme for the “first-order oracle” setting.


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

*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/20151022/5b1be991/attachment.htm