线性模型
通篇考虑线性模型
$$ \bm{Y} = \bm{X}\bm{\beta}^* + \bm{\varepsilon} $$其中 $\bm{\varepsilon}\in\text{subG}_n(\sigma^2)$，这表示对任意 $\bm{v}\in\mathbb{R}^n$ 且 $\|\bm{v}\|_2\leq1$，$\bm{v}'\bm{\varepsilon}\in\text{subG}(\sigma^2)$。此外，假设 $\bm{X}$ 是固定的。
LASSO 估计量就是
$$ \hat{\bm{\beta}} := \arg\min_{\bm{\beta}\in\mathbb{R}^p} \frac{1}{2n}\|\bm{Y}-\bm{X}\bm{\beta}\|_2^2 + \lambda_n\|\bm{\beta}\|_1 $$$\ell_1$ 范数作为惩罚项使得解具有稀疏性 (sparsity)。
预测误差的界
我们考察均方预测误差 (mean squared prediction error, MSPE)：
$$ \text{MSPE} = \frac{1}{n}\|\bm{X}(\hat{\bm{\beta}}-\bm{\beta}^*)\|_2^2 $$下面我们会给出它的界。
记事件 $A := \{\lambda_n \geq \frac1n\|\bm{X}'\bm{\varepsilon}\|_{\infty}\}$。
Theorem 1.
若事件 $A$ 成立，则
$$ \frac{1}{n}\|\bm{X}(\hat{\bm{\beta}}-\bm{\beta}^*)\|_2^2 \leq 4\|\bm{\beta}^*\|_1\lambda_n $$首先，我们证明如下基本不等式：
$$ \frac{1}{2n}\|\bm{X}(\hat{\bm{\beta}}-\bm{\beta}^*)\|_2^2 \leq \frac{1}{n}\bm{\varepsilon}'\bm{X}(\hat{\bm{\beta}}-\bm{\beta}^*) + \lambda_n(\|\bm{\beta}^*\|_1-\|\hat{\bm{\beta}}\|_1) $$此不等式事实上直接来自于
$$ \frac{1}{2n}\|\bm{Y}-\bm{X}\hat{\bm{\beta}}\|_2^2 + \lambda_n\|\hat{\bm{\beta}}\|_1 \leq \frac{1}{2n}\|\bm{Y}-\bm{X}\bm{\beta}^*\|_2^2 + \lambda_n\|\bm{\beta}^*\|_1 $$只需将 $\bm{Y} = \bm{X}\bm{\beta}^* + \bm{\varepsilon}$ 代入即可得到。
以下给出 $\frac{1}{2n}\|\bm{X}(\hat{\bm{\beta}}-\bm{\beta}^*)\|_2^2$ 的界：
$$ \begin{align*} \frac{1}{2n}\|\bm{X}(\hat{\bm{\beta}}-\bm{\beta}^*)\|_2^2 &\leq \frac{1}{n}\bm{\varepsilon}'\bm{X}(\hat{\bm{\beta}}-\bm{\beta}^*) + \lambda_n(\|\bm{\beta}^*\|_1-\|\hat{\bm{\beta}}\|_1) \\ &\leq \frac{1}{n}\|\bm{X}'\bm{\varepsilon}\|_\infty\|\hat{\bm{\beta}}-\bm{\beta}^*\|_1 + \lambda_n(\|\bm{\beta}^*\|_1-\|\hat{\bm{\beta}}\|_1) \\ &\leq \frac{1}{n}\|\bm{X}'\bm{\varepsilon}\|_\infty\|(\|\hat{\bm{\beta}}\|_1+\|\bm{\beta}\|_1) + \lambda_n(\|\bm{\beta}^*\|_1-\|\hat{\bm{\beta}}\|_1) \\ &= \|\hat{\bm{\beta}}\|_1\biggl(\frac{1}{n}\|\bm{X}'\bm{\varepsilon}\|_\infty-\lambda_n\biggr) + \|\bm{\beta}^*\|_1\biggl(\frac{1}{n}\|\bm{X}'\bm{\varepsilon}\|_\infty+\lambda_n\biggr) \\ &\leq 2\lambda_n\|\bm{\beta}^*\|_1 \end{align*} $$第二行使用了 Hölder 不等式，第三行使用了三角不等式，最后一行是因为事件 $A$ 成立。
关于此定理有几点需要注意：
- 不等式所给出的界取决于调谐参数 $\lambda_n$，而它又取决于样本量 $n$。
- 此不等式在事件 $A$ 上成立，因此如果事件 $A$ 有很大概率发生，则此不等式也有很大概率发生（不低于事件 $A$ 发生的概率）。
$\lambda_n$ 的选取和 LASSO 的慢率
我们当然希望 $\lambda_n$ 越小越好，我们特别希望 $\lambda_n\|\bm{\beta}^*\|=o(1)$，因为这样预测误差就会收敛。但是我们又要保证事件 $A$ 发生的概率，所以 $\lambda_n$ 又不能过小，或者说我们要限制 $\frac1n\|\bm{X}'\bm{\varepsilon}\|_{\infty}$。为此，我们对 $\bm{X}$ 施加一个额外的假设。
Assumption 2.
在这个假设下，对任意 $t>0$ 我们有
$$ \begin{align*} \mathbb{P}\biggl\{\frac{1}{n}\|\bm{X}'\bm{\varepsilon}\|_\infty\geq t\biggr\} &= \mathbb{P}\biggl\{\frac{1}{n}\max_j|\bm{X}_j'\bm{\varepsilon}|\geq t\biggr\} \\ &\leq \sum_j \mathbb{P}\biggl\{\frac{1}{n}|\bm{X}_j'\bm{\varepsilon}|\geq t\biggr\} \\ &\leq \sum_j \mathbb{P}\biggl\{\frac{|\bm{X}_j'\bm{\varepsilon}|}{n\|\bm{X}_j\|_2}\geq\frac{t}{\|\bm{X}_j\|_2}\biggr\} \\ &\leq 2p\exp\biggl(-\frac{t^2n}{2\sigma^2C}\biggr) \end{align*} $$最后一行利用了 sub-Gaussian 的性质：如果 $X\in\text{subG}(\sigma^2)$，则对任意 $t>0$ 有
$$ \mathbb{P}\{X\geq t\} \leq \exp\biggl(-\frac{t^2}{2\sigma^2}\biggr) $$给定一个 $\delta>0$，我们选择
$$ t = \sqrt{\frac{2\sigma^2C}{n}[\log(1/\delta)+\log(2p)]} $$那么以上概率就会
$$ \mathbb{P}\biggl\{\frac{1}{n}\|\bm{X}'\bm{\varepsilon}\|_\infty\geq t\biggr\} \leq 2p\exp\biggl(-\frac{t^2n}{2\sigma^2C}\biggr) \leq \delta $$也就是说，我们取 $\lambda_n$ 为上述 $t$ 值，那么事件 $A$ 发生的概率就至少是 $1-\delta$。我们有以下推论。
Corollary 3 (Slow rate for the LASSO).
至少以概率 $1-\delta$，我们有
$$ \frac{1}{n}\|\bm{X}(\hat{\bm{\beta}}-\bm{\beta}^*)\|_2^2 \leq 4\|\bm{\beta}^*\|_1\sigma\sqrt{\frac{2C}{n}[\log(1/\delta)+\log(2p)]} $$可见，当我们取 $\delta=1/n$，并假设 $\|\bm{\beta}^*\|=o(\sqrt{n/\log(p\vee n)})$，我们就得到了随 $n\to\infty$ 时预测误差的收敛。
Note
为什么叫 slow rate？在最优子集选择 (best subset selection) 中，我们可以推出 (reference?)
$$ \frac{1}{n}\|\bm{X}(\hat{\bm{\beta}}-\bm{\beta}^*)\|_2^2 \lesssim \|\bm{\beta}\|_0\frac{\log n+\log p}{n} $$而在上述推论中，如果我们选择 $\delta=1/n$，则会得到
$$ \frac{1}{n}\|\bm{X}(\hat{\bm{\beta}}-\bm{\beta}^*)\|_2^2 \lesssim \|\bm{\beta}^*\|_1\sqrt{\frac{\log n+\log p}{n}} $$这多了一个根号，因此比最优子集选择的收敛率要慢。
LASSO 的快率
我们是否能改进前述收敛速率呢？另外，有没有可能得到 $\hat{\bm{\beta}}$ 本身的一致性呢？答案是可以的。
Restricted Eigenvalue
注意到如果 $\mu_{\min}(\bm{X}'\bm{X})\geq\gamma_n>0$，则有
$$ \|\hat{\bm{\beta}}-\bm{\beta}^*\|_2 \leq \frac{1}{\gamma_n}\|\bm{X}(\hat{\bm{\beta}}-\bm{\beta}^*)\|_2^2 $$而当 $p>n$ 时，$\mu_{\min}(\bm{X}'\bm{X})=0$，此时我们无法得到 $\|\hat{\bm{\beta}}-\bm{\beta}^*\|_2$ 的收敛。我们需要对 $\bm{X}$ 施加额外的假设，有很多种方式，但基本思想就一个：让 $\gamma_n$ 和零保持距离。
以下介绍一种广泛使用的假设：受限特征值条件 (restricted eigenvalue condition, RE)。
Definition 4 (Restricted Eigenvalue).
给定 $\alpha\geq1$ 和 $S\subseteq\{1,\dots,p\}$ 且 $S\neq\emptyset$，令
$$ \mathcal{C}_\alpha(S) = \{\bm{\Delta}\in\mathbb{R}^p\colon\|\bm{\Delta}_{S^\complement}\|_1\leq\alpha\|\bm{\Delta}_S\|_1\} $$其中 $S^\complement = \{1,\dots,p\}\backslash S$，$\bm{\Delta}_{S}=(\Delta_j)_{j\in S}$。
如果存在某个 $\alpha\geq1$ 和 $\kappa>0$，对任意的 $\bm{\Delta}\in\mathcal{C}_\alpha(S)$ 都有
$$ \frac{1}{n}\|\bm{X}\bm{\Delta}\|_2^2 \geq \kappa\|\bm{\Delta}\|_2^2 $$则称 $n\times p$ 的矩阵 $\bm{X}$ 满足 $S$ 上的 $\text{RE}(\alpha,\kappa)$ 条件。
下面我们花一些篇幅来从直觉上理解这一条件。
取 $\bm{\Delta}=\hat{\bm{\beta}}-\bm{\beta}^*$。前面我们已经证明了 $\frac1n\|\bm{X}\bm{\Delta}\|_2^2$ 能够以大概率取很小的值，但这不意味着 $\|\bm{\Delta}\|_2^2$ 也可以很小，因为函数 $\bm{\Delta}\mapsto\frac1n\|\bm{X}\bm{\Delta}\|_2^2$ 在 $\hat{\bm{\beta}}-\bm{\beta}^*$ 附近可能很平坦，也就是说，在较宽的一个范围内我们都能得到较小的损失函数值。
如果 $\mu_{\min}(\bm{X}'\bm{X})/n$ 和零保持一定距离，譬如
$$ \kappa\|\bm{\Delta}\|_2^2 \leq \frac{1}{n}\|\bm{X}\bm{\Delta}\|_2^2 $$这将意味着 $\bm{\Delta}\mapsto\frac1n\|\bm{X}\bm{\Delta}\|_2^2$ 有足够的曲率（不是平坦的曲线）。我们只需要这个条件对某些 $\bm{\Delta}$ 成立，即 RE 所表述的那样。这些 $\bm{\Delta}$ 被集合 $\mathcal{C}_\alpha(S)$ 所刻画，它是这样一个集合：指标集 $S$ 所对应的那些系数要充分大于非 $S$ 对应的系数。这直觉上规定了 $S$ 和 $S^\complement$ 对应的系数值能被区分开的一类系数向量。
令 $S = \{j^*\colon\beta_j^*\neq0\}$ 是非零系数的指标集，称之为 active set，$s=|S|$ 是非零系数的个数，称之为稀疏性。在 RE 条件下，有如下定理。
Theorem 5 (Fast rate of the LASSO).
设存在某个 $\kappa>0$ 使得 $\bm{X}$ 满足 $S$ 上的 $\text{RE}(3,\kappa)$ 条件。若
$$ \lambda_n \geq \frac{2}{n}\|\bm{X}'\bm{\varepsilon}\|_\infty $$则 LASSO 估计量 $\hat{\beta}$ 满足
$$ \begin{align*} \frac{1}{n}\|\bm{X}(\hat{\bm{\beta}}-\bm{\beta}^*)\|_2^2 &\leq \frac{9s\lambda_n^2}{\kappa} \\ \|\hat{\bm{\beta}}-\bm{\beta}^*\|_2 &\leq \frac{3\sqrt{s}\lambda_n}{\kappa} \end{align*} $$首先证明，当 $\lambda_n$ 满足上述定理的条件时，有 $\hat{\bm{\Delta}}=\hat{\bm{\beta}}-\bm{\beta}^*\in\mathcal{C}_3(S)$。
因 $\hat{\bm{\beta}}$ 是最小化问题的解，有
$$ \frac{1}{2n}\|\bm{Y}-\bm{X}\hat{\bm{\beta}}\|_2^2 + \lambda_n\|\hat{\bm{\beta}}\|_1 \leq \frac{1}{2n}\|\bm{Y}-\bm{X}\bm{\beta}^*\|_2^2 + \lambda_n\|\bm{\beta}^*\|_1 $$代入 $\bm{Y} = \bm{X}\bm{\beta}^* + \bm{\varepsilon}$，整理得到
$$ 0 \leq \frac{1}{2n}\|\bm{X}\hat{\bm{\Delta}}\|_2^2 \leq \frac1n\bm{\varepsilon}'\bm{X}\hat{\bm{\Delta}} + \lambda_n(\|\bm{\beta}^*\|_1-\|\hat{\bm{\beta}}\|_1) $$根据 $S$ 的定义，$\|\bm{\beta}^*\|_1 = \|\bm{\beta}_S^*\|_1$。另外，可将 $\|\hat{\bm{\beta}}\|_1$ 写为
$$ \|\hat{\bm{\beta}}\|_1 = \|\hat{\bm{\beta}}_S\|_1 + \|\hat{\bm{\beta}}_{S^\complement}\|_1 = \|\bm{\beta}_S^*+\hat{\bm{\Delta}}_S\|_1 + \|\hat{\bm{\Delta}}_{S^\complement}\|_1 $$带入到前面的不等式得到
$$ \begin{align*} 0 \leq \frac{1}{2n}\|\bm{X}\hat{\bm{\Delta}}\|_2^2 &\leq \frac1n\bm{\varepsilon}'\bm{X}\hat{\bm{\Delta}} + \lambda_n(\|\bm{\beta}_S^*\|_1-\|\bm{\beta}_S^*+\hat{\bm{\Delta}}_S\|_1 - \|\hat{\bm{\beta}}_{S^\complement}\|_1) \\ &\leq \frac{1}{n}\|\bm{X}'\bm{\varepsilon}\|_\infty\|\hat{\bm{\Delta}}\|_1 + \lambda_n(\|\bm{\beta}_S^*\|_1-\|\bm{\beta}_S^*+\hat{\bm{\Delta}}_S\|_1 - \|\hat{\bm{\Delta}}_{S^\complement}\|_1) \\ &\leq \frac{1}{n}\|\bm{X}'\bm{\varepsilon}\|_\infty\|\hat{\bm{\Delta}}\|_1 + \lambda_n(\|\hat{\bm{\Delta}}_S\|_1 - \|\hat{\bm{\Delta}}_{S^\complement}\|_1) \\ &\leq \frac12\lambda_n\|\hat{\bm{\Delta}}\|_1 + \lambda_n(\|\hat{\bm{\Delta}}_S\|_1 - \|\hat{\bm{\Delta}}_{S^\complement}\|_1) \\ &= \frac12\lambda_n\|\hat{\bm{\Delta}}_S\|_1 + \frac12\lambda_n\|\hat{\bm{\Delta}}_{S^\complement}\|_1 + \lambda_n(\|\hat{\bm{\Delta}}_S\|_1 - \|\hat{\bm{\Delta}}_{S^\complement}\|_1) \\ &= \frac{3}{2}\lambda_n\|\hat{\bm{\Delta}}_S\|_1 - \frac12\lambda_n\|\hat{\bm{\Delta}}_{S^\complement}\|_1 \end{align*} $$第二行使用了 Hölder 不等式，第三行使用了三角不等式，第四行使用了条件 $\lambda_n \geq \frac{2}{n}\|\bm{X}'\bm{\varepsilon}\|_\infty$。这就导致了 $\|\hat{\bm{\Delta}}_{S^\complement}\|_1 \leq 3\|\hat{\bm{\Delta}}_S\|_1$，也就证明了 $\hat{\bm{\Delta}}\in\mathcal{C}_3(S)$。
第二步，我们将使用 RE 条件。注意到
$$ \lambda_n(3\|\hat{\bm{\Delta}}_S\|_1-\|\hat{\bm{\Delta}}_{S^\complement}\|_1) \leq 3\lambda_n\|\hat{\bm{\Delta}}_S\|_1 \leq 3\lambda_n\sqrt{s}\|\hat{\bm{\Delta}}_S\|_2 \leq 3\lambda_n\sqrt{s}\|\hat{\bm{\Delta}}\|_2 $$这里使用了 $\ell_1$ 和 $\ell_2$ 范数之间的关系：对 $\bm{x}\in\mathbb{R}^d$，有 $\|\bm{x}\|_2\leq\|\bm{x}\|_1\leq\sqrt{d}\|\bm{x}\|_2$，这可通过数形结合来理解。从而
$$ \begin{align*} \frac{1}{n}\|\bm{X}\hat{\bm{\Delta}}\|_2^2 &\leq \lambda_n(3\|\hat{\bm{\Delta}}_S\|_1-\|\hat{\bm{\Delta}}_{S^\complement}\|_1) \\ &\leq 3\lambda_n\sqrt{s}\|\hat{\bm{\Delta}}\|_2 \\ &\leq 3\lambda_n\sqrt{s}\frac{\|\bm{X}\hat{\bm{\Delta}}\|_2}{\sqrt{n\kappa}} \end{align*} $$最后一行用了 RE 条件。整理后就得到
$$ \frac{1}{n}\|\bm{X}\hat{\bm{\Delta}}\|_2^2 \leq \frac{9s\lambda_n^2}{\kappa} $$使用此结论和 RE 就有第二个收敛
$$ \begin{align*} \|\hat{\bm{\Delta}}\|_2 \leq \frac{\|\bm{X}\hat{\bm{\Delta}}\|_2}{\sqrt{n\kappa}} \leq \sqrt{\frac{9s\lambda_n^2}{\kappa^2}} = \frac{3\sqrt{s}\lambda_n}{\kappa} \end{align*} $$很显然，相比于 定理 1，我们把不等式右边的界的收敛速度提升了（$\lambda_n$ 提升到 $\lambda_n^2$），此外还得到了 $\|\hat{\bm{\beta}}-\bm{\beta}^*\|_2$ 的收敛，所以称之为 LASSO 的快率。
我们也可以像 推论 3 那样用概率的形式表述，这里略去。
Oracle Inequalities
Info
在英文里面，“oracle” 一词的含义是神的使者，向（愚昧）的人类传达神的旨意和预言，引申为提供智慧、知识或真理的源头。而在统计学中，这一词被借用来指代理论上所能达到的最佳表现，如同有一个神使向我们传达了真理。Oracle inequalities，「神谕不等式」，就描述了一个估计量的性能如何接近理论上最佳的性能。
我们知道，当 $p\leq n$ 且误差项 $\bm{\varepsilon}\sim N(0,\sigma^2\bm{I}_n)$ 时，OLS 是最优线性无偏估计量，它可以作为一个最优的标杆。由于 $\|\bm{X}(\hat{\bm{\beta}}^{\text{OLS}}-\bm{\beta}^*)\|_2^2/$ 服从 $\chi^2(p)$ 分布，因此期望预测误差
$$ \mathbb{E}\biggl(\frac{1}{n}\|\bm{X}(\hat{\bm{\beta}}^{\text{OLS}}-\bm{\beta}^*)\|_2^2\biggr) = \frac{\sigma^2p}{n} $$这表明，每个系数的估计精度是 $\sigma^2/n$，所以总体的估计精度就是 $(\sigma^2/n)\cdot p$。
当 $p>n$ 时，OLS 不再适用，但假设我们知道了 $\bm{\beta}^*$ 的稀疏度 $s$，按照上面的公式，能达到的最佳估计精度就应该是 $(\sigma^2/n)\cdot s$。那么，LASSO 是否达到了或接近了这一理想呢？在 前一节的定理 中，LASSO 的预测误差的界是
$$ \frac{1}{n}\|\bm{X}(\hat{\bm{\beta}}-\bm{\beta}^*)\|_2^2 \leq \frac{9s\lambda_n^2}{\kappa} $$如果我们采取前文所选取的 $\lambda_n$，那么我们就有
$$ \frac{1}{n}\|\bm{X}(\hat{\bm{\beta}}-\bm{\beta}^*)\|_2^2 \lesssim \sigma^2\frac{s\log p}{n} $$相比于理想中的最佳估计精度，我们多了一个因子 $\log p$，这可以被看作不知道哪些系数非零所付出的成本。这就是 LASSO 的神谕不等式。
参考
Alessandro Rinaldo’s Lecture Notes (2018): Oct 17, Oct 22.
Honglang Wang’s Tutorial on Lasso.
Bühlmann, Peter, and Sara van de Geer (2011). Statistics for High-Dimensional Data: Methods, Theory and Applications. Springer Science & Business Media.
Rigollet, Philippe, and Jan-Christian Hütter (2023). “High-Dimensional Statistics.” arXiv preprint. arXiv:2310.19244.
最后修改于 2024-09-06