Tight Bounds for Approximate Carathéodory and Beyond
By Vahab S. Mirrokni, Renato Paes Leme, Adrian Vladu, Sam Chiu-wai Wong. 2015
38 citations recorded by the source corpus.
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.
Subfields: Artificial Intelligence, Computational Mechanics, Computational Theory and Mathematics
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Artificial Intelligence
In Computational Mechanics
In Computational Theory and Mathematics
Citations in the corpus
- The Frank-Wolfe Algorithm: A Short Introduction (2023, unknown): “Otherwise, if 0 γ t 1, then dividing by γ t and plugging in the definition of In both cases, rearranging gives the desired inequality Finally, in case γ t = 0 we have x t = x t + 1 and the assertion holds trivially.”
- Second-order Conditional Gradients (2020, background): “Another important example is the approximate Carathéodory problem (Mirrokni et al., 2017; Combettes & Pokutta, 2019) where we want to find the decomposition of a point x 0 in a polytope P as a convex combination of the vertices of P and where the objective We stress that while we opted for the…”