Frank-Wolfe is Approximate Broximal Gradient Descent
Abstract
We show that the Frank-Wolfe method is an approximation of Broximal Gradient Descent (BroxGD), and hence of the ball-proximal method. For constrained minimization, the ball-proximal method minimizes the objective over the intersection of the feasible set with a ball around the current iterate. Linearizing the objective gives BroxGD, but the intersection can remain difficult to handle even when linear minimization over the feasible set alone is cheap. We therefore replace the intersection by a smaller copy of the feasible set, obtained by shrinking it toward the current iterate so that it lies inside the ball. Minimizing the linear model over this smaller set gives exactly Frank-Wolfe, with the shrinking factor as its step size. We examine what this approximation preserves and what it can lose. For smooth convex objectives on compact convex sets, Frank-Wolfe retains a linear-model decrease guarantee that gives it and BroxGD a common convergence proof, recovering the classical O(1/k) bound. Among compact convex regions inside the ball chosen before the gradient is known, the smaller copy is the smallest that preserves the same linear-model decrease guarantee. Nevertheless, Frank-Wolfe can achieve much less linear-model decrease than BroxGD at the same radius. A simplex example illustrates the sparsity gained by restricting the region, while a family of triangles shows how Frank-Wolfe can lose the distance decrease guaranteed by BroxGD. We also give a computable test for recovering the distance guarantee and a refinement procedure that terminates after finitely many oracle calls on polytopes.
Related
- Broximal Gradient Descent: A Projection-Free Sister of Projected Gradient Descent
- A Frank-Wolfe-based primal heuristic for quadratic mixed-integer optimization
- Optimal input design via Frank-Wolfe
- Asynchronous Parallel Computation of Lagrangian Bounds for Mixed-Integer Stochastic Programs by Frank-Wolfe Methods within Projective Hedging
- Stochastic Compositional Optimization via Hybrid Momentum Frank--Wolfe
BibTeX
@misc{richtarik2026frankwolfe,
title = {{Frank-Wolfe is Approximate Broximal Gradient Descent}},
author = {Peter Richtárik and Zhirayr Tovmasyan},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2611.02942},
eprint = {2611.02942},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2611.02942},
}
RIS
TY - UNPB
TI - Frank-Wolfe is Approximate Broximal Gradient Descent
AU - Peter Richtárik
AU - Zhirayr Tovmasyan
PY - 2026
DA - 2026/11/02
PB - arXiv
DO - 10.48550/arxiv.2611.02942
UR - https://arxiv.org/abs/2611.02942
AB - We show that the Frank-Wolfe method is an approximation of Broximal Gradient Descent (BroxGD), and hence of the ball-proximal method. For constrained minimization, the ball-proximal method minimizes the objective over the intersection of the feasible set with a ball around the current iterate. Linearizing the objective gives BroxGD, but the intersection can remain difficult to handle even when linear minimization over the feasible set alone is cheap. We therefore replace the intersection by a smaller copy of the feasible set, obtained by shrinking it toward the current iterate so that it lies inside the ball. Minimizing the linear model over this smaller set gives exactly Frank-Wolfe, with the shrinking factor as its step size. We examine what this approximation preserves and what it can lose. For smooth convex objectives on compact convex sets, Frank-Wolfe retains a linear-model decrease guarantee that gives it and BroxGD a common convergence proof, recovering the classical O(1/k) bound. Among compact convex regions inside the ball chosen before the gradient is known, the smaller copy is the smallest that preserves the same linear-model decrease guarantee. Nevertheless, Frank-Wolfe can achieve much less linear-model decrease than BroxGD at the same radius. A simplex example illustrates the sparsity gained by restricting the region, while a family of triangles shows how Frank-Wolfe can lose the distance decrease guaranteed by BroxGD. We also give a computable test for recovering the distance guarantee and a refinement procedure that terminates after finitely many oracle calls on polytopes.
ER -