  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.

Optimization and Control;Machine Learning;Machine Learning