Learning Feature Nonlinearities with Non-Convex Regularized Binned Regression
This work addresses the need for efficient nonlinear modeling in large-scale applications, offering a statistically and computationally efficient alternative to neural networks and regression trees, though it is incremental in nature.
The paper tackles the problem of learning feature nonlinearities in regression by proposing a method that bins feature values and applies non-convex regularized linear regression within quantiles, achieving competitive performance with state-of-the-art methods on synthetic and real datasets.
For various applications, the relations between the dependent and independent variables are highly nonlinear. Consequently, for large scale complex problems, neural networks and regression trees are commonly preferred over linear models such as Lasso. This work proposes learning the feature nonlinearities by binning feature values and finding the best fit in each quantile using non-convex regularized linear regression. The algorithm first captures the dependence between neighboring quantiles by enforcing smoothness via piecewise-constant/linear approximation and then selects a sparse subset of good features. We prove that the proposed algorithm is statistically and computationally efficient. In particular, it achieves linear rate of convergence while requiring near-minimal number of samples. Evaluations on synthetic and real datasets demonstrate that algorithm is competitive with current state-of-the-art and accurately learns feature nonlinearities. Finally, we explore an interesting connection between the binning stage of our algorithm and sparse Johnson-Lindenstrauss matrices.