# Splitting the Conditional Gradient Algorithm

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 9 Nov 2023.

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

- [Adaptive Lipschitz-Free Conditional Gradient Methods for Stochastic Composite Nonconvex Optimization](https://mlsanity.com/paper/2603.06369/) (2026)

## Abstract (arXiv)

We propose a novel generalization of the conditional gradient (CG / Frank-Wolfe) algorithm for minimizing a smooth function f under an intersection of compact convex sets, using a first-order oracle for nabla f and linear minimization oracles (LMOs) for the individual sets. Although this computational framework presents many advantages, there are only a small number of algorithms which require one LMO evaluation per set per iteration; furthermore, these algorithms require f to be convex. Our algorithm appears to be the first in this class which is proven to also converge in the nonconvex setting. Our approach combines a penalty method and a product-space relaxation. We show that one conditional gradient step is a sufficient subroutine for our penalty method to converge, and we provide several analytical results on the product-space relaxation's properties and connections to other problems in optimization. We prove that our average Frank-Wolfe gap converges at a rate of O(ln t/√t), -- only a log factor worse than the vanilla CG algorithm with one set.