# Accelerating Frank-Wolfe via Averaging Step Directions

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 10 of its 22 references that are in the map.
- First posted on arXiv 24 May 2022.

## Builds on (most cited first, 10 of 10)

- [On the Global Linear Convergence of Frank-Wolfe Optimization Variants](https://mlsanity.com/paper/1511.05932/) (2015)
- [Faster Rates for the Frank-Wolfe Method over Strongly-Convex Sets](https://mlsanity.com/paper/1406.1305/) (2014)
- [An Extended Frank-Wolfe Method with "In-Face" Directions, and its Application to Low-Rank Matrix Completion](https://mlsanity.com/paper/1511.02204/) (2015)
- [Local Linear Convergence of Forward-Backward under Partial Smoothness](https://mlsanity.com/paper/1407.5611/) (2014)
- [Local Convergence Properties of SAGA/Prox-SVRG and Acceleration](https://mlsanity.com/paper/1802.02554/) (2018)
- [Nonsmoothness in Machine Learning: specific structure, proximal identification, and applications](https://mlsanity.com/paper/2010.00848/) (2020)
- ["Active-set complexity" of proximal gradient: How long does it take to find the sparsity pattern?](https://mlsanity.com/paper/1712.03577/) (2017)
- [kFW: A Frank-Wolfe style algorithm with stronger subproblem oracles](https://mlsanity.com/paper/2006.16142/) (2020)
- [Gauge optimization and duality](https://mlsanity.com/paper/1310.2639/) (2013)
- [Continuous Time Frank-Wolfe Does Not Zig-Zag, But Multistep Methods Do Not Accelerate](https://mlsanity.com/paper/2106.05753/) (2021)

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

- [Assemblage: Automatic Binary Dataset Construction for Machine Learning](https://mlsanity.com/paper/2405.03991/) (2024)
- [Linearization Algorithms for Fully Composite Optimization](https://mlsanity.com/paper/2302.12808/) (2023)

## Abstract (arXiv)

The Frank-Wolfe method is a popular method in sparse constrained optimization, due to its fast per-iteration complexity. However, the tradeoff is that its worst case global convergence is comparatively slow, and importantly, is fundamentally slower than its flow rate--that is to say, the convergence rate is throttled by discretization error. In this work, we consider a modified Frank-Wolfe where the step direction is a simple weighted average of past oracle calls. This method requires very little memory and computational overhead, and provably decays this discretization error term. Numerically, we show that this method improves the convergence rate over several problems, especially after the sparse manifold has been detected. Theoretically, we show the method has an overall global convergence rate of O(1/kp), where 0< p < 1; after manifold identification, this rate speeds to O(1/k3p/2). We also observe that the method achieves this accelerated rate from a very early stage, suggesting a promising mode of acceleration for this family of methods.