# Revisiting the Approximate Carath'eodory Problem via the Frank-Wolfe Algorithm

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

## Key facts

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

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

- [Complexity of Linear Minimization and Projection on Some Sets](https://mlsanity.com/paper/2101.10040/) (2021)
- [Online Structured Prediction with Fenchel--Young Losses and Improved Surrogate Regret for Online Multiclass Classification with Logistic Loss](https://mlsanity.com/paper/2402.08180/) (2024)
- [Local and Global Uniform Convexity Conditions](https://mlsanity.com/paper/2102.05134/) (2021)
- [Geometric Algorithms for Neural Combinatorial Optimization with Constraints](https://mlsanity.com/paper/2510.24039/) (2025)
- [Efficient Test-Time Finetuning of LLMs via Convex Reconstruction and Gradient Caching](https://mlsanity.com/paper/2605.30337/) (2026)
- [Frank Wolfe Meets Metric Entropy](https://mlsanity.com/paper/2205.08634/) (2022)
- [Approximate Real Symmetric Tensor Rank](https://mlsanity.com/paper/2207.12529/) (2022)
- [Nonsmooth Projection-Free Optimization with Functional Constraints](https://mlsanity.com/paper/2311.11180/) (2023)
- [Multi-Play Combinatorial Semi-Bandit Problem](https://mlsanity.com/paper/2509.09933/) (2025)
- [Convex-Geometric Error Bounds for Positive-Weight Kernel Quadrature](https://mlsanity.com/paper/2605.05705/) (2026)
- [Self-Supervised Combinatorial Optimization with Constraints via Frank-Wolfe](https://mlsanity.com/paper/2609.25728/) (2026)

## Abstract (arXiv)

The approximate Carath'eodory theorem states that given a compact convex set Csubsetℝn and p∈left[2,+∞right[, each point x^*∈C can be approximated to ε-accuracy in the ℓp-norm as the convex combination of O(pDp2/ε2) vertices of C, where Dp is the diameter of C in the ℓp-norm. A solution satisfying these properties can be built using probabilistic arguments or by applying mirror descent to the dual problem. We revisit the approximate Carath'eodory problem by solving the primal problem via the Frank-Wolfe algorithm, providing a simplified analysis and leading to an efficient practical method. Furthermore, improved cardinality bounds are derived naturally using existing convergence rates of the Frank-Wolfe algorithm in different scenarios, when x^* is in the interior of C, when x^* is the convex combination of a subset of vertices with small diameter, or when C is uniformly convex. We also propose cardinality bounds when p∈left[1,2right[cup+∞ via a nonsmooth variant of the algorithm. Lastly, we address the problem of finding sparse approximate projections onto C in the ℓp-norm, p∈left[1,+∞right].