High-Dimensional Cost-constrained Regression Via Nonconvex Optimization

Abstract

Budget constraints become an important consideration in modern predictive modeling due to the high cost of collecting certain predictors. This motivates us to develop cost-constrained predictive modeling methods. In this article, we study a new high-dimensional cost-constrained linear regression problem, that is, we aim to find the cost-constrained regression model with the smallest expected prediction error among all models satisfying a budget constraint. The nonconvex budget constraint makes this problem NP-hard. In order to estimate the regression coefficient vector of the cost-constrained regression model, we propose a new discrete first-order continuous optimization method. In particular, our method delivers a series of estimates of the regression coefficient vector by solving a sequence of 0-1 knapsack problems. Theoretically, we prove that the series of the estimates generated by our iterative algorithm converge to a first-order stationary point, which can be a globally optimal solution under some conditions. Furthermore, we study some extensions of our method that can be used for general statistical learning problems and problems with groups of variables. Numerical studies using simulated datasets and a real dataset from a diabetes study indicate that our proposed method can solve problems of fairly high dimensions with promising performance.

KEYWORDS:

• Budget constraint
• Dynamic programming
• High-dimensional regression
• Nonconvex optimization
• 0-1 knapsack problem

Supplementary Materials

Supplementary file: All proofs and the comparison of the computational time of different methods are shown in this file. (pdf)

R codes: R codes for all the simulation examples and the diabetes study. (ZIP archive)

Funding

This research was supported in part by NSF grant DMS-1821231 and NIH grant R01GM126550.