# Reducing Discretization Error in the Frank-Wolfe Method

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 18 of its 37 references that are in the map.
- First posted on arXiv 4 Apr 2023.

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

- [A Differential Equation for Modeling Nesterov's Accelerated Gradient Method: Theory and Insights](https://mlsanity.com/paper/1503.01243/) (2015)
- [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)
- [Gap Safe screening rules for sparsity enforcing penalties](https://mlsanity.com/paper/1611.05780/) (2016)
- [The Approximate Duality Gap Technique: A Unified Theory of First-Order Methods](https://mlsanity.com/paper/1712.02485/) (2017)
- [Acceleration via Symplectic Discretization of High-Resolution Differential Equations](https://mlsanity.com/paper/1902.03694/) (2019)
- [Direct Runge-Kutta Discretization Achieves Acceleration](https://mlsanity.com/paper/1805.00521/) (2018)
- [New Analysis and Results for the Frank-Wolfe Method](https://mlsanity.com/paper/1307.0873/) (2013)
- [Let's Make Block Coordinate Descent Converge Faster: Faster Greedy Rules, Message-Passing, Active-Set Complexity, and Superlinear Convergence](https://mlsanity.com/paper/1712.08859/) (2017)
- [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)
- [Barrier Frank-Wolfe for Marginal Inference](https://mlsanity.com/paper/1511.02124/) (2015)
- [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)
- [Safe Screening for the Generalized Conditional Gradient Method](https://mlsanity.com/paper/2002.09718/) (2020)
- [How Does Momentum Help Frank Wolfe?](https://mlsanity.com/paper/2006.11116/) (2020)

## Abstract (arXiv)

The Frank-Wolfe algorithm is a popular method in structurally constrained machine learning applications, due to its fast per-iteration complexity. However, one major limitation of the method is a slow rate of convergence that is difficult to accelerate due to erratic, zig-zagging step directions, even asymptotically close to the solution. We view this as an artifact of discretization; that is to say, the Frank-Wolfe flow, which is its trajectory at asymptotically small step sizes, does not zig-zag, and reducing discretization error will go hand-in-hand in producing a more stabilized method, with better convergence properties. We propose two improvements: a multistep Frank-Wolfe method that directly applies optimized higher-order discretization schemes; and an LMO-averaging scheme with reduced discretization error, and whose local convergence rate over general convex sets accelerates from a rate of O(1/k) to up to O(1/k3/2).