[1512.04202] Preconditioned Stochastic Gradient Descent

Abstract:Stochastic gradient descent (SGD) still is the workhorse for many practical problems. However, it converges slow, and can be difficult to tune. It is possible to precondition SGD to accelerate its convergence remarkably. But many attempts in this direction either aim at solving specialized problems, or result in significantly more complicated methods than SGD. This paper proposes a new method to estimate a preconditioner such that the amplitudes of perturbations of preconditioned stochastic gradient match that of the perturbations of parameters to be optimized in a way comparable to Newton method for deterministic optimization. Unlike the preconditioners based on secant equation fitting as done in deterministic quasi-Newton methods, which assume positive definite Hessian and approximate its inverse, the new preconditioner works equally well for both convex and non-convex optimizations with exact or noisy gradients. When stochastic gradient is used, it can naturally damp the gradient noise to stabilize SGD. Efficient preconditioner estimation methods are developed, and with reasonable simplifications, they are applicable to large scaled problems. Experimental results demonstrate that equipped with the new preconditioner, without any tuning effort, preconditioned SGD can efficiently solve many challenging problems like the training of a deep neural network or a recurrent neural network requiring extremely long term memories.

Preconditioned Stochastic Gradient Descent Stochastic gradient descent (SGD) still is the workhorse for many practical problems. However, it converges slow, and can be difficult to tune. It is possible to precondition SGD to accelerate its convergence remarkably. But many attempts in this direction either aim at solving specialized problems, or result in significantly more complicated methods than SGD. This paper proposes a new method to estimate a preconditioner such that the amplitudes of perturbations of preconditioned stochastic gradient match that of the perturbations of parameters to be

saved by

• Jaisel Singh

related reading

• [2502.01131] Simple Linear Neuron Boostingarxiv.org
• Ji-Ha's Blogjiha-kim.github.io
• Stochastic gradient descent - Wikipediaen.m.wikipedia.org
• [1802.09568] Shampoo: Preconditioned Stochastic Tensor Optimizationar5iv.labs.arxiv.org
• Online KL Shampoo | Tildeblog.tilderesearch.com
• Muon: An optimizer for hidden layers in neural networks | Keller Jordan blogkellerjordan.github.io
• Deriving Muonjeremybernste.in
• Stochastic Modified Equations and Dynamics of Stochastic Gradient Algorithms I: Mathematical Foundationsjmlr.org
• [1511.06251] Stochastic modified equations and adaptive stochastic gradient algorithmsarxiv.org
• Why Momentum Really Worksdistill.pub
• Scalable Gradients for Stochastic Differential Equationsarxiv.org
• An overview of gradient descent optimization algorithmsruder.io