Double Descent in Linear Regression
Published:
Paper Reading: Two models of double descent for weak features.
Double Descent 现象近期得到更多关注，该论文通过给出分析了线性回归模型中的泛化误差解释该现象。原论文给出了两个模型，包括高斯模型和傅里叶特征模型，本博文只介绍更常见的高斯模型。
Introduction
考虑经典的线性回归模型，假设噪声来自独立零均值的正态分布，特征来自标准正态分布，
\[\begin{align*} y = x^\top \beta + \epsilon, \quad x \sim \mathcal{N} (0,I_p), \quad \epsilon \sim \mathcal{N} (0, \sigma^2 ). \end{align*}\]从分布中随机抽取 $n$ 个数据，构成数据集 $X \in \mathbb{R}^{n \times p}$. 使用最小范数最小二乘解得到系数的估计 $\hat \beta = X^{\dagger} y.$,
当 $p \le n$ 时假设 $X^\top X$ 满秩； 当 $ p > n$ 时假设 $XX^\top $ 满秩。则估计可以写为，
\[\begin{align*} \hat \beta = \begin{cases} (X^\top X)^{-1} X^\top y , & p \le n \\ X^\top (XX^\top)^{-1 } y , & p > n . \end{cases} \end{align*}\]我们关心泛化风险
\[\begin{align*} R(\hat \beta) &= \mathbb{E}_{(x, y) \sim \mathcal{D}, (X,y) \in \mathcal{D}}[ (x^\top \hat \beta - y )^2 - (x^\top \beta -y)^2 ] \\ &= \mathbb{E}_{(x,\epsilon) \sim \mathcal{D} ,(X,y) \in \mathcal{D}} [ (x^\top \hat \beta - x^\top \beta - \epsilon )^2 - \epsilon^2 ] \\ &=\mathbb{E}_{x \sim \mathcal{D}, (X,y) \in \mathcal{D}} [ (x^\top \hat \beta - x^\top \beta )^2 ] \\ &= \mathbb{E}_{x \sim \mathcal{D} ,(X,y) \in \mathcal{D}} [ (\hat \beta - \beta)^\top xx^\top ( \hat \beta - \beta) ] \\ &= \mathbb{E}_{(X,y) \in \mathcal{D}} [ (\hat \beta - \beta)^\top \mathbb{E}_{x \sim \mathcal{D}} [xx^\top] ( \hat \beta - \beta) ] \\ &= \mathbb{E}_{(X,y) \sim \mathcal{D} } [ \Vert \hat \beta - \beta \Vert^2]. \end{align*}\]根据偏差-方差分解，泛化风险由偏差项和方差项共同构成。根据 $p,n$ 不同的大小关系，泛化风险的来源并不相同。
注意到 $p \le n$ 的时候，$\hat \beta$ 为参数的无偏估计，泛化风险来自于方差
而当 $p > n$ 的时候， $\hat \beta$ 不再具有无偏性，但却可以完全拟合数据，也被称为插值性。
Under-Parameterized Setting
考虑 $p \le n $ 的情况，
\[\begin{align*} R(\hat \beta) &= \mathbb{E}_{(X,y) \sim \mathcal{D} } [ \Vert \hat \beta - \beta \Vert^2] \\ &= \mathbb{E}_{(X,y) \sim \mathcal{D} } [ \Vert (X^\top X)^{-1} X^\top y - \beta \Vert^2] \\ &= \mathbb{E}_{(X,\epsilon) \sim \mathcal{D} } [ \Vert (X^\top X)^{-1} X^\top (X \beta + \epsilon) - \beta \Vert^2] \\ &=\mathbb{E}_{(X,\epsilon) \sim \mathcal{D} } [ \Vert (X^\top X)^{-1} X^\top \epsilon \Vert^2] \\ &= \mathbb{E}_{(X,\epsilon) \sim \mathcal{D} } {\rm tr} (\epsilon^\top X(X^\top X)^{-1} (X^\top X)^{-1} X^\top \epsilon ) \\ &=\mathbb{E}_{(X,\epsilon) \sim \mathcal{D} } {\rm tr} (X(X^\top X)^{-1} (X^\top X)^{-1} X^\top \epsilon \epsilon^\top ) \\ &= \sigma^2 \mathbb{E}_{X \sim \mathcal{D} } {\rm tr} (X(X^\top X)^{-1} (X^\top X)^{-1} X^\top ) \\ &= \sigma^2 \mathbb{E}_{X \sim \mathcal{D} } {\rm tr} ((X^\top X)^{-1}) \\ &= \frac{\sigma^2}{n-p-1} {\rm tr} (I_p) \\ &= \frac{\sigma^2 p}{n-p-1} \mathbb{I} [ p \le n-2]. \end{align*}\]最后一步使用了逆Wishart分布的期望，参见 逆Wishart分布的期望的证明
绘制出风险关于 $p$ 的图像，可以发现呈现经典的 U 型曲线： 先下降后上升，也即先欠拟合后过拟合。
Over-Parameterized Setting
当 $p >n $ 的情况，由于估计不再具有无偏性，风险将由两项构成。
其中方差项的计算，与 $p <n$ 的情况类似，利用逆Wishart分布即可。不过此时逆Wishart分布中 $n,p$ 的地位互换。
而偏差，可以利用随机投影的期望计算，令 $\Pi_X = X^\top (XX^\top ) X$.
当 $X$ 的每一个元素来自标准正态分布时，$\Pi_X$ 形成一个从$p$ 维空间向 $n$ 维空间的随机投影，因此满足
\[\begin{align*} \Vert \Pi_X \beta \Vert^2 = \frac{n}{p} \Vert \beta \Vert^2. \end{align*}\]该部分的证明可以参见 StackExchange上的回答, 据此我们可以得到
\[\begin{align*} R(\hat \beta) &= \mathbb{E}_{(X,y) \sim \mathcal{D} } [ \Vert \hat \beta - \beta \Vert^2] \\ &= \mathbb{E}_{(X,y) \sim \mathcal{D} } [ \Vert X^\top (X X^\top )^{-1} y - \beta \Vert^2] \\ &= \mathbb{E}_{(X,\epsilon) \sim \mathcal{D} } [ \Vert X^\top (X X^\top )^{-1} (X \beta +\epsilon) - \beta \Vert^2] \\ &= \mathbb{E}_{(X,\epsilon) \sim \mathcal{D} } [ \Vert (I- X^\top (XX^\top)^{-1} X ) \beta \Vert^2] + \mathbb{E}_{(X,\epsilon) \sim \mathcal{D} } [ \Vert X^\top (XX^\top )^{-1} \epsilon \Vert^2] \\ &= \mathbb{E}_{X \sim \mathcal{D} } [ \Vert (I- \Pi_X) \beta \Vert^2] + \mathbb{E}_{(X,\epsilon) \sim \mathcal{D} } {\rm tr} ( \epsilon^\top (XX^\top)^{-1} \epsilon ) \\ &= \Vert \beta \Vert^2 - \mathbb{E}_{X \sim \mathcal{D} } [ \Vert\Pi_X \beta \Vert^2] + \sigma^2 \mathbb{E}_{X \sim \mathcal{D} } {\rm tr} ((XX^\top)^{-1}) \\ &= \frac{\Vert \beta \Vert^2 (n-p)}{p} + \frac{\sigma^2 n }{ p - n -1} \mathbb{E}[ p \ge n+2]. \end{align*}\]可以发现对于过参数化的情况，当信噪比 $\Vert \beta \Vert^2 / \sigma^2$ 满足一定条件时，泛化误差可以呈现随着参数增多单调下降。
此时虽然在数据集上每一点都完全拟合，但却并不会出现过拟合的现象。
综上两种 $n,p$ 不同的情况，可以刻画该模型下的Double Descent现象。
原论文还讨论了随机选择特征子集下的泛化风险，以及傅里叶特征下的情况。