Provable Non-convex Projections for High-dimensional Learning Problems

Speaker:        Prateek Jain
                Microsoft Research Lab, India

Title:          "Provable Non-convex Projections for High-dimensional
                 Learning Problems"

Date:           Friday, 16 October 2015

Time:           2:00pm - 3:00pm

Venue:          Room 2303 (via lifts 17/18), HKUST

Abstract:

Typical high-dimensional learning problems such as sparse regression,
low-rank matrix completion, robust PCA etc can be solved using projections
onto non-convex sets. However, providing theoretical guarantees for such
methods is difficult due to the non-convexity in projections. In this
talk, we will discuss some of our recent results that show that non-convex
projections based methods can be used to solve several important problems
in this area such as: a) sparse regression, b) low-rank matrix completion,
c) robust PCA.

In this talk, we will give an overview of the state-of-the-art for these
problems and also discuss how simple non-convex techniques can
significantly outperform state-of-the-art convex relaxation based
techniques and provide solid theoretical results as well. For example, for
robust PCA, we provide first provable algorithm with time complexity O(n^2
r) which matches the time complexity of normal SVD and is faster than the
usual nuclear+L_1-regularization methods that incur O(n^3) time
complexity. This talk is based on joint works with Ambuj Tewari,
Purushottam Kar, Praneeth Netrapalli, Animashree Anandkumar, U N Niranjan,
and Sujay Sanghavi.


*****************
Biography:

Prateek Jain is a researcher at Microsoft Research Lab, India since Jan
2010. Before joining MSRI, Prateek got his PhD and MS from CS Dept., The
University of Texas at Austin in Dec 2009, under the guidance of Prof.
Inderjit S. Dhillon. He got his BTech degree in Computer Science from IIT
Kanpur in 2004. Prateek's primary research interests are in Machine
Learning, Non-convex Optimization and Linear Algebra.