Sparse Convex Regression

We consider the problem of best k-subset convex regression using n observations in d 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 (n,d) = (10(4),10) in minutes and (n,d) = (10(5) ,10(2)) in hours. Our algorithm can be adapted to solve variants such as finding the best convex or concave functions with coordinate-wise monotonicity, norm-bounded subgradients, and minimize the l(1) loss-all with similar scalability to the least squares convex regression problem. Under sparsity, we propose algorithms which iteratively solve for the best subset of features based on first order and cutting plane methods. We show that our methods scale for sizes (n,d,k = 10(4),10(2) ,10) in minutes and (n,d, k = 10(5),10(2),10) in hours. We demonstrate that these methods control for the false discovery rate effectively.

Automated summary

The study addresses the problem of best k-subset convex regression using n observations in d variables, presenting scalable algorithms for both sparse and non-sparse cases. The algorithms show promising results when compared to state-of-the-art methods, providing high-quality solutions in practical times. Additionally, the methods are effective in controlling the false discovery rate.