# Conditional Gradient Algorithms for Norm-Regularized Smooth Convex Optimization

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

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 10 Feb 2013.

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

- [No-Regret Dynamics in the Fenchel Game: A Unified Framework for Algorithmic Convex Optimization](https://mlsanity.com/paper/2111.11309/) (2021)
- [Regularized Frank-Wolfe for Dense CRFs: Generalizing Mean Field and Beyond](https://mlsanity.com/paper/2110.14759/) (2021)
- [Enhancing LLM Training via Spectral Clipping](https://mlsanity.com/paper/2603.14315/) (2026)
- [A Projection-free Algorithm for Constrained Stochastic Multi-level Composition Optimization](https://mlsanity.com/paper/2202.04296/) (2022)
- [Heavy Ball Momentum for Conditional Gradient](https://mlsanity.com/paper/2110.04243/) (2021)
- [Constrained Stochastic Nonconvex Optimization with State-dependent Markov Data](https://mlsanity.com/paper/2206.11346/) (2022)
- [Fast Stochastic Composite Minimization and an Accelerated Frank-Wolfe Algorithm under Parallelization](https://mlsanity.com/paper/2205.12751/) (2022)
- [Stochastic Constrained Decentralized Optimization for Machine Learning with Fewer Data Oracles: a Gradient Sliding Approach](https://mlsanity.com/paper/2404.02511/) (2024)
- [Approximate Frank-Wolfe Algorithms over Graph-structured Support Sets](https://mlsanity.com/paper/2107.00472/) (2021)
- [Screening for a Reweighted Penalized Conditional Gradient Method](https://mlsanity.com/paper/2107.01106/) (2021)
- [A conditional gradient homotopy method with applications to Semidefinite Programming](https://mlsanity.com/paper/2207.03101/) (2022)
- [Conic Descent Redux for Memory-Efficient Optimization](https://mlsanity.com/paper/2308.07343/) (2023)
- [Quantum Algorithms for Projection-Free Sparse Convex Optimization](https://mlsanity.com/paper/2507.08543/) (2025)

## Abstract (arXiv)

Motivated by some applications in signal processing and machine learning, we consider two convex optimization problems where, given a cone K, a norm |·| and a smooth convex function f, we want either 1) to minimize the norm over the intersection of the cone and a level set of f, or 2) to minimize over the cone the sum of f and a multiple of the norm. We focus on the case where (a) the dimension of the problem is too large to allow for interior point algorithms, (b) |·| is "too complicated" to allow for computationally cheap Bregman projections required in the first-order proximal gradient algorithms. On the other hand, we assume that it is relatively easy to minimize linear forms over the intersection of K and the unit |·|-ball. Motivating examples are given by the nuclear norm with K being the entire space of matrices, or the positive semidefinite cone in the space of symmetric matrices, and the Total Variation norm on the space of 2D images. We discuss versions of the Conditional Gradient algorithm capable to handle our problems of interest, provide the related theoretical efficiency estimates and outline some applications.