We present a novel binary convex reformulation of the sparse regression
problem that constitutes a new duality perspective. We devise a new cutting
plane method and provide evidence that it can solve to provable optimality the
sparse regression problem for sample sizes n and number of regressors p in the
100,000s, that is two orders of magnitude better than the current state of the
art, in seconds. The ability to solve the problem for very high dimensions
allows us to observe new phase transition phenomena. Contrary to traditional
complexity theory which suggests that the difficulty of a problem increases
with problem size, the sparse regression problem has the property that as the
number of samples $n$ increases the problem becomes easier in that the solution
recovers 100% of the true signal, and our approach solves the problem extremely
fast (in fact faster than Lasso), while for small number of samples n, our
approach takes a larger amount of time to solve the problem, but importantly
the optimal solution provides a statistically more relevant regressor. We argue
that our exact sparse regression approach presents a superior alternative over
heuristic methods available at present.

本文提出了一种新的二元凸重构稀疏回归问题的方法，并提供了一种新的切平面方法来解决高维数据时出现的问题。实验证明，与当前最先进的算法相比，本方法能够在秒内解决样本数和回归器数均在 10 万个数量级的稀疏回归问题，并且可以观察到新的相变现象。