Introduction
In the realm of convex geometry, Carathéodory’s Theorem is a fundamental result: it guarantees that any point within the convex hull of a set in $d$-dimensional space can be represented as a convex combination of at most $d+1$ points. While theoretically elegant, this result poses a significant computational challenge in modern machine learning and high-dimensional optimization, where the dimension $d$ can reach millions. In such contexts, an "exact" representation is often prohibitively expensive.
The Approximate Carathéodory Problem
To address the curse of dimensionality, researchers turn to the Approximate Carathéodory Problem. Instead of seeking an exact representation, we ask: if we allow for a small error $\epsilon$, can we represent a point using a much smaller, "sparse" subset of vertices? Ideally, this subset size should be dimension-free, depending only on the desired precision $\epsilon$ and the geometric properties of the set, rather than the ambient dimension $d$.
Historically, solutions to this problem were either randomized—relying on sampling techniques—or required solving the exact problem first, which defeats the purpose of seeking a fast approximation. This paper introduces a deterministic, nearly-linear time algorithm that achieves tight theoretical bounds on sparsity.
Methodology: Mirror Descent and Saddle-Points
The authors depart from traditional sampling-based approaches, instead framing the approximation as an optimization problem solved via Mirror Descent.
Saddle-Point Reformulation
The problem is reformulated as a zero-sum game (a saddle-point problem) between two players:
- A minimization player seeking the best sparse convex combination.
- A maximization player identifying directions where the current approximation performs poorly.
By applying Sion’s Minimax Theorem, the authors derive a dual convex function. They then apply Mirror Descent to this dual, using a specialized "Mirror Map"—a truncated version of the square $\ell_q$-norm.
Constructive Sparsity
A key feature of this algorithmic approach is its constructive nature. Each iteration of the Mirror Descent algorithm adds exactly one vertex to the convex combination. By bounding the number of iterations required to reach an error threshold $\epsilon$, the authors simultaneously provide a fast algorithm and a proof of the sparsity bound.
Key Insights
Dimension-Free Efficiency
The paper establishes that the number of vertices needed for an $\epsilon$-approximation in the $\ell_p$ norm is $O(p/\epsilon^2)$. Because this bound is independent of the dimension $d$, the method is exceptionally well-suited for "Big Data" applications where $d$ is very large.
Optimization as a Geometric Proof Tool
Beyond the specific algorithm, the paper demonstrates that Mirror Descent is more than just a solver; it is a powerful tool for constructively proving geometric theorems. By bypassing the need for an exact Carathéodory representation, the algorithm only requires a "Linear Optimization Oracle"—a mechanism to find the "best" vertex in a given direction.
Results and Applications
The research provides both theoretical breakthroughs and practical speedups:
- Tight Bounds: The authors prove that the $O(p/\epsilon^2)$ bound is tight for $p \ge 2$. Using a probabilistic construction with random $\pm 1$ matrices, they show that in the worst case, one cannot achieve better sparsity.
- SVM Training: For training $\nu$-Support Vector Machines (SVMs) with various kernels (Polynomial, RBF, Sigmoid), the algorithm achieves $O(1/\epsilon^2)$ convergence. Crucially, it only requires matrix-vector products, eliminating the need to store massive kernel matrices or perform expensive Cholesky factorizations.
- Submodular Optimization: The framework leads to a simplified and provably faster version of Wolfe’s algorithm, the industry standard for minimum-norm point problems in combinatorial optimization.
Conclusion and Future Directions
While this work closes a significant gap by providing tight, deterministic bounds, several avenues for future research remain. The authors note that for specific tasks like submodular function minimization, the "oracle complexity" (the number of function queries) might be further reduced. Additionally, exploring "friendly" geometries—where the target point is far from the polytope boundary—could yield even higher sparsity, potentially reducing the dependence on $1/\epsilon$ to logarithmic scales.
Summary updated