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.

本文提出了一种快速算法来处理凸多面体中点的问题，并在此基础上对子模函数最小化和 SVM 训练提供了新算法。