Date: Friday, March 23, 2018
Location: 1084 East Hall (4:10 PM to 5:00 PM)
Title: The Landscape of Non-Convex Quadratic Feasibility
Abstract: Traditionally, a non-convex problem is oftentimes solved by solving a convex approximation since finding the global minimizer of a convex problem is theoretically efficient. Unfortunately, there can be a mismatch between practice and theory since the convex optimization approach can be practically slow. On the other hand, solving the original non-convex problem directly can be much faster in practice although in general, it is unclear whether these methods succeed since non-convex functions can have many saddle points and local minima.
Recently, researchers have closed the gap theoretically in understanding why solving non-convex problems directly reliably finds the global minimum. Under appropriate assumptions, in many important problems--like in matrix completion and simple neural networks--the reason for success is because every local minimum is a global minimum.
Motivated by this success and applications such as ordinal embedding and collaborative ranking, in this talk, we formulate homogeneous quadratic feasibility as an unconstrained, non-convex minimization problem and aim to understand the landscape (local minimizers and global minimizers) of the non-convex objective since the efficacy of applying a first-order method like stochastic gradient descent hinges on the landscape. The only prerequisite of this talk is calculus.
Files:
Speaker: Amanda Bower
Institution: University of Michigan
Event Organizer: Audra McMillan amcm@umich.edu
|