原文地址: https://www.jmlr.org/papers/volume9/lin08b/lin08b.pdf
该文提出了训练大型逻辑回归问题的新算法：置信域牛顿法(Trust Region Newton Method)，并通过实验证明了该算法效率比常用的拟牛顿法更高，同时也将该算法应用到L2-SVM的求解上。
问题引入
先来看带L2正则化的逻辑回归：
\[\min_{\pmb w}\quad f(\pmb w)=\frac12\pmb w^T\pmb w+C\sum_{i=1}^l\log(1+\exp(-y_i\pmb w^T\pmb x_i))\]这是一个无约束优化问题。求梯度：
\[\nabla f(\pmb w)=\pmb w+C\sum_{i=1}^l(\sigma(y_i\pmb w^T\pmb x_i)-1)y_i\pmb x_i\]其中
\[\sigma(x)=(1+\exp(-x))^{-1}\]再求二阶导(Hessian矩阵)：
\[\nabla^2 f(\pmb w)=I+CX^TDX\]$D$是一个对角矩阵:
\[D_{ii}=\sigma(y_i\pmb w_i^T\pmb x_i)(1-\sigma(y_i\pmb w_i^T\pmb x_i))\]这是因为
\[\begin{aligned} f(\pmb w)&=\log(1+\exp(-y_i\pmb w^T\pmb x))\\ \dfrac{\partial f}{\partial\pmb w}&=\frac{1}{1+\exp(-y_i\pmb w^T\pmb x)}\dfrac{\partial }{\partial\pmb w}(1+\exp(-y_i\pmb w^T\pmb x))\\ &=-y_i\pmb x_i\frac{\exp(-y_i\pmb w^T\pmb x)}{1+\exp(-y_i\pmb w^T\pmb x)}\\ &=(\sigma(y_i\pmb w^T\pmb x)-1)y_i\pmb x_i \end{aligned}\]$X$是数据集矩阵，即$l\times n$矩阵。显然Hessian矩阵是正定的，因此上述的优化问题是强凸的，我们可以证明下面的定理：
\[上述优化问题必有一个唯一的全局最优解\]牛顿法的思想是基于下面的迭代：
\[\pmb{w}^{k+1}=\pmb{w}^k+\pmb s^k\]其中
\[\nabla^2 f (\pmb w^k)s^k=-\nabla f(\pmb w^k)\]因为Hessian矩阵始终可逆，因此保证了牛顿法的可行性。但该算法有两个问题：
- 序列$\{\pmb w^k\}$不一定会收敛到一个最优解，甚至不能保证目标函数是递减的；
- 尽管我们假设数据集$X$是稀疏的，但$X^TDX$还是比较稠密。黑塞矩阵将会变得很大而难以存储，因此求解上面的线性方程组的方法需要认真考虑。
通过调整牛顿步径，我们可以解决第一个问题，通常采用两种方法：线搜索和置信域；而对于第二个问题，解线性方程组(也称作线性系统：Linear systems)也有两种方法：直接法和迭代法。直接法的代表就是高斯消元法，Jacobi法和共轭梯度法都属于迭代法。迭代法最主要的操作就是计算矩阵（也就是黑塞矩阵）和向量的乘积:
\[\begin{aligned} \nabla^2f(\pmb w)&=(I+CX^TDX)\pmb s\\ &=\pmb s+CX^T(D(X\pmb s)) \end{aligned}\]考虑$X$稀疏，那么上式就可以很高效地计算出来而不需要存储整个黑塞矩阵。相比于直接法要存储黑塞矩阵，迭代法无疑是更好的选择。作者选择了共轭梯度法作为求解牛顿方向的间接法。不幸的是，共轭梯度法在某些情况下不容易收敛。因此为了节省时间，作者会在收敛之前便从共轭梯度法中获取解，作为近似的牛顿方向，这种方法也被称作截断牛顿法(Truncated Newton Method)。
置信域牛顿法
我们在https://welts.xyz/2021/12/18/tr/中对一般置信域方法进行了分析，这里的置信域算法只在更新置信域半径时有少许差异，在此不做过多赘述。求解上面的置信域子问题中用到了共轭梯度法，笔者在https://welts.xyz/2021/12/19/cg/中对共轭梯度法进行了详细的证明，本文的共轭梯度法：
注意到共轭梯度法中，我们只需要进行一次黑塞矩阵与向量的乘积运算（实际上是两次，但是可以通过保存第一次的计算结果以避免第二次计算）。
同时，我们也注意到该算法与标准的共轭梯度法的区别：该算法需要保持$\pmb s_k\leq\Delta_k$，这是来自置信域算法的要求，所以才会多出计算$\tau$那一步。
改进的共轭梯度法
Preconditioned Conjugate Gradient法对共轭梯度法进行了改进，正如名字中的”preconditioned”，算法会进行一个矩阵分解的预处理：
\[\nabla^2f(\pmb w)\approx PP^T\]然后解一个新的线性系统：
\[(P^{-1}\nabla^2f(\pmb w_k)P^{-T})\hat{\pmb s}=-P^{-1}\nabla f(\pmb w^k),\hat{\pmb s}=P^T\pmb s\]如果上面的矩阵分解效果很好，那么$P^{-1}\nabla^2f(\pmb w^k)P^{-T}$就会很接近一个单位矩阵，从而减少迭代数。作者采用了简单的处理方式
\[P=P^T=\sqrt{\text{Diag}(\nabla^2f(\pmb w_k))}\]得到改进的共轭梯度法：
L2-SVM下的置信域牛顿法
L2-SVM求解的是下面的优化问题
\[\min_{\pmb w}\quad f_2(\pmb w)=\frac12\pmb w^T\pmb w+C\sum_{i=1}^l(\max(0,1-y_i\pmb w^T\pmb x_i))^2\]这里的损失函数实是一阶可微且强凸的，因此存在理论上全局最小值。我们先算$f_2$的梯度:
\[\nabla f_2(\pmb w)=(I+2CX^T_{I,:}X_{I,:})\pmb w-2CX_{I,:}^T\pmb y_I\]其中
\[I=\{i\vert1-y_i\pmb w^T\pmb x_i>0\}\]也就是说，$I$是一个下标集合，$X_{I,:}$就是取下标集对应的行形成的新矩阵。这一点不难理解，因为对于函数$\max(0,t)^2$，如果自变量小于0，求出的导数始终为0。
$\max$运算的存在使得$f_2$不是二阶可微的，但我们发现$f_2$是几乎处处二阶可微的。因为其梯度是Lipschitz连续的，所以我们可以利用次梯度定义出近似的黑塞矩阵（次梯度的概念可参考次梯度求解Lasso回归）:
\[B(\pmb w)=I+2CX^TDX\]其中$D$是对角矩阵，对角元是对应的次梯度：
\[D_{ii}=\begin{cases} 1&\text{if }1-y_i\pmb w^T\pmb x_i>0,\\ \text{any element in }[0,1]&\text{if }1-y_i\pmb w^T\pmb x_i=0,\\ 0&\text{if }1-y_i\pmb w^T\pmb x_i<0.\\ \end{cases}\]由此，对于前面的置信域牛顿法，我们只需要将$\nabla^2f(\pmb w)$替换成$B(\pmb w)$，就可以将该方法应用到L2-SVM的求解上。类似的，共轭梯度法求解的是下面的线性系统：
\[B(\pmb w)\pmb s=s+2CX_{I,:}^T(D_{I,I}(X_{I:,}\pmb s))\]改进的L2-SVM牛顿法
Keerthi和DeCoste在2005年提出一种很有效的方式来训练L2-SVM，它的核心思想是，对于任意的集合$I\subset\{1,\cdots,l\}$，如果$\pmb w^*$是问题
\[\min_{\pmb w}\quad\frac12\pmb w^T\pmb w+C\sum_{i\in I}(1-y_i\pmb w^T\pmb x_i)^2\]的最优解，且满足
\[1-\pmb y_i(\pmb w^*)^T\pmb x_i\begin{cases} >0&\text{if }i\in I\\ \leq0&\text{if }i\notin I \end{cases}\]那么$\pmb w^*$就是对应L2-SVM的最优解。一旦$I$被固定，那么上述问题就是简单的最小二乘问题，问题的解就是下面这个线性系统的解：
\[(I+2CX_{I,:}^TX_{I,:})\pmb w=2CX_{I,：}^T\pmb y_{I}\]完整算法：
