Approximation Bounds for Sparse Programs
From MaRDI portal
Publication:5073726
DOI10.1137/21M1398677zbMATH Open1493.62092arXiv2102.06742OpenAlexW3131933343MaRDI QIDQ5073726FDOQ5073726
Authors:
Publication date: 3 May 2022
Published in: SIAM Journal on Mathematics of Data Science (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/2102.06742
Recommendations
- Approximability of Sparse Integer Programs
- Approximability of sparse integer programs
- Approximation hardness for a class of sparse optimization problems
- Sparse Approximate Solutions to Semidefinite Programs
- Sparse approximation by greedy algorithms
- Sparsification and subexponential approximation
- Computing sparse approximations deterministically
- A note on the hardness of sparse approximation
- On the Complexity of Solving Sparse Symmetric Linear Programs Specified with Approximate Data
- On approximating (sparse) covering integer programs
Convex programming (90C25) Statistical ranking and selection procedures (62F07) Approximation methods and heuristics in mathematical programming (90C59) Asymptotic theory of convex bodies (52A23)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Decoding by Linear Programming
- Why Are Big Data Matrices Approximately Low Rank?
- Perspective cuts for a class of convex 0-1 mixed integer programs
- Title not available (Why is that?)
- Estimates of the Duality Gap in Nonconvex Optimization
- Sparse Approximate Solutions to Linear Systems
- On general minimax theorems
- A Continuous Exact $\ell_0$ Penalty (CEL0) for Least Squares Regularized Problem
- Bounding duality gap for separable problems with linear constraints
- Quasi-Equilibria in Markets with Non-Convex Preferences
- Optimal cardinality constrained portfolio selection
- A semidefinite programming method for integer convex quadratic minimization
- On the Convexification of Constrained Quadratic Optimization Problems with Indicator Variables
- Sparse learning via Boolean relaxations
Cited In (6)
- Phase transitions for greedy sparse approximation algorithms
- Design Strategies for ARX with Provable Bounds: Sparx and LAX
- Sparse semidefinite programs with guaranteed near-linear time complexity via dualized clique tree conversion
- Parameterized complexity of sparse linear complementarity problems
- \(\ell_1\)-sparsity approximation bounds for packing integer programs
- Exact Sparse Approximation Problems via Mixed-Integer Programming: Formulations and Computational Performance
Uses Software
This page was built for publication: Approximation Bounds for Sparse Programs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5073726)
