# Principal Component Hierarchy for Sparse Quadratic Programs

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 17 of its 71 references that are in the map.
- First posted on arXiv 25 May 2021.

## Builds on (most cited first, 17 of 17)

- ["Why Should I Trust You?": Explaining the Predictions of Any Classifier](https://mlsanity.com/paper/1602.04938/) (2016)
- [Best Subset Selection via a Modern Optimization Lens](https://mlsanity.com/paper/1507.03133/) (2015)
- [Low-rank Solutions of Linear Matrix Equations via Procrustes Flow](https://mlsanity.com/paper/1507.03566/) (2015)
- [Sparse Regression at Scale: Branch-and-Bound rooted in First-Order Optimization](https://mlsanity.com/paper/2004.06152/) (2020)
- [Sparse High-Dimensional Regression: Exact Scalable Algorithms and Phase Transitions](https://mlsanity.com/paper/1709.10029/) (2017)
- [Learning Sparse Classifiers: Continuous and Mixed Integer Optimization Perspectives](https://mlsanity.com/paper/2001.06471/) (2020)
- [A unified approach to mixed-integer optimization problems with logical constraints](https://mlsanity.com/paper/1907.02109/) (2019)
- [Subset Selection with Shrinkage: Sparse Linear Modeling when the SNR is low](https://mlsanity.com/paper/1708.03288/) (2017)
- [Extended Comparisons of Best Subset Selection, Forward Stepwise Selection, and the Lasso](https://mlsanity.com/paper/1707.08692/) (2017)
- [Solving Large-Scale Sparse PCA to Certifiable (Near) Optimality](https://mlsanity.com/paper/2005.05195/) (2020)
- [A Scalable Algorithm For Sparse Portfolio Selection](https://mlsanity.com/paper/1811.00138/) (2018)
- [The Trimmed Lasso: Sparsity and Robustness](https://mlsanity.com/paper/1708.04527/) (2017)
- [Safe Screening Rules for ℓ0-Regression](https://mlsanity.com/paper/2004.08773/) (2020)
- [A Block Decomposition Algorithm for Sparse Optimization](https://mlsanity.com/paper/1905.11031/) (2019)
- [Interpretable Matrix Completion: A Discrete Optimization Approach](https://mlsanity.com/paper/1812.06647/) (2018)
- [Noisy Inductive Matrix Completion Under Sparse Factor Models](https://mlsanity.com/paper/1609.03958/) (2016)
- [Sparse Group Inductive Matrix Completion](https://mlsanity.com/paper/1804.10653/) (2018)

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

- [Feasible Recourse Plan via Diverse Interpolation](https://mlsanity.com/paper/2302.11213/) (2023)

## Abstract (arXiv)

We propose a novel approximation hierarchy for cardinality-constrained, convex quadratic programs that exploits the rank-dominating eigenvectors of the quadratic matrix. Each level of approximation admits a min-max characterization whose objective function can be optimized over the binary variables analytically, while preserving convexity in the continuous variables. Exploiting this property, we propose two scalable optimization algorithms, coined as the "best response" and the "dual program", that can efficiently screen the potential indices of the nonzero elements of the original program. We show that the proposed methods are competitive with the existing screening methods in the current sparse regression literature, and it is particularly fast on instances with high number of measurements in experiments with both synthetic and real datasets.