Loading Events
  • This event has passed.
Stochastics and Statistics Seminar

An Extended Frank-Wolfe Method with Application to Low-Rank Matrix Completion

September 11, 2015 @ 11:00 am - 12:00 pm

Rob Freund (MIT Sloan)


We present an extension of the Frank-Wolfe method that is designed to induce near-optimal solutions on low-dimensional faces of the feasible region. We present computational guarantees for the method that trade off efficiency in computing near-optimal solutions with upper bounds on the dimension of minimal faces of iterates. We apply our method to the low-rank matrix completion problem, where low-dimensional faces correspond to low-rank solutions. We present computational results for large-scale low-rank matrix completion problems that demonstrate significant speed-ups in computing low-rank near-optimal solutions on both artificial and real datasets. This is joint work with Paul Grigas (ORC) and Rahul Mazumder (Sloan).

MIT Statistics + Data Science Center
Massachusetts Institute of Technology
77 Massachusetts Avenue
Cambridge, MA 02139-4307