# On the Global Linear Convergence of Frank-Wolfe Optimization Variants

**Authors:** Simon Lacoste-Julien, Martin Jaggi  
**arXiv:** [1511.05932](https://arxiv.org/abs/1511.05932)  
**Date:** 2015-11-18  
**Summary page:** https://www.summarizepaper.com/en/paper/1511.05932v1/

## Key points

- The Frank-Wolfe (FW) optimization algorithm is effective for handling structured constraints in machine learning applications.
- A drawback of the FW algorithm is its slow convergence rate, especially at the boundary.
- An enhancement involves incorporating 'away steps' during optimization without needing a feasibility oracle to address the slow convergence issue.
- Authors Simon Lacoste-Julien and Martin Jaggi explore successful variants of the FW algorithm, including away-steps FW, pairwise FW, fully-corrective FW, and Wolfe's minimum norm point algorithm.
- These variants exhibit global linear convergence under a weaker condition than strong convexity of the objective function.
- The authors provide an elegant interpretation of the constant in the convergence rate as a product of the classical condition number of the function and a novel geometric quantity serving as a 'condition number' for the constraint set.
- Practical examples are offered where these algorithms have made significant impacts in optimizing flow polytopes, marginal polytopes, and base polytopes for submodular optimization.
- The paper emphasizes considering different variants to achieve global linear convergence even in challenging scenarios.

## Summary

The Frank-Wolfe (FW) optimization algorithm has regained popularity for its effectiveness in handling structured constraints in machine learning applications. However, a known drawback is its slow convergence rate, especially at the boundary. To address this issue, an enhancement involves incorporating 'away steps' during optimization without needing a feasibility oracle. In their paper titled "On the Global Linear Convergence of Frank-Wolfe Optimization Variants," authors Simon Lacoste-Julien and Martin Jaggi delve into various successful variants of the FW algorithm. These include away-steps FW, pairwise FW, fully-corrective FW, and Wolfe's minimum norm point algorithm. The authors prove for the first time that these variants exhibit global linear convergence under a weaker condition than strong convexity of the objective function. One key highlight is the elegant interpretation of the constant in the convergence rate as a product of the classical condition number of the function and a novel geometric quantity serving as a 'condition number' for the constraint set. This unique perspective sheds light on efficient optimization with FW variants. Furthermore, Lacoste-Julien and Jaggi offer practical examples where these algorithms have made significant impacts in optimizing flow polytopes, marginal polytopes, and base polytopes for submodular optimization. By showcasing real-world applications, they demonstrate how these FW variants can effectively tackle complex optimization problems prevalent in machine learning and related fields. Overall, this paper provides valuable insights into enhancing FW optimization algorithms through innovative approaches and theoretical analysis while emphasizing considering different variants to achieve global linear convergence even in challenging scenarios.