Efficient Quadratic Corrections for Frank-Wolfe Algorithms
math.OC
Submitted: 2025-06-03
Updated: 2026-05-20
Journal ref: Advances in Neural Information Processing Systems 38, 2025
DOI: 10.52202/085713-0819
License: http://creativecommons.org/licenses/by/4.0/
The gist: We develop a Frank-Wolfe algorithm with corrective steps, generalizing previous algorithms including blended conditional gradients, blended pairwise conditional gradients…
Terminology
Abstract
We develop a Frank-Wolfe algorithm with corrective steps, generalizing previous algorithms including blended conditional gradients, blended pairwise conditional gradients, and fully-corrective Frank-Wolfe. For this, we prove tight convergence guarantees together with an optimal face identification property. Furthermore, we propose two highly efficient corrective steps for convex quadratic objectives based on linear optimization or linear system solving, akin to Wolfe's minimum-norm point, and show that they converge in finite time under suitable conditions. Beyond optimization problems that are directly quadratic, we revisit two algorithms - split conditional gradient and second-order conditional gradient sliding - which can leverage quadratic corrections to accelerate their quadratic subproblems. We demonstrate improved convergence rates for the first and broader applicability for the second, which may be of independent interest. Finally, we show substantial computational speedups for Frank-Wolfe-based algorithms with quadratic corrections across the considered problem classes.
Sources
- Alternating Linear Minimization: Revisiting von Neumann's alternating projections
- Second-order Conditional Gradient Sliding
- Unified Toolbox for Multipartite Entanglement Certification
Related papers
- An Accelerated Proximal Gradient Method for Bures-Wasserstein Space
- FOMTools: Development and AI-Assisted Code Generation for First-Order Methods
- Lions and Muons: Optimization via Stochastic Frank-Wolfe under Heavy-Tailed Noise
- Dynamic Service Recommendation with Congestion-Dependent Joining: Near-Optimal and Constant-Factor Approximation Algorithms
- Integrating Learning and Optimization for Open Transport Capacity Pooling under Disruption
- Zeroth-Order Gradient Estimators under Decision-Dependent Noise