Papers › Revisiting the Approximate Carathéodory Problem via the Frank-Wolfe Algorithm
Revisiting the Approximate Carathéodory Problem via the Frank-Wolfe Algorithm
Cyrille W. Combettes, Sebastian Pokutta
The approximate Carath\'eodory theorem states that given a compact convex set 𝒞⊂ℝⁿ and p∈[2,+∞[, each point x^*∈𝒞 can be approximated to ϵ-accuracy in the ℓₚ-norm as the convex combination of 𝒪(pDₚ²/ϵ²) vertices of 𝒞, where Dₚ is the diameter of 𝒞 in the ℓₚ-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 𝒞, when x^* is the convex combination of a subset of vertices with small diameter, or when 𝒞 is uniformly convex. We also propose cardinality bounds when p∈[1,2[∪{+∞} via a nonsmooth variant of the algorithm. Lastly, we address the problem of finding sparse approximate projections onto 𝒞 in the ℓₚ-norm, p∈[1,+∞].
In Syntology Open this paper in Syntology's Atlas, the map of the papers in Syntology's graph and their citations.
Code
Repository list and official/mentioned flags are the archive's, frozen 2025-07-28. Reachability, where shown, is from one Syntology probe window (2026-09-16 to 2026-09-18); repositories not probed show nothing. GitHub stars are not tracked.
Code Syntology ran Syntology
Not run by Syntology. Nothing on this page verifies that the listed code works.
Results from the paper archive 2025-07-28
No leaderboard rows for this paper in the archive.
Report a problem or propose a change · a person checks every report against the paper or source before anything changes; decisions are listed on /corrections