Approximation Bounds for Sparse Programs

2021/02/12 by Armin Askari, Askari, Armin, Alexandre d’Aspremont +3 · 1 citation
Decision Sciences · Mathematics · #Advanced Bandit Algorithms Research #Advanced Optimization Algorithms Research #FOS: Mathematics #Optimization and Control (math.OC) #Risk and Portfolio Optimization

paper · doi:10.48550/arxiv.2102.06742

openalex publication_date 2021/02/12 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

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.

Cited by

• AoI-Energy-Spectrum Optimization in Post-Disaster Powered Communication Intelligent Network via Hierarchical Heterogeneous Graph Neural Network

Related

• Lower Bound Convex Programs for Exact Sparse Optimization
• Improving proximity bounds using sparsity
• Optimization over Sparse Support-Preserving Sets: Two-Step Projection with Global Optimality Guarantees
• Lp Quasi-norm Minimization: Algorithm and Applications
• Some lower bounds on sparse outer approximations of polytopes