则称 f 为区间 [a,b] 上的凸函数 (convex function)。当 通常是凸函数。
2 线性回归
2.1 建模流程
线性回归 (linear regression) 回归问题
。其建模方法包括如下三步 (参见第 1.1 节)。
(1). 对 p(y | x; θ) 进行概率假设。
我们假设
被称为误差项，捕获了 (a)。特征向量 x 中没有包含的因素.
(b). 随机噪声。对不同的样本
是独立同分布地从中
进行采样得到的。
线性回归的假设函数是
为了书写方便，我们记
那么公式 12 等价于
在本文其余部分我们将沿用这一简化记号。因此，
(2). 对参数 θ 进行最大后验估计。
定理 7. 假设参数 θ 服从高斯先验，对参数 θ 进行最大后验估计等价于最小化如下损失函数
其中
被称为平方损失 (square loss)。在线性回归中，平方损失就是试图找到一个超平面
，使所有样本到该超平面的欧式距离 (Euclidean distance) 之和最小。
Proof
其中，最后一行只是为了数学计算上方便，下文推导对数几率回归和 Softmax 回归时的最后一步亦然。
(3). 对损失函数 L(θ) 进行梯度下降优化。
可以容易地得到损失函数对参数的偏导数
2.2 线性回归的闭式解
线性回归对应的平方损失的函数形式比较简单，可以通过求
直接得到最优解。
定理 8. 线性回归的闭式解为
Proof. L(θ) 可等价地写作
令
那么
求解
即得。
不可逆的情况及解决方案? (1). 属性数 d 1 多于样例数 m。(2). 属性之间线性相关。通过正则化项
mλI，即使
不可逆，
mλI 仍是可逆的。
2.3 其他正则化回归模型
事实上，上文介绍的线性回归模型是岭回归 (ridge regression)。根据正则化项的不同，有三种常用的线性回归模型，见表 1。
基于 ℓ0、ℓ1 和 ℓ2 范数正则化的效果? ℓ2 范数倾向于 w 的分量取值尽量均衡，即非零分量个数尽量稠密。而 ℓ0“范数”和 ℓ1 范数则倾向于 w 的分量尽量稀疏，即非零分量个数尽量少，优化结果得到了仅采用一部分属性的模型。也就是说，基于 ℓ0“范数”和 ℓ1 范数正则化的学习方法是一种嵌入式 (embedding) 特征选择方法，其特征选择过程和学习器训练过程融为一体，两者在同一个优化过程中完成。事实上，对 w 施加稀疏约束最自然的是使用 ℓ0“范数”。但 ℓ0“范数”不连续，难以优化求解。因此常采用 ℓ1 范数来近似。
为什么 ℓ1 正则化比 ℓ2 正则化更易于获得稀疏解？假设
，则
。我们绘制出平方损失项、ℓ1 范数和 ℓ2 范数的等值线 (取值相同的点的连线)，如图 1 所示。LASSO 的解要在平方损失项和正则化项之间折中，即出现在图中平方误差项等值线和正则化项等值线的相交处。从图中可以看出，采用 ℓ1 正则化时交点常出现在坐标轴上 (w2= 0), 而采用 ℓ2 正则化时交点常出现在某个象限中 (w1，w2均不为 0)。
Figure 1: ℓ1 正则化 (红色) 比 ℓ2 正则化 (黑色) 更易于获得稀疏解。本图源于 [17]。
考虑一般的带有 ℓ1 正则化的优化目标
若 ℓ(θ) 满足 L-Lipschitz 条件，即
优化通常使用近端梯度下降 (proximal gradient descent, PGD) [1]。PGD 也是一种贪心地迭代式地最小化策略，能快速地求解基于 ℓ1 范数最小化的方法。
定理 9. 假设当前参数是
，PGD 的更新准则是
其中
Proof. 在
附近将 ℓ(θ) 进行二阶泰勒展开近似
