Sparse high-dimensional regression: exact scalable algorithms and phase transitions (Q2176621)

This paper proposes a novel binary convex reformulation of the sparse regression problem. A new cutting plane method is devised to exactly solve the problem. Evidence is provided that the cutting plane algorithm fast scales to provable optimality for sample sizes \(n\) and number of regressors \(p\) in the 100,000s. A new phase transition is found in the ability to recover the true coefficients of the sparse regression problem and also in the ability to solve it. An extension of the sparse linear regression to the case of nonlinear regression by augmenting the input data \(X\) with auxiliary nonlinear transformations is also discussed.