回帰分析（Regression Analysis）は応答変数と共変量の関係を定量化する 統計的推論の枠組みであり、正則化（Regularization）は高次元・多重共線性・ 過学習の問題に対して推定の安定性と汎化性能を保証する手法である。 本節では線形回帰の古典的理論を基礎として、 多項式回帰・スプライン・カーネル法による非線形拡張、 Ridge・Lasso・Elastic Net による正則化、 および変数選択の理論を体系的に整理する。
応答変数 $y \in \mathbb{R}$、共変量ベクトル $\boldsymbol{x} \in \mathbb{R}^p$、 真の回帰関数 $f^*(\boldsymbol{x}) = \mathbb{E}[Y \mid \boldsymbol{X} = \boldsymbol{x}]$、 加法的ノイズモデル
\[ y_i = f^*(\boldsymbol{x}_i) + \varepsilon_i, \quad \varepsilon_i \overset{\text{i.i.d.}}{\sim} (0, \sigma^2), \quad i = 1, \ldots, n\]を考える（$\varepsilon_i$ の分布は正規性を仮定しない場合も含む）。 行列表記として $X \in \mathbb{R}^{n \times p}$（各行が $\boldsymbol{x}_i^\top$）、 $\boldsymbol{y} \in \mathbb{R}^n$ を用いる。 高次元設定として $p \gg n$ の場合も考慮する。
線形回帰モデル $f(\boldsymbol{x}) = \boldsymbol{x}^\top \boldsymbol{\beta}$ （$\boldsymbol{\beta} \in \mathbb{R}^p$）において、 OLS 推定量 $\hat{\boldsymbol{\beta}} = (X^\top X)^{-1}X^\top \boldsymbol{y}$ による予測値 $\hat{\boldsymbol{y}} = X\hat{\boldsymbol{\beta}} = H\boldsymbol{y}$ は $\boldsymbol{y}$ の列空間 $\mathrm{col}(X)$ への直交射影であり、 ハット行列 $H = X(X^\top X)^{-1}X^\top$ は対称・冪等である。 この幾何学的構造から以下の直交分解が成立する：
\[ \|\boldsymbol{y} - \bar{y}\boldsymbol{1}\|^2 = \|\hat{\boldsymbol{y}} - \bar{y}\boldsymbol{1}\|^2 + \|\boldsymbol{y} - \hat{\boldsymbol{y}}\|^2\]\[ \underbrace{\mathrm{TSS}}_{\text{全変動}} = \underbrace{\mathrm{ESS}}_{\text{説明された変動}} + \underbrace{\mathrm{RSS}}_{\text{残差変動}}\]ここで $\mathrm{TSS} = \|\boldsymbol{y} - \bar{y}\boldsymbol{1}\|^2$、 $\mathrm{ESS} = \|\hat{\boldsymbol{y}} - \bar{y}\boldsymbol{1}\|^2$、 $\mathrm{RSS} = \|\boldsymbol{y} - \hat{\boldsymbol{y}}\|^2$ であり、 決定係数 $R^2 = \mathrm{ESS}/\mathrm{TSS} = 1 - \mathrm{RSS}/\mathrm{TSS} \in [0,1]$ はモデルが全変動のうち説明できる割合を表す。 この直交分解は切片を含むモデルにおいて成立し、 切片なしモデルでは $\mathrm{TSS} \neq \mathrm{ESS} + \mathrm{RSS}$ となる場合がある。
$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}^{p \times r}$、$r = \mathrm{rank}(X)$）とおくと、
\[ \hat{\boldsymbol{\beta}}^{\mathrm{OLS}} = V\Sigma^{-1}U^\top \boldsymbol{y}, \qquad H = UU^\top\]と表される。$X^\top X = V\Sigma^2 V^\top$ の最小固有値 $\sigma_r^2$ が小さいとき、 $\Sigma^{-1}$ の最大固有値 $1/\sigma_r$ が発散し OLS 推定量の分散が増大する。 この条件数 $\kappa(X^\top X) = \sigma_1^2/\sigma_r^2$ が大きいとき、 多重共線性による数値的不安定性が生じる。 正則化は本質的にこの不安定方向を抑制することで推定を安定化する。
推定量 $\hat{f}$ の汎化誤差（二乗損失）を測度論的確率の枠組みで厳密に分解する。 新たな観測点 $\boldsymbol{x}_0$ における予測の期待二乗誤差は、 訓練データ $\mathcal{D}_n$ の確率的変動にわたる期待値として
\[ \mathbb{E}_{\mathcal{D}_n}\bigl[(y_0 - \hat{f}(\boldsymbol{x}_0))^2\bigr] = \underbrace{\bigl(f^*(\boldsymbol{x}_0) - \mathbb{E}[\hat{f}(\boldsymbol{x}_0)]\bigr)^2}_{\mathrm{Bias}^2} + \underbrace{\mathbb{E}\bigl[(\hat{f}(\boldsymbol{x}_0) - \mathbb{E}[\hat{f}(\boldsymbol{x}_0)])^2\bigr]}_{\mathrm{Variance}} + \underbrace{\sigma^2}_{\text{不可約誤差}}\]と分解される。各項の意味は以下の通りである。
線形モデル $\hat{f}(\boldsymbol{x}) = \boldsymbol{x}^\top \hat{\boldsymbol{\beta}}$ において、 OLS の各予測点でのバリアンスは $\mathrm{Var}(\hat{f}(\boldsymbol{x}_0)) = \sigma^2 \boldsymbol{x}_0^\top (X^\top X)^{-1} \boldsymbol{x}_0$ と表される。$p/n$ が大きいほどバリアンスは増大し、 適切な正則化が平均二乗誤差（MSE）を OLS より改善することが保証される （Hoerl–Kennard 定理）。
一変量 $x \in \mathbb{R}$ に対して、$K$ 次多項式回帰は
\[ f(x) = \beta_0 + \beta_1 x + \beta_2 x^2 + \cdots + \beta_K x^K = \boldsymbol{\phi}(x)^\top \boldsymbol{\beta}\]と定義される（$\boldsymbol{\phi}(x) = (1, x, x^2, \ldots, x^K)^\top$）。 基底 $\boldsymbol{\phi}(x)$ を用いて設計行列 $\Phi \in \mathbb{R}^{n \times (K+1)}$ を構成すれば、 OLS がそのまま適用できる。 $K$ を増やすとバイアスが減少するがバリアンスが増大し、 高次（$K \geq n-1$）では訓練データを完全内挿（補間）し汎化性能が著しく劣化する。 また高次多項式は Runge 現象（端点付近での振動）を引き起こすため、 実用上は区分多項式（スプライン）が好まれる。
区間 $[a,b]$ に節点（Knot）$a \leq \xi_1 < \xi_2 < \cdots < \xi_K \leq b$ を配置し、 各区間で多項式を当てはめつつ節点での滑らかさを保証する関数クラスを スプラインと呼ぶ。$M$ 次のスプラインは各区間で $M$ 次多項式であり、 節点で $M-1$ 階微分まで連続である。
3 次スプライン（$M=3$）は節点での二階微分連続性を持ち、 視覚的な滑らかさと数値的性質のバランスから最も広く用いられる。 その基底表現として切断べき基底 $\{1, x, x^2, x^3, (x-\xi_1)_+^3, \ldots, (x-\xi_K)_+^3\}$ が使えるが、数値的安定性からB スプライン基底が実用的に好まれる。
自然スプライン（Natural Spline）は両端区間で線形（二・三階微分がゼロ）という 追加制約を課したスプラインであり、端点での推定の不安定性を改善する。 自由度（基底の数）は節点数 $K$ に依存し、 交差検証または AIC・BIC（前節）により選択する。
節点選択の問題を回避するため、すべての観測点を節点として配置しつつ、 滑らかさを制御するペナルティを課した平滑化スプライン （Smoothing Spline）は
\[ \hat{f} = \arg\min_{f \in \mathcal{H}^2} \left[ \frac{1}{n}\sum_{i=1}^n (y_i - f(x_i))^2 + \lambda \int_a^b \{f''(x)\}^2\, dx \right]\]と定義される（$\mathcal{H}^2$：二乗可積分な二階導関数を持つ関数空間）。 ペナルティ項 $\int \{f''\}^2\,dx$ は関数の曲率を測り、 $\lambda = 0$ で完全補間、$\lambda \to \infty$ で最小二乗直線に収束する。 Reinsch（1967）によれば、この変分問題の解は必ず 節点 $\{x_i\}_{i=1}^n$ を持つ自然 3 次スプラインとなる （すなわち有限次元問題に帰着する）。 解は $\hat{\boldsymbol{f}} = (I + n\lambda \Omega)^{-1}\boldsymbol{y}$ と表され （$\Omega_{ij} = \int B_i''(x)B_j''(x)\,dx$、$B_i$ はスプライン基底）、 平滑化行列 $S_\lambda = (I + n\lambda \Omega)^{-1}$ はハット行列の一般化である。 有効自由度 $\mathrm{df}(\lambda) = \mathrm{tr}(S_\lambda)$ は $\lambda = 0$ で $n$（完全補間）から $\lambda \to \infty$ で $2$（線形）まで連続的に変化する。
ノンパラメトリックな回帰関数の推定として、 Nadaraya–Watson カーネル推定量は
\[ \hat{f}_h(x) = \frac{\sum_{i=1}^n K_h(x - x_i) y_i}{\sum_{i=1}^n K_h(x - x_i)}, \quad K_h(u) = \frac{1}{h}K\!\left(\frac{u}{h}\right)\]と定義される（$K$：カーネル関数、$h > 0$：バンド幅）。 代表的なカーネルとして $K(u) = \frac{1}{\sqrt{2\pi}}e^{-u^2/2}$（ガウスカーネル）や $K(u) = \frac{3}{4}(1-u^2)_+$（Epanechnikov カーネル）が用いられる。 バンド幅 $h$ はバイアス・バリアンストレードオフを制御し、 $h \to 0$ で補間、$h \to \infty$ で全体平均に収束する。 最適バンド幅の漸近的スケールは $h^* \propto n^{-1/5}$（一変量）であり、 これは収束速度 $O(n^{-4/5})$ を達成するが、$p$ 次元では $O(n^{-4/(4+p)})$ に劣化する （次元の呪い、Curse of Dimensionality）。
再生核ヒルベルト空間（Reproducing Kernel Hilbert Space, RKHS）は カーネル法を統一的に定式化する関数空間である。 対称正定値カーネル関数 $k: \mathcal{X} \times \mathcal{X} \to \mathbb{R}$ に対して、RKHS $\mathcal{H}_k$ はヒルベルト空間であって 内積 $\langle \cdot, \cdot \rangle_{\mathcal{H}_k}$ を持ち、 再生性（Reproducing Property）
\[ f(\boldsymbol{x}) = \langle f, k(\cdot, \boldsymbol{x}) \rangle_{\mathcal{H}_k} \quad \forall f \in \mathcal{H}_k,\; \boldsymbol{x} \in \mathcal{X}\]を満たす。Moore–Aronszajn 定理により、 各対称正定値カーネルに一意な RKHS が対応する。
RKHS 上の正則化回帰問題
\[ \hat{f} = \arg\min_{f \in \mathcal{H}_k} \left[ \frac{1}{n}\sum_{i=1}^n (y_i - f(\boldsymbol{x}_i))^2 + \lambda \|f\|_{\mathcal{H}_k}^2 \right]\]に対して、表現定理（Representer Theorem；Kimeldorf–Wahba, 1971）は 解が有限次元表現
\[ \hat{f}(\boldsymbol{x}) = \sum_{i=1}^n \alpha_i k(\boldsymbol{x}_i, \boldsymbol{x})\]を持つことを保証する。係数 $\boldsymbol{\alpha} = (\alpha_1,\ldots,\alpha_n)^\top$ は
\[ \boldsymbol{\alpha} = (K + n\lambda I)^{-1}\boldsymbol{y}\]と閉形式で得られる（$K_{ij} = k(\boldsymbol{x}_i, \boldsymbol{x}_j)$ はグラム行列）。 カーネル関数の選択により様々な関数クラスが誘導される。 $k(x,x') = \exp(-\|x-x'\|^2/(2h^2))$（RBF カーネル）は平滑化スプラインの一般化、 $k(x,x') = (x^\top x' + c)^K$ は $K$ 次多項式特徴写像に対応する。 カーネルトリック（$\boldsymbol{x}_i^\top \boldsymbol{x}_j$ をすべて $k(\boldsymbol{x}_i, \boldsymbol{x}_j)$ で置換）により、 高次元・無限次元の特徴空間での計算が $O(n^2)$ で実行可能となる。
Ridge 回帰（Tikhonov 正則化）は
\[ \hat{\boldsymbol{\beta}}^{\mathrm{Ridge}}(\lambda) = \arg\min_{\boldsymbol{\beta}} \left[ \|\boldsymbol{y} - X\boldsymbol{\beta}\|^2 + \lambda\|\boldsymbol{\beta}\|_2^2 \right] = (X^\top X + \lambda I_p)^{-1}X^\top \boldsymbol{y}\]と定義される（$\lambda > 0$）。SVD $X = U\Sigma V^\top$ を用いると
\[ \hat{\boldsymbol{\beta}}^{\mathrm{Ridge}} = V\,\mathrm{diag}\!\left(\frac{\sigma_j}{\sigma_j^2 + \lambda}\right) U^\top \boldsymbol{y}\]であり、OLS の各特異値方向の成分を縮小率 $\rho_j = \sigma_j^2/(\sigma_j^2 + \lambda) \in (0,1)$ 倍に縮小する。 小さな特異値（不安定方向）が強く抑制されることで分散が低減される。 対応する有効自由度は
\[ \mathrm{df}(\lambda) = \mathrm{tr}(H_\lambda) = \mathrm{tr}(X(X^\top X + \lambda I)^{-1}X^\top) = \sum_{j=1}^r \frac{\sigma_j^2}{\sigma_j^2 + \lambda}\]であり、$\lambda = 0$ で $r$（$= p$、フルランク時）から $\lambda \to \infty$ で $0$ まで連続的に変化する。
$\hat{\boldsymbol{\beta}}^{\mathrm{Ridge}}$ の平均と共分散行列は
\[ \mathbb{E}[\hat{\boldsymbol{\beta}}^{\mathrm{Ridge}}] = (X^\top X + \lambda I)^{-1}X^\top X \boldsymbol{\beta}^* = \boldsymbol{\beta}^* - \lambda(X^\top X + \lambda I)^{-1}\boldsymbol{\beta}^*\]\[ \mathrm{Cov}(\hat{\boldsymbol{\beta}}^{\mathrm{Ridge}}) = \sigma^2 (X^\top X + \lambda I)^{-1}X^\top X(X^\top X + \lambda I)^{-1}\]と計算される。バイアスは $-\lambda(X^\top X + \lambda I)^{-1}\boldsymbol{\beta}^*$ であり $\lambda$ とともに増大する一方、 バリアンス（$\mathrm{Cov}$ のトレース）は $\lambda$ とともに単調減少する。
Hoerl–Kennard 定理： 任意の $\boldsymbol{\beta}^* \neq \boldsymbol{0}$ に対して、 十分小さな $\lambda > 0$ が存在して
\[ \mathrm{MSE}(\hat{\boldsymbol{\beta}}^{\mathrm{Ridge}}(\lambda)) < \mathrm{MSE}(\hat{\boldsymbol{\beta}}^{\mathrm{OLS}})\]が成立する。すなわち Ridge 回帰は OLS よりも小さい MSE を達成できる $\lambda$ が必ず存在する（$\boldsymbol{\beta}^* = \boldsymbol{0}$ の場合は $\lambda = 0$ が最適）。 これはバイアスの導入がバリアンス低減によって補われることを意味し、 正則化の統計的正当性の基礎となる。
Ridge 回帰の双対問題（Lagrange 双対、前節）は
\[ \hat{\boldsymbol{y}} = X\hat{\boldsymbol{\beta}}^{\mathrm{Ridge}} = X(X^\top X + \lambda I)^{-1}X^\top \boldsymbol{y} = (XX^\top + \lambda I)^{-1}XX^\top \boldsymbol{y} \cdot \lambda^{-1}\]Woodbury 行列恒等式 $X(X^\top X + \lambda I)^{-1}X^\top = XX^\top(XX^\top + \lambda I)^{-1}$ を用いると、 グラム行列 $K = XX^\top \in \mathbb{R}^{n \times n}$ を用いて
\[ \hat{\boldsymbol{y}} = K(K + \lambda I)^{-1}\boldsymbol{y}\]と書ける。$K_{ij} = \boldsymbol{x}_i^\top \boldsymbol{x}_j$ を任意のカーネル $K_{ij} = k(\boldsymbol{x}_i, \boldsymbol{x}_j)$ に置き換えることで カーネル Ridge 回帰（Kernel Ridge Regression, KRR）が得られる。 KRR は表現定理の解と一致し、$O(n^3)$ の計算量（グラム行列の逆行列）で解が得られる。
Lasso（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]\]と定義される。等価な制約付き形式 $\min_{\boldsymbol{\beta}} \|\boldsymbol{y} - X\boldsymbol{\beta}\|^2$ s.t. $\|\boldsymbol{\beta}\|_1 \leq t$ において、 $\ell_1$ 球の頂点構造（多面体の角）により 解が座標軸上（スパース点）に引き寄せられる。 これに対して Ridge の $\ell_2$ 球は滑らかな球面であり、頂点を持たないためスパース解を生じない。
Lasso の KKT 条件（前節）は
\[ \frac{1}{n}[X^\top(\boldsymbol{y} - X\hat{\boldsymbol{\beta}})]_j = \lambda \hat{z}_j, \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$ が強制される。
Lasso の目的関数は $\beta_j$ について分離可能であり、 他の座標を固定して $\beta_j$ を更新する座標降下法が効率的に適用できる。 部分残差 $\boldsymbol{r}_j = \boldsymbol{y} - \sum_{k \neq j} \boldsymbol{x}_k \hat{\beta}_k$ に対して
\[ \hat{\beta}_j = \mathcal{S}_{\lambda n / \|\boldsymbol{x}_j\|^2} \!\left(\frac{\boldsymbol{x}_j^\top \boldsymbol{r}_j}{\|\boldsymbol{x}_j\|^2}\right), \qquad \mathcal{S}_\tau(z) = \mathrm{sign}(z)\max(|z| - \tau, 0)\]と閉形式で得られる。$\mathcal{S}_\tau$ はソフト閾値処理（$\ell_1$ 近接写像）であり、 OLS の推定値を $\tau$ だけ零に向けて縮小する。
$\lambda$ を $\lambda_{\max} = \|X^\top \boldsymbol{y}\|_\infty / n$ （すべての係数がゼロとなる最小の $\lambda$）から $0$ まで減少させると、 解のパスは $\boldsymbol{\beta}$ の各成分について区分線形となる （LARS アルゴリズム；Efron et al., 2004）。 この性質により $\lambda$ の全パス（正則化パス）を $O(np\min(n,p))$ の計算量で追跡でき、交差検証による $\lambda$ 選択が効率化される。
サポート $S = \mathrm{supp}(\boldsymbol{\beta}^*)$（$|S| = s$）、 制限固有値条件（RE 条件）$\kappa > 0$、 $\lambda \geq 2\sigma\sqrt{2\log(2p/\delta)/n}$ のもとで、 確率 $1-\delta$ 以上で
\[ \|\hat{\boldsymbol{\beta}}^{\mathrm{Lasso}} - \boldsymbol{\beta}^*\|_2 \leq \frac{4\lambda\sqrt{s}}{\kappa}, \qquad \frac{1}{n}\|X(\hat{\boldsymbol{\beta}}^{\mathrm{Lasso}} - \boldsymbol{\beta}^*)\|^2 \leq \frac{16\lambda^2 s}{\kappa^2}\]が成立する。$\lambda = O(\sigma\sqrt{\log p / n})$ のとき $\ell_2$ 誤差は $O(\sigma\sqrt{s\log p / n})$、 予測誤差は $O(\sigma^2 s \log p / n)$ となり、 これらは高次元スパース推定のミニマックス最適レートに一致する。 変数選択の一致性（サポートの正確な回復）には、 より強いアービン条件（Irrepresentability Condition）が必要である。
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]\]と定義される。$\ell_2$ 項により目的関数は $\mu = 2\lambda_2$ の強凸となり 一意解が保証される。$\ell_1$ 項がスパース性を誘導し、 $\ell_2$ 項が相関変数をグループとして選択する傾向（グループ効果）をもたらす。 Lasso の制限（$d > n$ で高々 $n$ 変数しか選べない、 相関変数のうち一つのみを任意に選択する）を克服する。 座標ごとのソフト閾値更新式は
\[ \hat{\beta}_j = \frac{1}{1 + 2\lambda_2 n/\|\boldsymbol{x}_j\|^2} \mathcal{S}_{\lambda_1 n/\|\boldsymbol{x}_j\|^2} \!\left(\frac{\boldsymbol{x}_j^\top \boldsymbol{r}_j}{\|\boldsymbol{x}_j\|^2}\right)\]であり、ソフト閾値処理の後に $\ell_2$ 縮小が乗じられる形となる。
共変量に既知のグループ構造 $\{1,\ldots,p\} = G_1 \cup \cdots \cup G_K$ がある場合、 グループ Lasso（Yuan–Lin, 2006）は $\lambda \sum_{k=1}^K \sqrt{|G_k|}\|\boldsymbol{\beta}_{G_k}\|_2$ をペナルティとして グループ単位でのゼロ/非ゼロを制御する。
隣接する係数間の差を罰する融合 Lasso（Fused Lasso；Tibshirani et al., 2005）は
\[ \hat{\boldsymbol{\beta}}^{\mathrm{FL}} = \arg\min_{\boldsymbol{\beta}} \left[ \frac{1}{2n}\|\boldsymbol{y} - X\boldsymbol{\beta}\|^2 + \lambda_1\|\boldsymbol{\beta}\|_1 + \lambda_2\sum_{j=2}^p |\beta_j - \beta_{j-1}| \right]\]と定義される。第二ペナルティ項が係数の空間的・時系列的な連続性を誘導し、 ゲノム解析（CNV 検出）・信号処理（変化点検出）に有効である。 一般化ペナルティ $\lambda\|D\boldsymbol{\beta}\|_1$（$D$：差分行列）として Total Variation 正則化と接続する。
説明変数の部分集合 $S \subseteq \{1,\ldots,p\}$ を選択する 最良部分集合選択（Best Subset Selection）は
\[ \hat{S} = \arg\min_{S \subseteq \{1,\ldots,p\},\, |S| \leq s} \|\boldsymbol{y} - X_S\hat{\boldsymbol{\beta}}_S\|^2\]と定義される（$X_S$：$S$ に対応する列、$\hat{\boldsymbol{\beta}}_S$：OLS 解）。 この問題は $2^p$ 個の候補を探索する NP 困難な組み合わせ最適化であり、 $p \leq 40$ 程度が実用上の限界とされてきたが、 近年の Mixed Integer Optimization（MIO）アプローチ（Bertsimas et al., 2016）により $p \sim 10^3$ 規模での解法が可能となっている。 変数選択の基準として AIC・BIC・$C_p$ 統計量
\[ C_p = \frac{\mathrm{RSS}_S}{\hat{\sigma}^2} - n + 2|S|\]が用いられる（$\hat{\sigma}^2$ は飽和モデルの誤差分散推定量）。 $C_p \approx |S|$ のとき予測誤差が最小となる。
貪欲なヒューリスティックとして以下のアルゴリズムが広く用いられる。
これらの貪欲法は最良部分集合選択の最適解を保証しないが、 計算効率と変数選択性能のバランスから実用上広く用いられる。 ただし多重比較の問題（p ハッキング）に注意が必要であり、 確証的な推論には検定後の推論（Post-Selection Inference）理論が必要となる。
変数選択のための情報量基準は以下のように適用される。
\[ \mathrm{AIC}(S) = n\log\!\left(\frac{\mathrm{RSS}_S}{n}\right) + 2|S|, \qquad \mathrm{BIC}(S) = n\log\!\left(\frac{\mathrm{RSS}_S}{n}\right) + |S|\log n\]BIC は一致性（$n \to \infty$ で真のモデルを確率 $1$ で選択）を持ち、 AIC は予測精度の最適化を目的とする。 高次元設定（$p \gg n$）では通常の BIC では変数選択の一致性が失われるため、 拡張 BIC（EBIC；Chen–Chen, 2008）
\[ \mathrm{EBIC}_\gamma(S) = n\log\!\left(\frac{\mathrm{RSS}_S}{n}\right) + |S|\log n + 2\gamma |S|\log p, \quad \gamma \in [0,1]\]が用いられる。$\gamma = 0$ が通常の BIC、$\gamma = 1$ が最も厳しいペナルティに対応する。
$k$-分割交差検証（$k$-Fold Cross-Validation）では $\mathcal{D}_n$ を $k$ 個の等サイズのフォールドに分割し、 各フォールドを順に検証データとしたときの予測誤差の平均
\[ \mathrm{CV}(\lambda) = \frac{1}{k}\sum_{\ell=1}^k \frac{1}{|\mathcal{V}_\ell|}\sum_{i \in \mathcal{V}_\ell} (y_i - \hat{f}^{(-\ell)}(\boldsymbol{x}_i))^2\]を $\lambda$ の関数として計算し最小化する（$\hat{f}^{(-\ell)}$：$\ell$ 番目のフォールドを除いて学習したモデル）。 $k = n$（Leave-One-Out CV, LOOCV）のとき、 線形モデルでは LOOCV の予測誤差が
\[ \mathrm{LOOCV}(\lambda) = \frac{1}{n}\sum_{i=1}^n \left(\frac{y_i - \hat{y}_i}{1 - H_{\lambda,ii}}\right)^2\]と閉形式で計算できる（$H_\lambda = X(X^\top X + \lambda I)^{-1}X^\top$、 $H_{\lambda,ii}$ はその $(i,i)$ 成分）。 実用上は $k = 5$ または $k = 10$ が広く用いられ、 バイアス・バリアンスのトレードオフ（$k$ が大きいほど低バイアス・高バリアンス）から選択する。 Lasso の正則化パスの区分線形性を利用すれば、 全パスの LOOCV が $O(np\min(n,p))$ で計算できる。
LOOCV の計算効率化として、 一般化交差検証（Generalized Cross-Validation, GCV；Craven–Wahba, 1979）は
\[ \mathrm{GCV}(\lambda) = \frac{1}{n} \frac{\|\boldsymbol{y} - H_\lambda\boldsymbol{y}\|^2} {(1 - \mathrm{tr}(H_\lambda)/n)^2}\]と定義される。LOOCV では $H_{\lambda,ii}$ ごとに異なる分母を持つのに対し、 GCV は $\mathrm{tr}(H_\lambda)/n$ という一様な近似を用いる。 正則化スプライン・Ridge 回帰・カーネル回帰に対して広く適用され、 $O(n^2)$ または $O(np)$ の計算量で最適 $\lambda$ を選択できる。
回帰分析は OLS の幾何学的構造（直交射影・ハット行列）と Gauss–Markov 定理による BLUE 性を基礎とし、 多項式回帰・スプライン・カーネル RKHS による非線形拡張と、 Ridge・Lasso・Elastic Net・グループ Lasso・融合 Lasso による正則化が バイアス・バリアンストレードオフを制御する体系を形成する。 Ridge は SVD を通じた連続的縮小と Hoerl–Kennard 定理による MSE 改善を保証し、 カーネル Ridge 回帰へと自然に拡張される。 Lasso は $\ell_1$ 球の多面体構造と KKT 条件のソフト閾値処理により スパース解を誘導し、RE 条件のもとで $O(\sigma\sqrt{s\log p/n})$ の ミニマックス最適な推定精度を達成する。 変数選択は最良部分集合選択・段階的選択・情報量基準（AIC・BIC・EBIC）により行われ、 正則化係数の選択は交差検証・GCV が標準的手法を提供する。 これらは凸最適化の双対理論・近接写像・劣微分、 測度論的確率の集中不等式、そして統計的推定の漸近理論と有機的に統合された 現代の統計的学習理論の中核をなす。
Mathematics is the language with which God has written the universe.