Second-order optimization algorithms exhibit excellent convergence properties
for training deep learning models, but often incur significant computation and
memory overheads. This can result in lower training efficiency than the
first-order counterparts such as stochastic gradient descent (SGD). In this
work, we present a memory- and time-efficient second-order algorithm named Eva
with two novel techniques: 1) we construct the second-order information with
the Kronecker factorization of small stochastic vectors over a mini-batch of
training data to reduce memory consumption, and 2) we derive an efficient
update formula without explicitly computing the inverse of matrices using the
Sherman-Morrison formula. We further extend Eva to a general vectorized
approximation framework to improve the compute and memory efficiency of two
existing second-order algorithms (FOOF and Shampoo) without affecting their
convergence performance. Extensive experimental results on different models and
datasets show that Eva reduces the end-to-end training time up to 2.05x and
2.42x compared to first-order SGD and second-order algorithms (K-FAC and
Shampoo), respectively.

我们提出了一种记忆和时间高效的二阶算法 Eva，通过使用小批量训练数据的 Kronecker 因式分解构建二阶信息以减少内存消耗，并使用 Sherman-Morrison 公式推导出高效的更新公式，将 Eva 扩展为通用的向量化近似框架以提高现有二阶算法（FOOF 和 Shampoo）的计算和内存效率。在不影响收敛性能的情况下，对不同模型和数据集进行的广泛实验结果表明，与一阶 SGD 和二阶算法（K-FAC 和 Shampoo）相比，Eva 可将端到端训练时间减少 2.05 倍和 2.42 倍。