# Approximation Bounds for Sparse Programs

arXiv: https://arxiv.org/abs/2102.06742 · HTML: https://mlsanity.com/paper/2102.06742/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 12 Feb 2021.

## Built on by (most cited first, 2 of 2)

- [Sparse Plus Low Rank Matrix Decomposition: A Discrete Optimization Approach](https://mlsanity.com/paper/2109.12701/) (2021)
- [On the Partial Convexification for Low-Rank Spectral Optimization: Rank Bounds and Algorithms](https://mlsanity.com/paper/2305.07638/) (2023)

## Abstract (arXiv)

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, which means in particular that the relaxation is nearly tight as soon as the target cardinality is large enough so that only uninformative features are added.