Sparse Max-Affine Regression

Abstract

Abstract. This paper presents sparse gradient descent as a solution for variable selection in convex piecewise linear regression where the model is given as the maximum of [Formula: see text]-affine functions [Formula: see text] for [Formula: see text]. Here, [Formula: see text] and [Formula: see text] denote the ground-truth weight vectors and intercepts. A nonasymptotic local convergence analysis is provided for Sp-GD under sub-Gaussian noise when the covariate distribution satisfies the sub-Gaussianity and anticoncentration properties. When the model order and parameters are fixed, Sp-GD provides an [Formula: see text]-accurate estimate given [Formula: see text] observations, where [Formula: see text] denotes the noise variance. This also implies the exact parameter recovery by Sp-GD from [Formula: see text] noise-free observations. Since optimizing the squared loss for sparse max-affine is nonconvex, an initialization scheme is proposed to provide a suitable initial estimate within the basin of attraction for Sp-GD, i.e., sufficiently accurate to invoke the convergence guarantees. The initialization scheme uses sparse principal component analysis to estimate the subspace spanned by [Formula: see text], then applies an [Formula: see text]-covering search to estimate the model parameters. A nonasymptotic analysis is presented for this initialization scheme when the covariates and noise samples follow Gaussian distributions. When the model order and parameters are fixed, this initialization scheme provides an [Formula: see text]-accurate estimate given [Formula: see text] observations. A new transformation named Real Maslov Dequantization (RMD) is proposed to transform sparse generalized polynomials into sparse max-affine models. The error decay rate of RMD is shown to be exponentially small in its temperature parameter. Furthermore, theoretical guarantees for Sp-GD are extended to the bounded noise model induced by RMD. Numerical Monte Carlo results corroborate theoretical findings for Sp-GD and the initialization scheme.