Approximation Bounds for Sparse Programs

DOI10.1137/21M1398677zbMATH Open1493.62092arXiv2102.06742OpenAlexW3131933343MaRDI QIDQ5073726FDOQ5073726

Author name not available (Why is that?)

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

zbMATH Keywords

sparsityconvex relaxationduality gapShapley-Folkman theorem

Mathematics Subject Classification ID

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?)
• 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
• 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

• Scikit
• boost

Recommendations

• Title not available (Why is that?) 👍 👎
• Sparse Approximate Solutions to Semidefinite Programs 👍 👎
• Approximability of sparse integer programs 👍 👎
• Sparse Approximation by Greedy Algorithms 👍 👎
• Approximability of Sparse Integer Programs 👍 👎
• Computing sparse approximations deterministically 👍 👎
• On the Complexity of Solving Sparse Symmetric Linear Programs Specified with Approximate Data 👍 👎
• Sparsification and subexponential approximation 👍 👎
• On Approximating (Sparse) Covering Integer Programs 👍 👎
• A note on the hardness of sparse approximation 👍 👎

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)