Approximation Bounds for Sparse Programs

Armin Askari, Alexandre d'Aspremont, Laurent El Ghaoui

We show that sparsity constrained optimization problems over low dimensional spaces tend to have a small duality gap. We use the Shapley-Folkman theorem to derive both data-driven…