Sparse Convex Regression

Dimitris Bertsimas () and Nishanth Mundru ()
Additional contact information
Dimitris Bertsimas: Sloan School of Management and Operations Research Center, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139;
Nishanth Mundru: Kenan-Flagler Business School, University of North Carolina at Chapel Hill, Chapel Hill, North Carolina 27599

INFORMS Journal on Computing, 2021, vol. 33, issue 1, 262-279

Abstract: 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 , 1 0 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 ℓ 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 , 1 0 2 , 10 ) in minutes and ( n , d , k = 10 5 , 1 0 2 , 10 ) in hours. We demonstrate that these methods control for the false discovery rate effectively.

Keywords: statistics; regression; linear programming; large-scale systems; applications (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (4)

Downloads: (external link)
https://doi.org/10.1287/ijoc.2020.0954 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:orijoc:v:33:y:2021:i:1:p:262-279

Access Statistics for this article

More articles in INFORMS Journal on Computing from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().