An Approximate Shapley-Folkman Theorem.

TITLE: An Approximate Shapley-Folkman Theorem.

AUTHORS: Alexandre d'Aspremont, Igor Colin

ABSTRACT: The Shapley-Folkman theorem shows that Minkowski averages of uniformly bounded sets tend to be convex when the number of terms in the sum becomes much larger than the ambient dimension. In optimization, this produces a priori bounds on the duality gap of separable nonconvex optimization problems involving finite sums. We show an approximate version of this result with weaker dependence on the problem's nonconvexity. This result hinges on a new version of Maurey's classical approximate Carath'eodory lemma where we sample a significant fraction of the coefficients, without replacement.

STATUS: Preprint.

ArXiv PREPRINT: 1712.08559