Principal Component Hierarchy for Sparse Quadratic Programs
This provides a more efficient method for sparse regression problems, though it appears incremental relative to existing screening techniques.
The authors tackled the problem of solving cardinality-constrained convex quadratic programs by proposing a novel approximation hierarchy based on principal components, which enables efficient screening of nonzero elements. They developed two scalable algorithms that are competitive with existing methods, showing particular speed advantages on datasets with many measurements.
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.