Second-order Information Promotes Mini-Batch Robustness in Variance-Reduced Gradients

我们展示了对于有限和最小化问题，将目标函数的部分二阶信息纳入可以显著提高方差减少随机梯度方法对小批量大小的鲁棒性，使它们更具可伸缩性，同时保留它们相对于传统牛顿类型方法的优势。我们在一个典型的随机二阶算法上展示了这种现象，称为小批量随机方差减少牛顿法（$\texttt{Mb-SVRN}$），它将方差减少的梯度估计与近似的黑塞矩阵预测相结合。特别地，我们展示了当数据大小$n$足够大，即$n\gg \alpha^2\kappa$，其中$\kappa$是条件数，$\alpha$是黑塞矩阵近似因子时，$\texttt{Mb-SVRN}$实现了快速线性收敛速度，该速度独立于梯度小批量大小$b$，只要$b$在$1$和$b_{\max}=O(n/(\alpha \log n))$之间。只有当增加小批量大小超过这个临界点$b_{\max}$时，该方法才开始过渡到标准牛顿类型算法，后者对黑塞矩阵近似质量更为敏感。我们在基准优化任务上通过实证展示了这种现象，表明在调整步长后，$\texttt{Mb-SVRN}$的收敛速度在一定范围的小批量大小内仍然很快，并且相位转换点$b_{\max}$对黑塞矩阵近似因子$\alpha$的依赖与我们的理论预测相一致。

本文旨在解决有限和最小化问题中，如何利用目标函数的二阶信息来改善小批量随机梯度方法的鲁棒性和可扩展性的问题。同时，验证假设：在数据量足够大的情况下，小批量随机梯度方法可以实现快速线性收敛，且独立于梯度小批量大小。

本文提出了一种基于随机二阶算法的小批量随机方差规约牛顿方法（$ exttt{Mb-SVRN}$），将方差规约梯度估计与近似Hessian Oracle相结合。在数据量足够大的情况下，该方法可以实现快速线性收敛，且独立于梯度小批量大小，同时对Hessian近似质量的敏感度较低。

实验结果表明，本文提出的$ exttt{Mb-SVRN}$方法在广泛的小批量大小范围内都能够实现快速收敛，且相比于传统的牛顿类型算法，对Hessian近似质量的敏感度较低。此外，本文所提出的方法在多个基准优化任务中都表现出优异的性能。同时，本文还提供了开源代码。

最近的相关研究包括：使用二阶信息的优化算法，以及小批量随机梯度方法的改进。其中，部分研究者提出了基于二阶信息的优化算法，但是这些方法的计算成本较高。而本文所提出的方法通过结合方差规约梯度估计和近似Hessian Oracle，实现了较低的计算成本和较高的鲁棒性。