# Revisiting Frank-Wolfe for Structured Nonconvex Optimization

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 18 of its 49 references that are in the map.
- First posted on arXiv 11 Mar 2025.

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

- [EfficientNet: Rethinking Model Scaling for Convolutional Neural Networks](https://mlsanity.com/paper/1905.11946/) (2019)
- [Enriching Word Vectors with Subword Information](https://mlsanity.com/paper/1607.04606/) (2016)
- [Word Translation Without Parallel Data](https://mlsanity.com/paper/1710.04087/) (2017)
- [Old Optimizer, New Norm: An Anthology](https://mlsanity.com/paper/2409.20325/) (2024)
- [Convergence Rate of Frank-Wolfe for Non-Convex Objectives](https://mlsanity.com/paper/1607.00345/) (2016)
- [Faster Rates for the Frank-Wolfe Method over Strongly-Convex Sets](https://mlsanity.com/paper/1406.1305/) (2014)
- [A gradient sampling method with complexity guarantees for Lipschitz functions in high and low dimensions](https://mlsanity.com/paper/2112.06969/) (2021)
- [Disciplined Convex-Concave Programming](https://mlsanity.com/paper/1604.02639/) (2016)
- [Deep Neural Network Training with Frank-Wolfe](https://mlsanity.com/paper/2010.07243/) (2020)
- [Complexity of Linear Minimization and Projection on Some Sets](https://mlsanity.com/paper/2101.10040/) (2021)
- [Convergence guarantees for a class of non-convex and non-smooth optimization problems](https://mlsanity.com/paper/1804.09629/) (2018)
- [Fixed-point algorithms for learning determinantal point processes](https://mlsanity.com/paper/1508.00792/) (2015)
- [Non-convex Conditional Gradient Sliding](https://mlsanity.com/paper/1708.04783/) (2017)
- [On the rate of convergence of the Difference-of-Convex Algorithm (DCA)](https://mlsanity.com/paper/2109.13566/) (2021)
- [The cost of nonconvexity in deterministic nonsmooth optimization](https://mlsanity.com/paper/2210.00652/) (2022)
- [CCCP is Frank-Wolfe in disguise](https://mlsanity.com/paper/2206.12014/) (2022)
- [Best-Effort Adaptation](https://mlsanity.com/paper/2305.05816/) (2023)
- [Addressing misspecification in contextual optimization](https://mlsanity.com/paper/2409.10479/) (2024)

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

- [Scalable DC Optimization via Adaptive Frank-Wolfe Algorithms](https://mlsanity.com/paper/2507.17545/) (2025)
- [Analytical Evaluation of DCA Convergence Properties for Minimizing Prediction Functions of Gaussian RBF Support Vector Regression](https://mlsanity.com/paper/2606.03559/) (2026)

## Abstract (arXiv)

We introduce a new projection-free (Frank-Wolfe) method for optimizing structured nonconvex functions that are expressed as a difference of two convex functions. This problem class subsumes smooth nonconvex minimization, positioning our method as a promising alternative to the classical Frank-Wolfe algorithm. DC decompositions are not unique; by carefully selecting a decomposition, we can better exploit the problem structure, improve computational efficiency, and adapt to the underlying problem geometry to find better local solutions. We prove that the proposed method achieves a first-order stationary point in O(1/ε2) iterations, matching the complexity of the standard Frank-Wolfe algorithm for smooth nonconvex minimization in general. Specific decompositions can, for instance, yield a gradient-efficient variant that requires only O(1/ε) calls to the gradient oracle. Finally, we present numerical experiments demonstrating the effectiveness of the proposed method compared to other projection-free algorithms.