Approximate Carathéodory bounds via Discrepancy Theory
share
The approximate Carathéodory problem in general form is as follows: Given two symmetric convex bodies P,Q ⊆ℝ^m, a parameter k and 𝐳∈conv(X) with X ⊆ P, find 𝐯_1,…,𝐯_k ∈ X so that 𝐳 - 1/k∑_i=1^k 𝐯_i_Q is minimized. Maurey showed that if both P and Q coincide with the ·_p-ball, then an error of O(√(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 ·_p-balls we prove an upper bound of √(min{ p, log (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 ·_p and ·_q-balls with 2 ≤ p ≤ q ≤∞.
READ FULL TEXT