# Adaptive Conditional Gradient Descent

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 23 of its 53 references that are in the map.
- First posted on arXiv 13 Oct 2025.

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

- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [Training Deep Learning Models with Norm-Constrained LMOs](https://mlsanity.com/paper/2502.07529/) (2025)
- [Adaptive Gradient Descent without Descent](https://mlsanity.com/paper/1910.09529/) (2019)
- [Coordinate Descent Converges Faster with the Gauss-Southwell Rule Than Random Selection](https://mlsanity.com/paper/1506.00552/) (2015)
- [Adaptive Proximal Gradient Method for Convex Optimization](https://mlsanity.com/paper/2308.02261/) (2023)
- [Complexity of Linear Minimization and Projection on Some Sets](https://mlsanity.com/paper/2101.10040/) (2021)
- [An Almost-Linear-Time Algorithm for Approximate Max Flow in Undirected Graphs, and its Multicommodity Generalizations](https://mlsanity.com/paper/1304.2338/) (2013)
- [Generalized Gradient Norm Clipping & Non-Euclidean (L0,L1)-Smoothness](https://mlsanity.com/paper/2506.01913/) (2025)
- [A Unified Optimization View on Generalized Matching Pursuit and Frank-Wolfe](https://mlsanity.com/paper/1702.06457/) (2017)
- [Linearly Convergent Frank-Wolfe with Backtracking Line-Search](https://mlsanity.com/paper/1806.05123/) (2018)
- [Frank-Wolfe and friends: a journey into projection-free first-order optimization methods](https://mlsanity.com/paper/2106.10261/) (2021)
- [Matrix Scaling and Balancing via Box Constrained Newton's Method and Interior Point Methods](https://mlsanity.com/paper/1704.02310/) (2017)
- [Accelerated Methods for α-Weakly-Quasi-Convex Problems](https://mlsanity.com/paper/1710.00797/) (2017)
- [On Matching Pursuit and Coordinate Descent](https://mlsanity.com/paper/1803.09539/) (2018)
- [On the complexity of finding a local minimizer of a quadratic function over a polytope](https://mlsanity.com/paper/2008.05558/) (2020)
- [Continuized Acceleration for Quasar Convex Functions in Non-Convex Optimization](https://mlsanity.com/paper/2302.07851/) (2023)
- [An Affine Invariant Linear Convergence Analysis for Frank-Wolfe Algorithms](https://mlsanity.com/paper/1312.7864/) (2013)
- [Beyond Short Steps in Frank-Wolfe Algorithms](https://mlsanity.com/paper/2501.18773/) (2025)
- [Convex mixed-integer optimization with Frank-Wolfe methods](https://mlsanity.com/paper/2208.11010/) (2022)
- [Frank-Wolfe algorithm for star-convex functions](https://mlsanity.com/paper/2507.17272/) (2025)
- [Accelerated Affine-Invariant Convergence Rates of the Frank-Wolfe Algorithm with Open-Loop Step-Sizes](https://mlsanity.com/paper/2310.04096/) (2023)
- [Secant Line Search for Frank-Wolfe Algorithms](https://mlsanity.com/paper/2501.18775/) (2025)
- [Smooth Quasar-Convex Optimization with Constraints](https://mlsanity.com/paper/2510.01943/) (2025)

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

- [Boosted Stochastic Frank-Wolfe for Constrained Nonconvex Optimization](https://mlsanity.com/paper/2605.25255/) (2026)

## Abstract (arXiv)

Selecting an effective step-size is a fundamental challenge in first-order optimization, especially for problems with non-Euclidean geometries. This paper presents a novel adaptive step-size strategy for optimization algorithms that rely on linear minimization oracles, as used in the Conditional Gradient or non-Euclidean Normalized Steepest Descent algorithms. Using a simple heuristic to estimate a local Lipschitz constant for the gradient, we can determine step-sizes that guarantee sufficient decrease at each iteration. More precisely, we establish convergence guarantees for our proposed Adaptive Conditional Gradient Descent algorithm, which covers as special cases both the classical Conditional Gradient algorithm and non-Euclidean Normalized Steepest Descent algorithms with adaptive step-sizes. Our analysis covers optimization of continuously differentiable functions in non-convex, quasar-convex, and strongly convex settings, achieving convergence rates that match state-of-the-art theoretical bounds. Comprehensive numerical experiments validate our theoretical findings and illustrate the practical effectiveness of Adaptive Conditional Gradient Descent. The results exhibit competitive performance, underscoring the potential of the adaptive step-size for applications.