Sparse Convex Regression

We consider the problem of best [Formula: see text]-subset convex regression using [Formula: see text] observations in [Formula: see text] variables. For the case without sparsity, we develop a scalable algorithm for obtaining high quality solutions in practical times that compare favorably with other state of the art methods. We show that by using a cutting plane method, the least squares convex regression problem can be solved for sizes...