Some Greedy Algorithms for Sparse Nonlinear Regression

Abstract

We present deterministic greedy algorithms for building sparse nonlinear regression models from observational data. Our objective is to develop ecient numerical schemes for reducing the training and runtime complexities of nonlinear regression techniques applied to massive datasets. In the spirit of Natarajan's greedy algorithm (Natarajan, 1995), we iteratively minimize a loss function subject to a speci ed constraint on the degree of sparsity required of the nal model or an upper bound on the empirical error. We discuss various greedy criteria for basis selection and numerical schemes for improving the robustness and computational eciency. Subsequently, algorithms based on residual minimization and thin incremental QR factorization updating are presented for constructing sparse regularization networks. Experimental results on some benchmark problems are presented to demonstrate the competitiveness of the algorithms developed in this paper. 1.