スパース最大アフィン回帰
なぜ重要か: 企業や社会への影響が見込まれ、一般メディアにも波及する可能性があります。
arXiv:2411.02225v2は、凸区分線形回帰における変数選択のための解法としてSparse Gradient Descent (Sp-GD)を提案する。モデルはk個のアフィン関数$x \mapsto \max_{j \in [k]} \langle a_j^\star, x \rangle + b_j^\star$ (j = 1,…,k)の最大値として与えられる。ここで、$\{ a_j^\star\}_{j=1}^k$と$\{b_j^\star\}_{j=1}^k$は真の重みベクトルと切片を表す。共変量分布が準ガウス性と反集積性を満たす場合、準ガウスノイズ下でのSp-GDの非漸近局所収束解析を示す。モデル次数とパラメータが固定されている場合、Sp-GDは$\mathcal{O}(\max(\epsilon^{-2}\sigma_z^2,1)s\log(d/s))$個の観測値を用いて$\epsilon$-精度推定を与える。これは、ノイズのない観測値$\mathcal{O}(s\log(d/s))$個からSp-GDによる正確なパラメータ復元も意味する。提案する初期化スキームは、Sparse Principal Component Analysisを用いて$\{ a_j^\star\}_{j=1}^k$によって張られる部分空間を推定し、その後r-covering searchを用いてモデルパラメータを推定する。共変量とノイズサンプルがガウス分布に従う場合、この初期化スキームの非漸近解析を示す。モデル次数とパラメータが固定されている場合、この初期化スキームは$\mathcal{O}(\epsilon^{-2}\max(\sigma_z^4,\sigma_z^2,1)s^2\log^4(d))$個の観測値を用いて$\epsilon$-精度推定を与える。スパース一般化多項式をスパースmax-affineモデルに変換するための新しい変換であるReal Maslov Dequantization (RMD)を提案する。RMDの誤差減衰速度は、その温度パラメータに関して指数的に小さいことが示される。さらに、Sp-GDの理論的保証をRMDによって誘起される有界ノイズモデルに拡張する。数値モンテカルロ結果は、Sp-GDと初期化スキームに関する理論的知見を裏付ける。
原文（英語）を表示
Title (EN): Sparse Max-Affine Regression
arXiv:2411.02225v2 Announce Type: replace-cross
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 $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 $\epsilon$-accurate estimate given $\mathcal{O}(\max(\epsilon^{-2}\sigma_z^2,1)s\log(d/s))$ observations where $\sigma_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 $\epsilon$-accurate estimate given $\mathcal{O}(\epsilon^{-2}\max(\sigma_z^4,\sigma_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.
Published: 2025-09-24 19:00 UTC