Definition
AdaDelta is an adaptive optimizer that scales each parameter's gradient by . Both are exponential moving averages: one of past updates, one of past gradients. The ratio stands in for a per-parameter learning rate, so the method has no global step size .
Matthew Zeiler introduced AdaDelta in a 2012 arXiv note, ADADELTA: An Adaptive Learning Rate Method. He wanted to fix two things about AdaGrad (Duchi, Hazan and Singer, 2011). First, AdaGrad divides by the square root of a sum of all past squared gradients, so its effective learning rate can only fall and training eventually stalls. Second, AdaGrad still needs a hand-tuned global learning rate.
AdaDelta fixes the first problem the same way RMSProp does: it replaces the growing sum with a decaying average. For the second, it uses a units argument. The update has the units of a gradient, not of the parameter. Newton's step does have the parameter's units, and AdaDelta builds a cheap diagonal stand-in for out of quantities it already tracks.
The update rule
- the gradient at step ; every operation is element-wise, one copy per parameter
- decaying average of squared gradients (RMSProp's accumulator); starts at 0
- decaying average of squared updates; starts at 0
- decay rate. Zeiler used 0.95 on MNIST; PyTorch's default is 0.9
- added inside both square roots. Zeiler used on MNIST, which is also PyTorch's default
The numerator uses because is not known until the step has been computed. That lag is also what makes AdaDelta start slowly: at the numerator is .
PyTorch's torch.optim.Adadelta adds one knob the paper does not have: lr (default 1.0) multiplies just before it is applied. The accumulator still stores the unscaled . With lr=1.0 you get the paper's method. Keras's Adadelta defaults to learning_rate=0.001, so you have to pass 1.0 explicitly to get the original algorithm.
At a glance
- Paper
- Zeiler, arXiv:1212.5701 (Dec 2012)
- State per parameter
- two tensors, and : the same memory as Adam
- Hyperparameters
- and ; PyTorch adds an
lrmultiplier (default 1.0) - Units of the step
- those of (if is negligible), unlike SGD, AdaGrad and RMSProp
- First step
- for any gradient with : at the defaults
- PyTorch
torch.optim.Adadelta(params, lr=1.0, rho=0.9, eps=1e-6, weight_decay=0)
Where the ratio comes from: a units argument
Give the unit "metres" and treat the loss as unitless. Then is in 1/metres, and an SGD step is in 1/metres too unless is in metres². The learning rate quietly carries the conversion. AdaGrad and RMSProp divide by an RMS of , so their step is unitless, and again has to supply the metres.
Newton's method gets the units right on its own. Its step divides 1/metres by 1/metres², which gives metres. Rearranging Newton's step gives an expression for the inverse curvature that uses only first-order quantities:
- the diagonal curvature, which AdaDelta never computes
- a running estimate of inverse curvature, in metres per (1/metre)
So AdaDelta is "RMSProp whose learning rate is ". Where the updates have recently been large, it keeps taking large steps. Where the gradient RMS is large (a steep direction), it shrinks them. The argument is a heuristic. The ratio is a crude, lagged, diagonal estimate, not a real Hessian, and it is only unit-correct when is small next to both averages.
ε is the hidden learning rate
Look at the first step. , so the numerator is , and . For any gradient with :
- for ; for Zeiler's
The first step does not depend on the gradient's size at all, only on and . It is measured in the parameter's own units, so the same is a tiny step for a weight of order 100 and a huge one for a weight of order 0.01. After that, can only grow as fast as the steps feed it. Under a constant gradient the step grows roughly like , that is, like the square root of the step count.
Hence the figure's units buttons. Rescale the parameters by and the gradients scale by . As long as the denominator's stays small next to , nothing changes there, but the numerator's now behaves like in the original units. A model whose weights are of order 0.01 sees PyTorch's default as if it were . "No learning rate" really means "a learning rate written as , in units of ".
Worked example: a constant gradient
One parameter, gradient at every step, . Iterating the four lines of the update rule gives (checked in Node):
| step t | (ε = 1e-6) | step (ε = 1e-6) | step (ε = 1e-2) | |
|---|---|---|---|---|
| 1 | 0.100 | 0.00100 | 0.00316 | 0.302 |
| 2 | 0.190 | 0.00141 | 0.00324 | 0.309 |
| 3 | 0.271 | 0.00172 | 0.00330 | 0.314 |
| 10 | 0.651 | 0.00283 | 0.00351 | 0.334 |
| 100 | 1.000 | 0.00466 | 0.00466 | 0.436 |
| 1000 | 1.000 | 0.0106 | 0.0106 | 0.817 |
Step 1 at the PyTorch defaults
- 1, so .
- 2.
- 3.
- 4. The numerator for step 2 is , so the step barely grows.
- 5After 1000 steps the parameter has moved in total. With it moves . The gradient was identical in both runs; only differed.
Near a minimum the ratio drifts to 1
As the gradients shrink, both averages decay toward 0 and both square roots approach , so the multiplier approaches , times PyTorch's lr. AdaDelta then behaves like plain gradient descent with step 1. That step is unstable in any direction with curvature above 2. In the figure's steep direction (curvature 25) the iterate starts to oscillate until grows enough to pull the ratio back to the edge of stability, . With noisy minibatch gradients never decays to 0, which hides the effect. When it does show up, decaying PyTorch's lr multiplier with a schedule removes it.
1import torch23# The paper's method is lr=1.0 (PyTorch's default). Keras defaults to learning_rate=0.001.4opt = torch.optim.Adadelta(model.parameters(), lr=1.0, rho=0.9, eps=1e-6)56# One parameter under a constant gradient of 1: the first step is sqrt(eps / (1 - rho)).7p = torch.zeros(1, requires_grad=True)8opt = torch.optim.Adadelta([p], lr=1.0, rho=0.9, eps=1e-6)9for t in range(1000):10 opt.zero_grad()11 p.sum().backward() # dL/dp = 112 opt.step()13 if t == 0:14 print(p.item()) # about -0.0031615print(p.item()) # about -7.6 after 1000 steps1617# The update, written out (all element-wise)18@torch.no_grad()19def adadelta_step(p, g, sq, acc, rho=0.9, eps=1e-6, lr=1.0):20 sq.mul_(rho).addcmul_(g, g, value=1 - rho) # E[g^2]21 delta = (acc + eps).sqrt() / (sq + eps).sqrt() * g # RMS[dθ]_{t-1} / RMS[g]_t * g22 acc.mul_(rho).addcmul_(delta, delta, value=1 - rho) # E[dθ^2], unscaled by lr23 p.sub_(lr * delta)Use when
- +No global learning rate to tune in the paper's form; reasonable defaults often train
- +Decaying averages: unlike AdaGrad, the effective step does not shrink to zero
- +Unit-consistent step (when ε is small), loosely mimicking a diagonal Newton step
- +Starts with small steps by construction, a built-in warm-up
Avoid when
- − secretly sets the step scale in parameter units, so it must be tuned to the parameters' magnitude
- −Slow start: the step grows roughly like from
- −No momentum, and with full-batch gradients the ratio drifts to 1 near a minimum and can oscillate
- −Two state tensors per parameter (as much as Adam) with no momentum term to show for it
Check yourself
AdaDelta (PyTorch defaults ρ = 0.9, ε = 1e-6, lr = 1) takes its first step on a parameter whose gradient is 50. About how big is the step?
Check yourself
Why does AdaDelta put RMS[Δθ] in the numerator of its per-parameter rate?
Remember
- ✓Update: , with decaying averages of squared gradients and squared updates.
- ✓It fixes AdaGrad's ever-shrinking step, like RMSProp, and drops the global learning rate with a units argument from Newton's method.
- ✓ sits inside both square roots and sets the first step, (0.0032 at the defaults), in the parameter's own units.
- ✓Rescaling the parameters by acts like changing the numerator's to : tune to the weights' magnitude.
- ✓PyTorch: Adadelta(lr=1.0, rho=0.9, eps=1e-6); lr is an extra multiplier. Keras defaults to 0.001, so pass 1.0 for the paper's method.