2022/07/07 by Reis, Victor, Rothvoss, Thomas
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Metric Geometry (math.MG)
paper · doi:10.48550/arxiv.2207.03614
The approximate Carathéodory problem in general form is as follows: Given two symmetric convex bodies P,Q ⊆ ℝm, a parameter k ∈ ℕ and z ∈ \textrmconv(X) with X ⊆ P, find v1,…,vk ∈ X so that ‖z - (1)/(k)∑i=1k vi‖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 √ \fracmin\ 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 ≤ ∞.