Principal Component Hierarchy for Sparse Quadratic Programs

Principal Component Hierarchy for Sparse Quadratic Programs

Authors: Robbie Vreugdenhil, Viet Anh Nguyen, Armin Eftekhari, Peyman Mohajerin Esfahani

ICML 2021 - to appear


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.

title = “Principal Component Hierarchy for Sparse Quadratic Programs”,
author = {Robbie Vreugdenhil and Viet Anh Nguyen and Armin Eftekhari and Peyman Mohajerin Esfahani},
booktitle= {Proceedings of the 38th International Conference on Machine Learning},
year = {2021}