2024/11/04 by H. Kanj, Kanj, Haitham, Seonho Kim +3
Computer Science · Mathematics · #FOS: Computer and information sciences #FOS: Mathematics #Face and Expression Recognition #Information Theory (cs.IT) #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Statistical Methods and Inference #Statistics Theory (math.ST)
paper · pdf · doi:10.48550/arxiv.2411.02225
openalex publication_date 2024/11/04 · openalex created_date 2024/11/15 · openalex updated_date 2026/07/28
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 k-affine functions x ↦ maxj ∈ [k] ⟨ aj^⋆, x ⟩ + bj^⋆ for j = 1,…,k. Here, \ aj^⋆\j=1k and \bj^⋆\j=1k denote the ground-truth weight vectors and intercepts. A non-asymptotic local convergence analysis is provided for Sp-GD under sub-Gaussian noise when the covariate distribution satisfies the sub-Gaussianity and anti-concentration properties. When the model order and parameters are fixed, Sp-GD provides an ε-accurate estimate given O(max(ε-2σz2,1)slog(d/s)) observations where σz2 denotes the noise variance. This also implies the exact parameter recovery by Sp-GD from O(slog(d/s)) noise-free observations. The proposed initialization scheme uses sparse principal component analysis to estimate the subspace spanned by \ aj^⋆\j=1k, then applies an r-covering search to estimate the model parameters. A non-asymptotic 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 ε-accurate estimate given O(ε-2max(σz4,σz2,1)s2log4(d)) 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.