Sparsity, Feature Selection and the ShapleyFolkman Theorem

The Shapley Folkman theorem acts as a central limit theorem for convexity: It shows that Minkowski sums of arbitrary bounded sets are increasingly close to their convex hull as the number of terms in the sum increases. This produces a priori bounds on the duality gap of separable optimization problems. We use these results to show that several classical sparsity constrained optimization problems have low duality gaps in meaningful data settings.