Tight Bounds for Approximate Carathéodory and Beyond

Vahab S. Mirrokni, Renato Paes Leme, Adrian Vladu, Sam Chiu-wai Wong

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$.

Formal definition of the Approximate Carathéodory Problem.

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:

  1. A minimization player seeking the best sparse convex combination.
  2. 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

Abstract

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\'{e}odory Problem, which states that any point inside a polytope contained in the $\ell_p$ ball of radius $D$ can be approximated to within $\epsilon$ in $\ell_p$ norm by a convex combination of only $O\left(D^2 p/\epsilon^2\right)$ vertices of the polytope for $p \geq 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/\epsilon^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.
BibTeX
@inproceedings{mirrokni2017tight,
  author = {Vahab S. Mirrokni and Renato Paes Leme and Adrian Vladu and Sam Chiu-wai Wong},
  title = {{Tight Bounds for Approximate Carathéodory and Beyond}},
  booktitle = {International Conference on Machine Learning},
  year = {2017},
  url = {https://openreview.net/forum?id=ByV15o-OZH},
}
Figure