Tight Bounds for Approximate Carathéodory and Beyond
[edit]
Proceedings of the 34th International Conference on Machine Learning, PMLR 70:24402448, 2017.
Abstract
We present a deterministic nearlylinear 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é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 $O\left(D^2 p/\epsilon^2\right)$ vertices of the polytope for $p \geq 2$. While for the particular case of $p=2$, this can be achieved by the wellknown Perceptron algorithm, we follow a more principled approach which generalizes to arbitrary $p\geq 2$; furthermore, this naturally extends to domains with more complicated geometry, as it is the case for providing an approximate Birkhoffvon Neumann decomposition. Secondly, we show that the sparsity bound is tight for $\ell_p$ norms, using an argument based on anticoncentration for the binomial distribution, thus resolving an open question posed by Barman. Experimentally, we verify that our deterministic optimizationbased algorithms achieve in practice much better sparsity than previously known samplingbased algorithms. We also show how to apply our techniques to SVM training and rounding fractional points in matroid and flow polytopes.
Related Material


