  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.
