Stochastic Optimization

Adafactor is a stochastic optimization method based on Adam that reduces memory usage while retaining the empirical benefits of adaptivity. This is achieved through maintaining a factored representation of the squared gradient accumulator across training steps. Specifically, by tracking moving averages of the row and column sums of the squared gradients for matrix-valued variables, we are able to reconstruct a low-rank approximation of the exponentially smoothed accumulator at each training step that is optimal with respect to the generalized Kullback-Leibler divergence. For an $n \times m$ matrix, this reduces the memory requirements from $O(n m)$ to $O(n + m)$. Instead of defining the optimization algorithm in terms of absolute step sizes {$\alpha_t$}$\_{t=1}^T$, the authors define the optimization algorithm in terms of relative step sizes {$\rho_t$}$\_{t=1}^T$, which get multiplied by the scale of the parameters. The scale of a parameter vector or matrix is defined as the root-mean-square of its components, lower-bounded by a small constant $\epsilon_2$. The reason for this lower bound is to allow zero-initialized parameters to escape 0. Proposed hyperparameters are: $\epsilon\_{1} = 10^{-30}$, $\epsilon\_{2} = 10^{-3}$, $d=1$, $p\_{t} = \min\left(10^{-2}, \frac{1}{\sqrt{t}}\right)$, $\hat{\beta}\_{2\_{t}} = 1 - t^{-0.8}$.

This optimizer mix ADAM and SGD creating the MAS optimizer.

LAMB is a a layerwise adaptive large batch optimization technique. It provides a strategy for adapting the learning rate in large batch settings. LAMB uses Adam as the base algorithm and then forms an update as: $$r\_{t} = \frac{m\_{t}}{\sqrt{v\_{t}} + \epsilon}$$ $$x\_{t+1}^{\left(i\right)} = x\_{t}^{\left(i\right)} - \eta\_{t}\frac{\phi\left(|| x\_{t}^{\left(i\right)} ||\right)}{|| m\_{t}^{\left(i\right)} || }\left(r\_{t}^{\left(i\right)}+\lambda{x\_{t}^{\left(i\right)}}\right) $$ Unlike LARS, the adaptivity of LAMB is two-fold: (i) per dimension normalization with respect to the square root of the second moment used in Adam and (ii) layerwise normalization obtained due to layerwise adaptivity.

Please enter a description about the method here

AMSGrad is a stochastic optimization method that seeks to fix a convergence issue with Adam based optimizers. AMSGrad uses the maximum of past squared gradients $v\_{t}$ rather than the exponential average to update the parameters: $$m\_{t} = \beta\_{1}m\_{t-1} + \left(1-\beta\_{1}\right)g\_{t} $$ $$v\_{t} = \beta\_{2}v\_{t-1} + \left(1-\beta\_{2}\right)g\_{t}^{2}$$ $$ \hat{v}\_{t} = \max\left(\hat{v}\_{t-1}, v\_{t}\right) $$ $$\theta\_{t+1} = \theta\_{t} - \frac{\eta}{\sqrt{\hat{v}_{t}} + \epsilon}m\_{t}$$

Stochastic Weight Averaging is an optimization procedure that averages multiple points along the trajectory of SGD, with a cyclical or constant learning rate. On the one hand it averages weights, but it also has the property that, with a cyclical or constant learning rate, SGD proposals are approximately sampling from the loss surface of the network, leading to stochastic weights and helping to discover broader optima.

Gradient Sparsification is a technique for distributed training that sparsifies stochastic gradients to reduce the communication cost, with minor increase in the number of iterations. The key idea behind our sparsification technique is to drop some coordinates of the stochastic gradient and appropriately amplify the remaining coordinates to ensure the unbiasedness of the sparsified stochastic gradient. The sparsification approach can significantly reduce the coding length of the stochastic gradient and only slightly increase the variance of the stochastic gradient.

Progressive Neural Architecture Search, or PNAS, is a method for learning the structure of convolutional neural networks (CNNs). It uses a sequential model-based optimization (SMBO) strategy, where we search the space of cell structures, starting with simple (shallow) models and progressing to complex ones, pruning out unpromising structures as we go. At iteration $b$ of the algorithm, we have a set of $K$ candidate cells (each of size $b$ blocks), which we train and evaluate on a dataset of interest. Since this process is expensive, PNAS also learns a model or surrogate function which can predict the performance of a structure without needing to train it. We then expand the $K$ candidates of size $b$ into $K' \gg K$ children, each of size $b+1$. The surrogate function is used to rank all of the $K'$ children, pick the top $K$, and then train and evaluate them. We continue in this way until $b=B$, which is the maximum number of blocks we want to use in a cell.

ADAHESSIAN is a new stochastic optimization algorithm that directly incorporates approximate curvature information from the loss function, and it includes several novel performance-improving features, including a fast Hutchinson based method to approximate the curvature matrix with low computational overhead.

Aging Evolution, or Regularized Evolution, is an evolutionary algorithm for neural architecture search. Whereas in tournament selection, the best architectures are kept, in aging evolution we associate each genotype with an age, and bias the tournament selection to choose the younger genotypes. In the context of architecture search, aging evolution allows us to explore the search space more, instead of zooming in on good models too early, as non-aging evolution would.

PowerSGD is a distributed optimization technique that computes a low-rank approximation of the gradient using a generalized power iteration (known as subspace iteration). The approximation is computationally light-weight, avoiding any prohibitively expensive Singular Value Decomposition. To improve the quality of the efficient approximation, the authors warm-start the power iteration by reusing the approximation from the previous optimization step.

AdaSmooth is a stochastic optimization technique that allows for per-dimension learning rate method for SGD. It is an extension of Adagrad and AdaDelta that seek to reduce its aggressive, monotonically decreasing learning rate. Instead of accumulating all past squared gradients, Adadelta restricts the window of accumulated past gradients to a fixed size $w$ while AdaSmooth adaptively selects the size of the window. Given the window size $M$, the effective ratio is calculated by $$e_t = \frac{s_t}{n_t}= \frac{| x_t - x_{t-M}|}{\sum_{i=0}^{M-1} | x_{t-i} - x_{t-1-i}|}\\ = \frac{| \sum_{i=0}^{M-1} \Delta x_{t-1-i}|}{\sum_{i=0}^{M-1} | \Delta x_{t-1-i}|}.$$ Given the effective ratio, the scaled smoothing constant is obtained by: $$c_t = ( \rho_2- \rho_1) \times e_t + (1-\rho_2),$$ The running average $E\left[g^{2}\right]\_{t}$ at time step $t$ then depends only on the previous average and current gradient: $$ E\left[g^{2}\right]\_{t} = c_t^2 \odot g_{t}^2 + \left(1-c_t^2 \right)\odot E[g^2]_{t-1} $$ Usually $\rho_1$ is set to around $0.5$ and $\rho_2$ is set to around 0.99. The update step the follows: $$ \Delta x_t = -\frac{\eta}{\sqrt{E\left[g^{2}\right]\_{t} + \epsilon}} \odot g_{t}, $$ which is incorporated into the final update: $$x_{t+1} = x_{t} + \Delta x_t.$$ The main advantage of AdaSmooth is its faster convergence rate and insensitivity to hyperparameters.

Quasi-Hyperbolic Momentum (QHM) is a stochastic optimization technique that alters momentum SGD with a momentum step, averaging an SGD step with a momentum step: $$ g\_{t+1} = \beta{g\_{t}} + \left(1-\beta\right)\cdot{\nabla}\hat{L}\_{t}\left(\theta\_{t}\right) $$ $$ \theta\_{t+1} = \theta\_{t} - \alpha\left[\left(1-v\right)\cdot\nabla\hat{L}\_{t}\left(\theta\_{t}\right) + v\cdot{g\_{t+1}}\right]$$ The authors suggest a rule of thumb of $v = 0.7$ and $\beta = 0.999$.

Please enter a description about the method here

AdaMod is a stochastic optimizer that restricts adaptive learning rates with adaptive and momental upper bounds. The dynamic learning rate bounds are based on the exponential moving averages of the adaptive learning rates themselves, which smooth out unexpected large learning rates and stabilize the training of deep neural networks. The weight updates are performed as: $$ g\_{t} = \nabla{f}\_{t}\left(\theta\_{t-1}\right) $$ $$ m\_{t} = \beta\_{1}m\_{t-1} + \left(1-\beta\_{1}\right)g\_{t} $$ $$ v\_{t} = \beta\_{2}v\_{t-1} + \left(1-\beta\_{2}\right)g\_{t}^{2} $$ $$ \hat{m}\_{t} = m\_{t} / \left(1 - \beta^{t}\_{1}\right)$$ $$ \hat{v}\_{t} = v\_{t} / \left(1 - \beta^{t}\_{2}\right)$$ $$ \eta\_{t} = \alpha\_{t} / \left(\sqrt{\hat{v}\_{t}} + \epsilon\right) $$ $$ s\_{t} = \beta\_{3}s\_{t-1} + (1-\beta\_{3})\eta\_{t} $$ $$ \hat{\eta}\_{t} = \text{min}\left(\eta\_{t}, s\_{t}\right) $$ $$ \theta\_{t} = \theta\_{t-1} - \hat{\eta}\_{t}\hat{m}\_{t} $$

BAGUA is a communication framework whose design goal is to provide a system abstraction that is both flexible and modular to support state-of-the-art system relaxation techniques of distributed training. The abstraction goes beyond parameter server and Allreduce paradigms, and provides a collection of MPI-style collective operations to facilitate communications with different precision and centralization strategies.

The MADGRAD method contains a series of modifications to the AdaGrad-DA method to improve its performance on deep learning optimization problems. It gives state-of-the-art generalization performance across a diverse set of problems, including those that Adam normally under-performs on.

Pipelined Backpropagation is an asynchronous pipeline parallel training algorithm. It was first introduced by Petrowski et al (1993). It avoids fill and drain overhead by updating the weights without draining the pipeline first. This results in weight inconsistency, the use of different weights on the forward and backward passes for a given micro-batch. The weights used to produce a particular gradient may also have been updated when the gradient is applied, resulting in stale (or delayed) gradients. For these reasons PB resembles Asynchronous SGD and is not equivalent to standard SGD. Finegrained pipelining increases the number of pipeline stages and hence increases the weight inconsistency and delay.

The Quasi-Hyperbolic Momentum Algorithm (QHM) is a simple alteration of momentum SGD, averaging a plain SGD step with a momentum step. QHAdam is a QH augmented version of Adam, where we replace both of Adam's moment estimators with quasi-hyperbolic terms. QHAdam decouples the momentum term from the current gradient when updating the weights, and decouples the mean squared gradients term from the current squared gradient when updating the weights. In essence, it is a weighted average of the momentum and plain SGD, weighting the current gradient with an immediate discount factor $v\_{1}$ divided by a weighted average of the mean squared gradients and the current squared gradient, weighting the current squared gradient with an immediate discount factor $v\_{2}$. $$ \theta\_{t+1, i} = \theta\_{t, i} - \eta\left[\frac{\left(1-v\_{1}\right)\cdot{g\_{t}} + v\_{1}\cdot\hat{m}\_{t}}{\sqrt{\left(1-v\_{2}\right)g^{2}\_{t} + v\_{2}\cdot{\hat{v}\_{t}}} + \epsilon}\right], \forall{t} $$ It is recommended to set $v\_{2} = 1$ and $\beta\_{2}$ same as in Adam.