Learning Feature Nonlinearities with Non-Convex Regularized Binned Regression

Recently, substantial progress has been made on the problem of high-dimensional sparse linear models [22]. In particular, Lasso has been shown to be remarkably successful, and is statistically well-behaved and generates interpretable solutions. However, in the presence of non-linearity (i.e., the relation between the covariates and response is nonlinear), boosted decision trees, deep learning models, and kernel methods are regarded as the most effective models that deliver substantial performance boost over linear models; however, their interpretability is limited. As a result, there is a significant gap between the statistical performance and the interpretability, and it is often desirable to have computationally efficient algorithms that learn interpretable models without sacrificing statistical guarantees. This raises a natural question that we aim to tackle: Is there any algorithm which has similar statistical performance to complex models, while still retaining much of the interpretability of Lasso? In this paper, we answer the above question affirmatively and propose a novel way of learning the feature non-linearities with provable statistical and computational guarantees.