2015/11/06 by Robert M. Freund, Freund, Robert M., Paul Grigas +3 · 3 citations
Mathematics · #90C25 #Computation (stat.CO) #FOS: Computer and information sciences #FOS: Mathematics #G.1.6 #Machine Learning (stat.ML) #Optimization and Control (math.OC) #acm:90C25 #math.OC #msc:90C25 #stat.CO #stat.ML
paper · pdf · doi:10.48550/arxiv.1511.02204
25 pages, 3 tables and 2 figues
arxiv created 2015/11/06 · arxiv updated 2015/11/09
Motivated principally by the low-rank matrix completion problem, 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. This is accomplished by a new approach to generating ``in-face" directions at each iteration, as well as through new choice rules for selecting between in-face and ``regular" Frank-Wolfe steps. Our framework for generating in-face directions generalizes the notion of away-steps introduced by Wolfe. In particular, the in-face directions always keep the next iterate within the minimal face containing the current iterate. We present computational guarantees for the new method that trade off efficiency in computing near-optimal solutions with upper bounds on the dimension of minimal faces of iterates. We apply the new method to the matrix completion problem, where low-dimensional faces correspond to low-rank matrices. We present computational results that demonstrate the effectiveness of our methodological approach at producing nearly-optimal solutions of very low rank. On both artificial and real datasets, we demonstrate significant speed-ups in computing very low-rank nearly-optimal solutions as compared to either the Frank-Wolfe method or its traditional away-step variant.