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