An Extended Frank-Wolfe Method with "In-Face" Directions, and its Application to Low-Rank Matrix Completion

Motivated principally by the low-rank matrix completion problem, we present\nan extension of the Frank-Wolfe method that is designed to induce near-optimal\nsolutions on low-dimensional faces of the feasible region. This is accomplished\nby a new approach to generating ``in-face" directions at each iteration, as\nwell as through new choice rules for selecting between in-face and ``regular"\nFrank-Wolfe steps. Our framework for generating in-face directions generalizes\nthe notion of away-steps introduced by Wolfe. In particular, the in-face\ndirections always keep the next iterate within the minimal face containing the\ncurrent iterate. We present computational guarantees for the new method that\ntrade off efficiency in computing near-optimal solutions with upper bounds on\nthe dimension of minimal faces of iterates. We apply the new method to the\nmatrix completion problem, where low-dimensional faces correspond to low-rank\nmatrices. We present computational results that demonstrate the effectiveness\nof our methodological approach at producing nearly-optimal solutions of very\nlow rank. On both artificial and real datasets, we demonstrate significant\nspeed-ups in computing very low-rank nearly-optimal solutions as compared to\neither the Frank-Wolfe method or its traditional away-step variant.\n