Department of Mathematics

Applied Mathematics

  •  Alexandre d'Aspremont, École Normale Supérieure
  •  Approximation Bounds for Sparse Programs
  •  03/24/2022
  •  4:30 AM - 5:30 AM
  •  Online (virtual meeting) (Virtual Meeting Link)
  •  Olga Turanova (

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 bounds on the duality gap, and an efficient primalization procedure to recover feasible points satisfying these bounds. These error bounds are proportional to the rate of growth of the objective with the target cardinality k, which means in particular that the relaxation is nearly tight as soon as k is large enough so that only uninformative features are added.



Department of Mathematics
Michigan State University
619 Red Cedar Road
C212 Wells Hall
East Lansing, MI 48824

Phone: (517) 353-0844
Fax: (517) 432-1562

College of Natural Science