Approximate Carath\'eodory bounds via Discrepancy Theory

arXiv2207.03614MaRDI QIDQ6404344FDOQ6404344

Publication date: 7 July 2022

Abstract: The approximate Carath'eodory problem in general form is as follows: Given two symmetric convex bodies

P, Q s u b s e t e q m a t h b b R^{m}

, a parameter

k i n m a t h b b N

and

m a t h b f z i n e x t r m c o n v (X)

with

X s u b s e t e q P

, find

m a t h b f v_{1}, l d o t s, m a t h b f v_{k} i n X

so that

| m a t h b f z - f r a c 1 k s u m_{i = 1}^{k} m a t h b f v_{i} |_{Q}

is minimized. Maurey showed that if both

P

and

Q

coincide with the

| c d o t |_{p}

-ball, then an error of

O (s q r t 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

| c d o t |_{p}

-balls we prove an upper bound of

s q r t f r a c m i n p, l o g (f r a c 2 m 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

| c d o t |_{p}

and

| c d o t |_{q}

-balls with

2 l e q p l e q q l e q i n f t y

.

This page was built for publication: Approximate Carath\'eodory bounds via Discrepancy Theory

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6404344)