正則化（Regularization）は学習問題の過学習を抑制し汎化性能を高める枠組みであり、 スパース推定（Sparse Estimation）は高次元設定において真にゼロでない パラメータを少数に限定するという構造的仮定のもとで推定を行う統計的理論である。 本節では正則化の統計的・最適化的解釈を整理したうえで、 $\ell_1$ 正則化を中心とするスパース推定の理論（Lasso・圧縮センシング）を 体系的に展開する。
入力行列 $X = (\boldsymbol{x}_1, \ldots, \boldsymbol{x}_n)^\top \in \mathbb{R}^{n \times d}$、 応答ベクトル $\boldsymbol{y} = (y_1, \ldots, y_n)^\top \in \mathbb{R}^n$、 パラメータ $\boldsymbol{\beta} \in \mathbb{R}^d$ を考える。 線形モデル
\[ \boldsymbol{y} = X\boldsymbol{\beta}^* + \boldsymbol{\varepsilon}, \quad \boldsymbol{\varepsilon} \sim \mathcal{N}(\boldsymbol{0}, \sigma^2 I_n)\]を基本設定とする（$\boldsymbol{\beta}^* \in \mathbb{R}^d$ が真のパラメータ）。 高次元設定では $d \gg n$ の場合も含む。 $\boldsymbol{\beta}^*$ が$s$-スパースであるとは、 $\|\boldsymbol{\beta}^*\|_0 = |\{j : \beta_j^* \neq 0\}| = s \ll d$ が成立することをいう。 真に非ゼロな添字集合をサポート $S = \mathrm{supp}(\boldsymbol{\beta}^*) = \{j : \beta_j^* \neq 0\}$ と呼ぶ（$|S| = s$）。
正則化なしの最小二乗推定（OLS）
\[ \hat{\boldsymbol{\beta}}^{\mathrm{OLS}} = \arg\min_{\boldsymbol{\beta}} \|\boldsymbol{y} - X\boldsymbol{\beta}\|^2 = (X^\top X)^{-1} X^\top \boldsymbol{y}\]は $d \leq n$ かつ $X^\top X$ が正則のとき一意解を持ち、 Gauss–Markov 定理より線形不偏推定量のうち最小分散を達成する（BLUE）。 しかし以下の場合に深刻な問題が生じる。
正則化付き推定問題の一般形は
\[ \hat{\boldsymbol{\beta}} = \arg\min_{\boldsymbol{\beta} \in \mathbb{R}^d} \left[ \mathcal{L}(\boldsymbol{\beta}; \mathcal{D}_n) + \lambda \Omega(\boldsymbol{\beta}) \right]\]と書ける。$\mathcal{L}$ は損失関数（経験リスク）、 $\Omega: \mathbb{R}^d \to \mathbb{R}_+$ は正則化項（ペナルティ）、 $\lambda > 0$ は正則化係数（ハイパーパラメータ）である。 $\lambda$ が大きいほど正則化が強く（バイアス増・バリアンス減）、 $\lambda \to 0$ で正則化なしの推定に近づく。 主要な正則化項の性質を以下に整理する。
| 正則化項 $\Omega(\boldsymbol{\beta})$ | 名称 | 解の特徴 | ベイズ事前分布 |
|---|---|---|---|
| $\|\boldsymbol{\beta}\|_2^2$ | Ridge（$\ell_2$） | 係数の縮小・一意解・スパースでない | ガウス事前分布 $\mathcal{N}(0, (2\lambda)^{-1}I)$ |
| $\|\boldsymbol{\beta}\|_1$ | Lasso（$\ell_1$） | スパース解・変数選択 | ラプラス事前分布 $\mathrm{Laplace}(0, (2\lambda)^{-1})$ |
| $\alpha\|\boldsymbol{\beta}\|_1 + (1-\alpha)\|\boldsymbol{\beta}\|_2^2$ | Elastic Net | スパース＋グループ化 | ガウス＋ラプラスの混合 |
| $\|\boldsymbol{\beta}\|_0$ | $\ell_0$（スパース制約） | 最適スパース解・NP 困難 | スパイク・スラブ事前分布 |
| $\|B\|_*$（核ノルム） | 核ノルム正則化 | 低ランク行列推定 | — |
Ridge 回帰（Hoerl–Kennard, 1970）は
\[ \hat{\boldsymbol{\beta}}^{\mathrm{Ridge}} = \arg\min_{\boldsymbol{\beta}} \left[ \|\boldsymbol{y} - X\boldsymbol{\beta}\|^2 + \lambda\|\boldsymbol{\beta}\|_2^2 \right]\]と定義される。目的関数は $\lambda > 0$ のとき強凸であり（前節）、 一意解が解析的に得られる：
\[ \hat{\boldsymbol{\beta}}^{\mathrm{Ridge}} = (X^\top X + \lambda I_d)^{-1} X^\top \boldsymbol{y}\]$\lambda I_d$ の加算により $X^\top X + \lambda I_d$ は常に正定値となり、 多重共線性・$d > n$ の設定でも一意解が存在する。
$X = U\Sigma V^\top$（SVD、$U \in \mathbb{R}^{n \times r}$、 $\Sigma = \mathrm{diag}(\sigma_1, \ldots, \sigma_r)$、 $V \in \mathbb{R}^{d \times r}$、$r = \mathrm{rank}(X)$）とおくと、
\[ \hat{\boldsymbol{\beta}}^{\mathrm{Ridge}} = V \mathrm{diag}\!\left(\frac{\sigma_j}{\sigma_j^2 + \lambda}\right) U^\top \boldsymbol{y}, \qquad \hat{\boldsymbol{\beta}}^{\mathrm{OLS}} = V \mathrm{diag}\!\left(\frac{1}{\sigma_j}\right) U^\top \boldsymbol{y}\]Ridge 推定量は OLS 推定量の各特異値方向の成分を $\sigma_j^2 / (\sigma_j^2 + \lambda) \in (0,1)$ 倍に縮小する。 小さな特異値 $\sigma_j \approx 0$ に対応する方向（不安定方向）が 強く抑制され、分散が低減される。
$\hat{\boldsymbol{\beta}}^{\mathrm{Ridge}}$ のバイアスとバリアンスは
\[ \mathrm{Bias}(\hat{\boldsymbol{\beta}}^{\mathrm{Ridge}}) = -\lambda(X^\top X + \lambda I)^{-1}\boldsymbol{\beta}^*, \qquad \mathrm{Var}(\hat{\boldsymbol{\beta}}^{\mathrm{Ridge}}) = \sigma^2 (X^\top X + \lambda I)^{-1} X^\top X (X^\top X + \lambda I)^{-1}\]と計算される。$\lambda$ の増加はバイアスを増大させる一方でバリアンスを低減し、 バイアス・バリアンストレードオフを制御する。 OLS は $\lambda = 0$ で不偏であるが高バリアンス、 Ridge は有偏だが低バリアンスであり、 適切な $\lambda > 0$ のもとで平均二乗誤差（MSE）が OLS を下回ることが保証される （Hoerl–Kennard 定理）。
Lasso（Least Absolute Shrinkage and Selection Operator；Tibshirani, 1996）は
\[ \hat{\boldsymbol{\beta}}^{\mathrm{Lasso}} = \arg\min_{\boldsymbol{\beta}} \left[ \frac{1}{2n}\|\boldsymbol{y} - X\boldsymbol{\beta}\|^2 + \lambda\|\boldsymbol{\beta}\|_1 \right]\]と定義される。$\|\boldsymbol{\beta}\|_1 = \sum_{j=1}^d |\beta_j|$ は凸だが $\boldsymbol{\beta} = \boldsymbol{0}$ で微分不可能であり、 前節の劣微分・近接写像の理論が本質的に必要となる。
Lasso は制約付き問題
\[ \min_{\boldsymbol{\beta}} \|\boldsymbol{y} - X\boldsymbol{\beta}\|^2 \quad \text{s.t.} \quad \|\boldsymbol{\beta}\|_1 \leq t\]と等価である（$\lambda$ と $t$ の間に一対一対応が存在）。 $\ell_1$ 球 $\{\boldsymbol{\beta} : \|\boldsymbol{\beta}\|_1 \leq t\}$ は $\mathbb{R}^d$ における多面体（正規形：菱形）であり、 その頂点（スパースな点）に解が引き寄せられやすい。 これに対して Ridge の $\ell_2$ 球は滑らかな球面であり、 軸上の頂点を持たないためスパース解が得られない。
より厳密には、最適解の KKT 条件（前節）は
\[ \frac{1}{n} X^\top(\boldsymbol{y} - X\hat{\boldsymbol{\beta}}) = \lambda \hat{\boldsymbol{z}}, \qquad \hat{z}_j \in \begin{cases} \{\mathrm{sign}(\hat{\beta}_j)\} & \hat{\beta}_j \neq 0 \\ [-1, 1] & \hat{\beta}_j = 0 \end{cases}\]と書ける。$j$ 番目の成分について、 $|[X^\top(\boldsymbol{y} - X\hat{\boldsymbol{\beta}})]_j| / n < \lambda$ のとき $\hat{\beta}_j = 0$ が強制される。 このソフト閾値処理（Soft Thresholding）の構造が Lasso のスパース性の根拠である。
Lasso の目的関数は $j$ 番目の座標方向に関して分離可能であるため、 座標降下法（Coordinate Descent）が効率的に適用できる。 他の座標 $\boldsymbol{\beta}_{-j}$ を固定して $\beta_j$ を最適化すると、 残差 $r_j = y_i - \sum_{k \neq j} x_{ik}\beta_k$ を用いて
\[ \hat{\beta}_j = \mathcal{S}_{\lambda n / \|X_j\|^2}\!\left( \frac{X_j^\top \boldsymbol{r}_j}{\|X_j\|^2} \right)\]と閉形式で得られる。ここでソフト閾値関数は
\[ \mathcal{S}_\tau(z) = \mathrm{sign}(z)\max(|z| - \tau, 0)\]であり、これは $\ell_1$ 正則化の近接写像（前節）そのものである。 座標降下法を全座標について繰り返す glmnet アルゴリズム（Friedman et al., 2010）は 大規模 Lasso 問題の標準的解法であり、$O(nd)$ の計算量で高速に収束する。
Lasso の理論的保証を与えるために、計画行列 $X$ に対する条件が必要となる。 最も広く用いられるのは制限固有値条件 （Restricted Eigenvalue Condition, REC；Bickel–Ritov–Tsybakov, 2009）である。
サポート $S$（$|S| = s$）と定数 $c_0 > 0$ に対して、 錐集合 $\mathcal{C}(S, c_0) = \{\boldsymbol{\delta} \in \mathbb{R}^d : \|\boldsymbol{\delta}_{S^c}\|_1 \leq c_0 \|\boldsymbol{\delta}_S\|_1\}$ において
\[ \kappa(s, c_0) = \min_{\boldsymbol{\delta} \in \mathcal{C}(S,c_0),\, \boldsymbol{\delta} \neq \boldsymbol{0}} \frac{\|X\boldsymbol{\delta}\|^2}{n\|\boldsymbol{\delta}_S\|^2} > 0\]が成立するとき、$X$ は RE 条件を満たすという。 RE 条件は多重共線性があっても $X$ のスパース方向への正定値性を保証し、 ランダム計画行列（ガウス行列等）では高確率で成立することが知られている。
定理（Lasso の $\ell_2$ 誤差上界）： $\boldsymbol{\varepsilon} \sim \mathcal{N}(\boldsymbol{0}, \sigma^2 I_n)$、 $X$ が RE 条件 $\kappa = \kappa(s, 3)$ を満たし、 正則化係数を
\[ \lambda \geq 2\sigma\sqrt{\frac{2\log(2d/\delta)}{n}}\]と選ぶとき、確率 $1-\delta$ 以上で
\[ \|\hat{\boldsymbol{\beta}}^{\mathrm{Lasso}} - \boldsymbol{\beta}^*\|_2^2 \leq \frac{16\lambda^2 s}{\kappa^2} = O\!\left(\frac{s\log d}{n}\right)\]が成立する。この $O(s\log d / n)$ という収束率は $s$ 個の非ゼロパラメータのみ推定する問題の ミニマックス最適レートに一致し、$d$ に対して対数的にしか依存しない。 OLS の $\ell_2$ 誤差が $O(d/n)$ であることと対比すると、 $s \ll d$ の高次元スパース設定での Lasso の優位性が明確である。
さらに $\ell_1$ 誤差と予測誤差についても同様の上界が成立する：
\[ \|\hat{\boldsymbol{\beta}}^{\mathrm{Lasso}} - \boldsymbol{\beta}^*\|_1 \leq \frac{4\lambda s}{\kappa^2} = O\!\left(s\sqrt{\frac{\log d}{n}}\right), \qquad \frac{1}{n}\|X(\hat{\boldsymbol{\beta}}^{\mathrm{Lasso}} - \boldsymbol{\beta}^*)\|^2 = O\!\left(\frac{s\log d}{n}\right)\]Lasso がサポート $S$ を確率 $1$ で正確に回復する（変数選択一致性）ための 条件としてアービン条件（Irrepresentability Condition；Zhao–Yu, 2006）がある：
\[ \left\| \frac{1}{n} X_{S^c}^\top X_S \left(\frac{1}{n} X_S^\top X_S\right)^{-1} \mathrm{sign}(\boldsymbol{\beta}_S^*) \right\|_\infty < 1\]これは「非サポート変数が、サポート変数によって $\ell_1$ 意味で 一に近い形で表現されない」という幾何学的条件である。 アービン条件は RE 条件より強く、 特にサポート変数と非サポート変数の相関が高い場合には満たされにくい。 アービン条件のもとで $\lambda = O(\sigma\sqrt{\log d / n})$ と選べば、 Lasso は確率収束の意味でサポートを完全に回復する。
Elastic Net（Zou–Hastie, 2005）は $\ell_1$ と $\ell_2$ の混合正則化として
\[ \hat{\boldsymbol{\beta}}^{\mathrm{EN}} = \arg\min_{\boldsymbol{\beta}} \left[ \frac{1}{2n}\|\boldsymbol{y} - X\boldsymbol{\beta}\|^2 + \lambda_1\|\boldsymbol{\beta}\|_1 + \lambda_2\|\boldsymbol{\beta}\|_2^2 \right]\]と定義される。Lasso の欠点（相関変数のうち一つしか選ばない傾向、 $d > n$ で選択できる変数が $n$ 個以下）を克服しつつスパース性を保持する。 $\lambda_2 > 0$ により目的関数は強凸となり一意解が保証される。 Elastic Net の解もソフト閾値処理の形で書け、 座標降下法が効率的に適用できる。
共変量に既知のグループ構造 $\{1,\ldots,d\} = G_1 \cup \cdots \cup G_K$ がある場合、 グループ Lasso（Yuan–Lin, 2006）は
\[ \hat{\boldsymbol{\beta}}^{\mathrm{GL}} = \arg\min_{\boldsymbol{\beta}} \left[ \frac{1}{2n}\|\boldsymbol{y} - X\boldsymbol{\beta}\|^2 + \lambda \sum_{k=1}^K \sqrt{|G_k|}\,\|\boldsymbol{\beta}_{G_k}\|_2 \right]\]と定義される。ペナルティ項はグループ単位のスパース性を誘導し、 グループ全体をゼロまたは非ゼロとして選択する。 $\sqrt{|G_k|}$ の係数はグループサイズの違いを補正する。 各グループ内の近接写像は $\ell_2$ ノルム版のソフト閾値処理 （ブロックソフト閾値）となる。
圧縮センシング（Compressed Sensing；Candès–Tao, Donoho, 2006）は、 $n \ll d$ の線形観測
\[ \boldsymbol{y} = X\boldsymbol{\beta}^* + \boldsymbol{\varepsilon}, \quad X \in \mathbb{R}^{n \times d},\quad n \ll d\]から $s$-スパースな $\boldsymbol{\beta}^*$ を回復する問題を扱う。 ナイキスト–シャノンの標本化定理を超える圧縮を、 スパース性という事前知識によって可能にする点が理論的に革新的である。
制限等長条件（Restricted Isometry Property, RIP；Candès–Tao, 2005）は、 行列 $X/\sqrt{n}$ が任意の $s$-スパースベクトルの $\ell_2$ ノルムを ほぼ保存することを要求する： $s$-次の RIP 定数 $\delta_s \in [0,1)$ を
\[ (1 - \delta_s)\|\boldsymbol{\beta}\|_2^2 \leq \frac{1}{n}\|X\boldsymbol{\beta}\|_2^2 \leq (1 + \delta_s)\|\boldsymbol{\beta}\|_2^2\]をすべての $s$-スパース $\boldsymbol{\beta}$ に対して満たす最小値として定義する。 $\delta_s$ が小さいほど $X/\sqrt{n}$ は $s$-スパースベクトルに対して 等長写像（等距離変換）に近い。
RIP と RE 条件の関係：RIP は RE 条件より強い条件であり、 $\delta_{2s} < 1$ が RE 条件を含意する。 ランダム行列（$X_{ij} \overset{\text{i.i.d.}}{\sim} \mathcal{N}(0,1/n)$ など）は $n \geq Cs\log(d/s)$（$C$ は定数）のとき高確率で RIP を満たす。
ノイズなし（$\boldsymbol{\varepsilon} = \boldsymbol{0}$）の場合、 真の問題は $\ell_0$ 最小化
\[ \min_{\boldsymbol{\beta}} \|\boldsymbol{\beta}\|_0 \quad \text{s.t.} \quad X\boldsymbol{\beta} = \boldsymbol{y}\]であるが、これは NP 困難である。その凸緩和として 基底追跡（Basis Pursuit）
\[ \min_{\boldsymbol{\beta}} \|\boldsymbol{\beta}\|_1 \quad \text{s.t.} \quad X\boldsymbol{\beta} = \boldsymbol{y}\]を考える。
定理（RIP による正確回復；Candès–Tao, 2005）： $\delta_{2s} < \sqrt{2} - 1 \approx 0.414$ のとき、 基底追跡の解は $s$-スパースな真の解 $\boldsymbol{\beta}^*$ と一致する。
ノイズあり（$\boldsymbol{\varepsilon} \neq \boldsymbol{0}$）の場合、 基底追跡デノイジング（Basis Pursuit Denoising, BPDN）
\[ \min_{\boldsymbol{\beta}} \|\boldsymbol{\beta}\|_1 \quad \text{s.t.} \quad \|X\boldsymbol{\beta} - \boldsymbol{y}\|_2 \leq \epsilon\]はラグランジュ形式で Lasso に一致し、$\delta_{2s} < \sqrt{2} - 1$ のもとで
\[ \|\hat{\boldsymbol{\beta}} - \boldsymbol{\beta}^*\|_2 \leq C_1 \frac{\|\boldsymbol{\beta}^* - \boldsymbol{\beta}^*_{(s)}\|_1}{\sqrt{s}} + C_2 \epsilon\]が成立する（$\boldsymbol{\beta}^*_{(s)}$ は $\boldsymbol{\beta}^*$ の上位 $s$ 成分のみ残したベクトル、 $C_1, C_2$ は定数）。右辺第一項はスパース近似誤差、 第二項はノイズに起因する誤差であり、$\boldsymbol{\beta}^*$ が正確に $s$-スパースなら 第一項はゼロとなる。
Lasso の $\ell_1$ ペナルティは凸であるため最適化が容易だが、 大きな係数に対しても線形のペナルティを課すため、 真に非ゼロな係数の推定量にバイアスが生じる。 このバイアスを低減するために以下の非凸ペナルティが提案されている。
非凸ペナルティは目的関数の非凸性を引き起こすため、 局所最適解への収束が問題となる。しかし局所最小解が適切な統計的性質を持つことが 示されており、LLA（Local Linear Approximation）アルゴリズムや 座標降下法による効率的な近似解法が開発されている。
正則化係数 $\lambda$ の選択は推定精度に直結する重要な問題である。
正則化は過学習抑制・分散低減・高次元設定での推定可能性を理論的に保証する枠組みであり、 ベイズ推定における事前分布（MAP 推定）・凸最適化におけるペナルティ付き目的関数・ 情報量基準によるモデル選択と統一的に理解できる。 $\ell_2$ 正則化（Ridge）は連続的な縮小と一意解を提供し、 $\ell_1$ 正則化（Lasso）は近接写像のソフト閾値処理によりスパース解を誘導し、 RE 条件のもとで $O(s\log d / n)$ というミニマックス最適な推定誤差を達成する。 圧縮センシングは RIP のもとで $n \ll d$ からの正確なスパース回復を保証し、 Lasso と基底追跡の理論的等価性を示す。 非凸ペナルティ（SCAD・MCP）はバイアスをさらに低減しオラクル性質を達成する。 これらの理論は凸最適化の双対理論・KKT 条件・近接写像・劣微分、 統計的推定のクラメール・ラオ下界・バイアス・バリアンス分解、 そして測度論的確率の集中不等式を有機的に統合した 高次元統計学の中核をなす。
Mathematics is the language with which God has written the universe.