Approximate Carathéodory bounds via Discrepancy Theory

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 $\mathrm{\parallel }\mathbf{z}-\frac{1}{k}{\sum }_{i=1}^k{\mathbf{v}}_i{\mathrm{\parallel }}_Q$ is minimized. Maurey showed that if both $P$ and $Q$ coincide with the $\mathrm{\parallel }\cdot {\mathrm{\parallel }}_p$-ball, then an error of $O(\sqrt{p\mathrm{/}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 $\mathrm{\parallel }\cdot {\mathrm{\parallel }}_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 $\mathrm{\parallel }\cdot {\mathrm{\parallel }}_p$ and $\mathrm{\parallel }\cdot {\mathrm{\parallel }}_q$-balls with $2\le p\le q\le \mathrm{\infty }$.