  We present a novel approach to accelerate stochastic gradient descent (SGD)
by utilizing curvature information obtained from Hessian-vector products or
finite differences of parameters and gradients, similar to the BFGS algorithm.
Our approach involves two preconditioners: a matrix-free preconditioner and a
low-rank approximation preconditioner. We update both preconditioners online
using a criterion that is robust to stochastic gradient noise and does not
require line search or damping. To preserve the corresponding symmetry or
invariance, our preconditioners are constrained to certain connected Lie
groups. The Lie group's equivariance property simplifies the preconditioner
fitting process, while its invariance property eliminates the need for damping,
which is commonly required in second-order optimizers. As a result, the
learning rate for parameter updating and the step size for preconditioner
fitting are naturally normalized, and their default values work well in most
scenarios. Our proposed approach offers a promising direction for improving the
convergence of SGD with low computational overhead. We demonstrate that
Preconditioned SGD (PSGD) outperforms SoTA on Vision, NLP, and RL tasks across
multiple modern deep-learning architectures. We have provided code for
reproducing toy and large scale experiments in this paper.
