提出稀疏梯度下降法，高效求解分段线性回归的变量选择问题。
Sparse Max-Affine Regression
- 用稀疏梯度下降实现分段线性模型的变量选择与参数估计。
- 在噪声条件下仅需 $\mathcal{O}(s\log(d/s))$ 样本即可精确恢复参数。
- 适用于高维稀疏场景，适合机器学习中的结构化回归任务。
本文提出稀疏梯度下降（Sp-GD）用于解决凸分段线性回归中的变量选择问题，模型形式为 $ x \mapsto \max_{j \in [k]} \langle a_j^\star, x \rangle + b_j^\star $，其中 $\{a_j^\star\}$ 和 $\{b_j^\star\}$ 为真实权重与截距。在子高斯噪声下，若协变量分布满足子高斯性和反集中性质，Sp-GD 的非渐近局部收敛分析表明：当模型阶数和参数固定时，只需 $\mathcal{O}(\max(\varepsilon^{-2}\sigma_z^2,1)s\log(d/s))$ 个样本即可获得 $\varepsilon$-精度估计，且在无噪声情况下可实现参数精确恢复。所提初始化方案基于稀疏主成分分析估计 $\{a_j^\star\}$ 张成的子空间，并结合 $r$-覆盖搜索估计参数，在高斯分布假设下，保证 $\varepsilon$-精度估计所需样本数为 $\mathcal{O}(\varepsilon^{-2}\max(\sigma_z^4,\sigma_z^2,1)s^2\log^4(d))$。进一步提出实马斯洛德量子化（RMD）变换，将稀疏广义多项式转化为稀疏最大仿射模型，其误差随温度参数呈指数衰减。理论结果还扩展至由 RMD 诱导的有界噪声模型。蒙特卡洛实验验证了 Sp-GD 及初始化方案的理论性能。
原文摘要 · Abstract (English)
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 \mapsto \max_{j \in [k]} \langle a_j^\star, x \rangle + b_j^\star$ for $j = 1,\dots,k$. Here, $\{ a_j^\star\}_{j=1}^k$ and $\{b_j^\star\}_{j=1}^k$ 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 $\mathcal{O}(\max(ε^{-2}σ_z^2,1)s\log(d/s))$ observations where $σ_z^2$ denotes the noise variance. This also implies the exact parameter recovery by Sp-GD from $\mathcal{O}(s\log(d/s))$ noise-free observations. The proposed initialization scheme uses sparse principal component analysis to estimate the subspace spanned by $\{ a_j^\star\}_{j=1}^k$, 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 $\mathcal{O}(ε^{-2}\max(σ_z^4,σ_z^2,1)s^2\log^4(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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。