Adaptive Learning Rate Algorithm (AdaDelta)

An Adaptive Learning Rate Algorithm (AdaDelta) is a Gradient Descent-based Learning Algorithm that uses the exponential decay rate of the first- and second-order moments.

• AKA: AdaDelta, AdaDelta Optimizer, AdaDelta Algorithm.
• Context:
  • It (typically) doesn't require manual tuning of a learning rate.
  • …
• Example(s):
  • torch.optim.Adadelta [1],
  • chainer.optimizers.AdaDelta [2]
  • tflearn.optimizers.AdaDelta [3]
  • ADADELTA from CRAN gradDescent Repository [4],
  • AdaDelta in Deeplearning4j [5],
• Counter-Example(s):
  • an Accelerated Gradient Descent (AGD),
  • an Adaptive Gradient Algorithm (AdaGrad),
  • an Adaptive Moment Estimation Algorithm (Adam),
  • a Mini-Batch Gradient Descent Algorithm (MBGD).
  • a Momentum Gradient Descent (MGD),
  • a Root Mean Square Propagation Algorithm (RMSprop),
  • a SGD-based Algorithm such as:
    • a Kalman-based Stochastic Gradient Descent (kSGD),
    • a Mini-Batch Stochastic Gradient Descent Algorithm (MBSGD),
    • a Stochastic Average Gradient (SAG),
    • a Semi-Stochastic Gradient Descent (SSGD),
    • a Stochastic Recursive Gradient Algorithm (SARAH),
    • a Stochastic Variance Reduce Gradient (SVRG).
• See: Stochastic Optimization, Convex Optimization, Learning Rate, Gradient Descent, Outer Product, Hadamard Matrix Product, Euclidean Norm, Proximal Function.

---

---

References

2018a

• (Wijaya et al., 2018) ⇒ Galih Praja Wijaya, Dendi Handian, Imam Fachmi Nasrulloh, Lala Septem Riza, Rani Megasari, Enjun Junaeti (2018), "gradDescent: Gradient Descent for Regression Tasks", "Reference manual (PDF).
  • QUOTE: An implementation of various learning algorithms based on Gradient Descent for dealing with regression tasks. The variants of gradient descent algorithm are: Mini-Batch Gradient Descent (MBGD), which is an optimization to use training data partially to reduce the computation load. Stochastic Gradient Descent (SGD), which is an optimization to use a random data in learning to reduce the computation load drastically. Stochastic Average Gradient (SAG), which is a SGD-based algorithm to minimize stochastic step to average. Momentum Gradient Descent (MGD), which is an optimization to speed-up gradient descent learning. Accelerated Gradient Descent (AGD), which is an optimization to accelerate gradient descent learning. Adagrad, which is a gradient-descent-based algorithm that accumulate previous cost to do adaptive learning. Adadelta, which is a gradient-descent-based algorithm that use hessian approximation to do adaptive learning. RMSprop, which is a gradient-descent-based algorithm that combine Adagrad and Adadelta adaptive learning ability. Adam, which is a gradient-descent-based algorithm that mean and variance moment to do adaptive learning. Stochastic Variance Reduce Gradient (SVRG), which is an optimization SGD-based algorithm to accelerates the process toward converging by reducing the gradient. Semi Stochastic Gradient Descent (SSGD),which is a SGD-based algorithm that combine GD and SGD to accelerates the process toward converging by choosing one of the gradients at a time. Stochastic Recursive Gradient Algorithm (SARAH), which is an optimization algorithm similarly SVRG to accelerates the process toward converging by accumulated stochastic information. Stochastic Recursive Gradient Algorithm+ (SARAHPlus), which is a SARAH practical variant algorithm to accelerates the process toward converging provides a possibility of earlier termination.

2018c

• (DL4J, 2018) ⇒ https://deeplearning4j.org/updater#adadelta Retrieved: 2018-04-29.
  • QUOTE: AdaDelta also uses an exponentially decaying average of g_t, which was our second moment of gradient. But without using the alpha we typically use as learning rate, it introduces x_t, which is the second moment of v_t.

    

    • AdaDeltaUpdater in Deeplearning4j

2018d

• (Redii et al.) ⇒ Reddi, S. J., Kale, S., & Kumar, S. (2018, February). "On the convergence of adam and beyond. In International Conference on Learning Representations (PDF)" [6].
  • ABSTRACT: Several recently proposed stochastic optimization methods that have been successfully used in training deep networks such as RMSProp, Adam, Adadelta, Nadam are based on using gradient updates scaled by square roots of exponential moving averages of squared past gradients. In many applications, e.g. learning with large output spaces, it has been empirically observed that these algorithms fail to converge to an optimal solution (or a critical point in nonconvex settings). We show that one cause for such failures is the exponential moving average used in the algorithms. We provide an explicit example of a simple convex optimization setting where Adam does not converge to the optimal solution, and describe the precise problems with the previous analysis of Adam algorithm. Our analysis suggests that the convergence issues can be fixed by endowing such algorithms with “long-term memory of past gradients, and propose new variants of the Adam algorithm which not only fix the convergence issues but often also lead to improved empirical performance.

2012

• (Zeiler, 2012) ⇒ Zeiler, M. D. (2012). "ADADELTA: an adaptive learning rate method"(PDF). arXiv preprint arXiv:1212.5701.
  • ABSTRACT: We present a novel per-dimension learning rate method for gradient descent called ADADELTA. The method dynamically adapts over time using only first order information and has minimal computational overhead beyond vanilla stochastic gradient descent. The method requires no manual tuning of a learning rate and appears robust to noisy gradient information, different model architecture choices, various data modalities and selection of hyperparameters. We show promising results compared to other methods on the MNIST digit classification task using a single machine and on a large scale voice dataset in a distributed cluster environment.

---