ORIE Colloquium: Alexandre d'Aspremont (École Normale Supérieure) - Sparsity, Feature Selection and the Shapley Folkman 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 simple and explicit approximation bounds on a broad class of combinatorial optimization problems. We use these results to show that several classical sparsity constrained optimization problems in e.g. feature selection have low duality gaps in meaningful data settings.
After dual PhDs from École Polytechnique and Stanford University in optimization and finance, followed by a postdoc at U.C. Berkeley, Alexandre d’Aspremont joined the faculty at Princeton University as an assistant then associate professor. He returned to Europe in 2011 and is now a research director at CNRS, attached to École Normale Supérieure in Paris. He received the SIAM Optimization prize, an NSF CAREER award, and an ERC starting grant. He co-founded and is the scientific director of the MASH Msc degree at PSL. He also co-founded Kayrros SAS, which focuses on energy markets and earth observation.