Abstract
本論文は、凸な区分線形回帰における変数選択のための解として、スパース勾配降下法（Sparse Gradient Descent; Sp-GD）を提案する。ここでモデルは、k個のアフィン関数の最大値として与えられ、x \mapsto \max_{j \in [k]} \langle a_j^\star, x \rangle + b_j^\star（j = 1,\dots,k）である。ここで、\{ a_j^\star\}_{j=1}^k と \{b_j^\star\}_{j=1}^k は、真の重みベクトルと切片を表す。共変量分布がサブガウス性および反集中（anti-concentration）性を満たすとき、サブガウスノイズのもとでSp-GDに対する非漸近的な局所収束解析を与える。モデル次数とパラメータが固定されている場合、Sp-GDは、ノイズ分散を \sigma_z^2 とすると、\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-被覆（r-covering）探索によりモデルパラメータを推定する。この初期化スキームに対して、共変量とノイズ標本がガウス分布に従うと仮定した場合の非漸近的解析を提示する。モデル次数とパラメータが固定されている場合、この初期化スキームは、\mathcal{O}(\epsilon^{-2}\max(\sigma_z^4,\sigma_z^2,1)s^2\log^4(d)) 個の観測により \epsilon 精度の推定を提供する。RMD（Real Maslov Dequantization：実マスロフ脱量子化）と名付けられた新しい変換を提案し、疎な一般化多項式を疎な max-アフィン（max-affine）モデルへ変換する。RMDの誤差減衰率は、その温度パラメータに関して指数的に小さいことが示される。さらに、RMDによって誘起される有界ノイズモデルに対して、Sp-GDの理論的保証を拡張する。数値的なモンテカルロ結果は、Sp-GDおよび初期化スキームに関する理論的知見を裏付ける。
