We present EGN, a stochastic second-order optimization algorithm that
combines the generalized Gauss-Newton (GN) Hessian approximation with low-rank
linear algebra to compute the descent direction. Leveraging the Duncan-Guttman
matrix identity, the parameter update is obtained by factorizing a matrix which
has the size of the mini-batch. This is particularly advantageous for
large-scale machine learning problems where the dimension of the neural network
parameter vector is several orders of magnitude larger than the batch size.
Additionally, we show how improvements such as line search, adaptive
regularization, and momentum can be seamlessly added to EGN to further
accelerate the algorithm. Moreover, under mild assumptions, we prove that our
algorithm converges to an $\epsilon$-stationary point at a linear rate.
Finally, our numerical experiments demonstrate that EGN consistently exceeds,
or at most matches the generalization performance of well-tuned SGD, Adam, and
SGN optimizers across various supervised and reinforcement learning tasks.

我们介绍了 EGN，一种随机二阶优化算法，将广义高斯 - 牛顿（GN）Hessian 近似与低秩线性代数相结合，计算下降方向。借助 Duncan-Guttman 矩阵恒等式，通过分解一个与小批次大小相同的矩阵来获得参数更新，这在维度远超批次大小的大规模机器学习问题中特别有优势。此外，我们展示了如何将线搜索、自适应正则化和动量等改进无缝地添加到 EGN 中以进一步加速算法。此外，在温和假设下，我们证明了我们的算法以线性速率收敛到一个 ε- 稳定点。最后，我们的数值实验表明，在各种监督学习和强化学习任务中，EGN 始终超过或最多与 SGD、Adam 和 SGN 等优化器的泛化性能相匹配。