Alexandre d’Aspremont, ENS/INRIA, le 4 décembre 2020

Sparsity, Feature Selection & the Shapley-Folkman Theorem
mardi 1er décembre 2020
par  Alain Celisse

The Shapley Folkman theorem acts 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