# kFW: A Frank-Wolfe style algorithm with stronger subproblem oracles

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 29 Jun 2020.

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

- [Low-Rank Extragradient Method for Nonsmooth and Low-Rank Matrix Optimization Problems](https://mlsanity.com/paper/2202.04026/) (2022)
- [Accelerating Frank-Wolfe via Averaging Step Directions](https://mlsanity.com/paper/2205.11794/) (2022)
- [Efficiency of First-Order Methods for Low-Rank Tensor Recovery with the Tensor Nuclear Norm Under Strict Complementarity](https://mlsanity.com/paper/2308.01677/) (2023)
- [Low-Rank Mirror-Prox for Nonsmooth and Low-Rank Matrix Optimization Problems](https://mlsanity.com/paper/2206.11523/) (2022)
- [Reducing Discretization Error in the Frank-Wolfe Method](https://mlsanity.com/paper/2304.01432/) (2023)
- [Scalable High-Dimensional Multivariate Linear Regression for Feature-Distributed Data](https://mlsanity.com/paper/2307.03410/) (2023)
- [Accelerated Frank-Wolfe Algorithms: Complementarity Conditions and Sparsity](https://mlsanity.com/paper/2511.02821/) (2025)

## Abstract (arXiv)

This paper proposes a new variant of Frank-Wolfe (FW), called kFW. Standard FW suffers from slow convergence: iterates often zig-zag as update directions oscillate around extreme points of the constraint set. The new variant, kFW, overcomes this problem by using two stronger subproblem oracles in each iteration. The first is a k linear optimization oracle (kLOO) that computes the k best update directions (rather than just one). The second is a k direction search (kDS) that minimizes the objective over a constraint set represented by the k best update directions and the previous iterate. When the problem solution admits a sparse representation, both oracles are easy to compute, and kFW converges quickly for smooth convex objectives and several interesting constraint sets: kFW achieves finite frac4Lf3D4γδ2 convergence on polytopes and group norm balls, and linear convergence on spectrahedra and nuclear norm balls. Numerical experiments validate the effectiveness of kFW and demonstrate an order-of-magnitude speedup over existing approaches.