Approximate Carathéodory bounds via Discrepancy Theory

Abstract

The approximate Carathéodory problem in general form is as follows: Given two symmetric convex bodies $P,Q\subseteq {\mathbb{R}}^m$, a parameter $k\in \mathbb{N}$ and $\mathbf{z}\in \text{conv}(X)$ with $X\subseteq P$, find ${\mathbf{v}}_1,\dots ,{\mathbf{v}}_k\in X$ so that $\Vert \mathbf{z}-\frac{1}{k}{\sum }_{i=1}^k{\mathbf{v}}_i{\Vert }_Q$ is minimized. Maurey showed that if both $P$ and $Q$ coincide with the $\Vert \cdot {\Vert }_p$-ball, then an error of $O(\sqrt{p/k})$ is possible. We prove a reduction to the vector balancing constant from discrepancy theory which for most cases can provide tight bounds for general $P$ and $Q$. For the case where $P$ and $Q$ are both $\Vert \cdot {\Vert }_p$-balls we prove an upper bound of $\sqrt{\frac{\min \{p,\log (\frac{2m}{k})\}}{k}}$. Interestingly, this bound cannot be obtained taking independent random samples; instead we use the Lovett-Meka random walk. We also prove an extension to the more general case where $P$ and $Q$ are $\Vert \cdot {\Vert }_p$ and $\Vert \cdot {\Vert }_q$-balls with $2\le p\le q\le \infty$.

arXiv comment16 pages