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

arXiv: https://arxiv.org/abs/1511.02204 · HTML: https://mlsanity.com/paper/1511.02204/

## Key facts

- Cited by 15 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 6 Nov 2015.

## Built on by (most cited first, 15 of 15)

- [Complexity of Linear Minimization and Projection on Some Sets](https://mlsanity.com/paper/2101.10040/) (2021)
- [Breaking the Linear Iteration Cost Barrier for Some Well-known Conditional Gradient Methods Using MaxIP Data-structures](https://mlsanity.com/paper/2111.15139/) (2021)
- [Heavy Ball Momentum for Conditional Gradient](https://mlsanity.com/paper/2110.04243/) (2021)
- [Zeroth and First Order Stochastic Frank-Wolfe Algorithms for Constrained Optimization](https://mlsanity.com/paper/2107.06534/) (2021)
- [Fast Stochastic Composite Minimization and an Accelerated Frank-Wolfe Algorithm under Parallelization](https://mlsanity.com/paper/2205.12751/) (2022)
- [Reusing Combinatorial Structure: Faster Iterative Projections over Submodular Base Polytopes](https://mlsanity.com/paper/2106.11943/) (2021)
- [Accelerating Frank-Wolfe via Averaging Step Directions](https://mlsanity.com/paper/2205.11794/) (2022)
- [Conditional Gradients for the Approximate Vanishing Ideal](https://mlsanity.com/paper/2202.03349/) (2022)
- [Faster One-Sample Stochastic Conditional Gradient Method for Composite Convex Minimization](https://mlsanity.com/paper/2202.13212/) (2022)
- [Scalable DC Optimization via Adaptive Frank-Wolfe Algorithms](https://mlsanity.com/paper/2507.17545/) (2025)
- [Generating Structured Adversarial Attacks Using Frank-Wolfe Method](https://mlsanity.com/paper/2102.07360/) (2021)
- [Screening for a Reweighted Penalized Conditional Gradient Method](https://mlsanity.com/paper/2107.01106/) (2021)
- [Using Taylor-Approximated Gradients to Improve the Frank-Wolfe Method for Empirical Risk Minimization](https://mlsanity.com/paper/2208.13933/) (2022)
- [Reducing Discretization Error in the Frank-Wolfe Method](https://mlsanity.com/paper/2304.01432/) (2023)
- [A Randomized Linearly Convergent Frank-Wolfe-type Method for Smooth Convex Minimization over the Spectrahedron](https://mlsanity.com/paper/2503.01441/) (2025)

## Abstract (arXiv)

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.