# Tight Bounds for Approximate Carath'eodory and Beyond

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 29 Dec 2015.

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

- [Best-of-Three-Worlds Linear Bandit Algorithm with Variance-Adaptive Regret Bounds](https://mlsanity.com/paper/2302.12370/) (2023)
- [Aligning Compound AI Systems via System-level DPO](https://mlsanity.com/paper/2502.17721/) (2025)
- [Geometric Algorithms for Neural Combinatorial Optimization with Constraints](https://mlsanity.com/paper/2510.24039/) (2025)
- [Online Learning for Non-monotone Submodular Maximization: From Full Information to Bandit Feedback](https://mlsanity.com/paper/2208.07632/) (2022)
- [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)
- [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)

We give a deterministic nearly-linear time algorithm for approximating any point inside a convex polytope with a sparse convex combination of the polytope's vertices. Our result provides a constructive proof for the Approximate Carath'eodory Problem, which states that any point inside a polytope contained in the ℓp ball of radius D can be approximated to within ε in ℓp norm by a convex combination of only Oleft(D2 p/ε2right) vertices of the polytope for p ≥ 2. We also show that this bound is tight, using an argument based on anti-concentration for the binomial distribution. Along the way of establishing the upper bound, we develop a technique for minimizing norms over convex sets with complicated geometry; this is achieved by running Mirror Descent on a dual convex function obtained via Sion's Theorem. As simple extensions of our method, we then provide new algorithms for submodular function minimization and SVM training. For submodular function minimization we obtain a simplification and (provable) speed-up over Wolfe's algorithm, the method commonly found to be the fastest in practice. For SVM training, we obtain O(1/ε2) convergence for arbitrary kernels; each iteration only requires matrix-vector operations involving the kernel matrix, so we overcome the obstacle of having to explicitly store the kernel or compute its Cholesky factorization.