Deep learning optimizers

There are a lot of optimizers for training deep learning models, among which SGD (stochastic gradient descent) and Adam (Adaptive Momentum Estimation) are mostly used at least in object detection. For example, FAIR loves SGD with momentum 0.9 in their seminal papers including Faster R-CNN, RetinaNet and Mask R-CNN, while Adam are the common optimizer in 3D LiDAR object detections.

SGD

SGD with momentum in Pytorch in of the form \begin{equation} { \begin{array}{c}\mathbf{m}^{(t+1)} &=& \mu\,\mathbf{m}^{(t)} + \nabla f\left(\mathbf{x}^{(t)}\right)\,,\nonumber\\\mathbf{x}^{(t+1)} &=&\mathbf{x}^{(t)} - \gamma\,\mathbf{m}^{(t+1)} \,,\end{array}}\tag{1}\end{equation} where $\mu$ is the momentum coefficient and $\gamma$ is the learning rate.
Remarks:

  • Vanilla SGD updates $\mathbf{x}^{(t)}$ only by its gradient $\nabla f\left(\mathbf{x}^{(t)}\right)$, i.e. $\mu=0$.

  • Here, $\mathbf{x}^{(t)}$ is updated by the exponentially weighted moving average (EWMA) of all the past gradients: \begin{equation} \mathbf{m}^{(t+1)} = \sum_{\tau=0} ^{t} \mu^{t-\tau} \,\nabla f\left(\mathbf{x}^{(\tau)}\right)\,.\nonumber \end{equation} To me, EWMA view is more transparent than the physics analogy of momentum and acceleration.  

  • EWMA at the first look should be \begin{eqnarray} \mathbf{m}^{(t+1)}&=&\mu\,\mathbf{m}^{(t)} + (1-\mu) \nabla f\left(\mathbf{x}^{(t)}\right)\,,\nonumber\\ \mathbf{x}^{(t+1)} &=& \mathbf{x}^{(t)} - \alpha\,\mathbf{m}^{(t+1)} \,,\nonumber \end{eqnarray} which is the same as the pytorch implementation (1) with $\gamma = \alpha (1-\mu)$.

  • The pytorch implementation (1) relates to the version in Sutskever et.al paper \begin{eqnarray} \mathbf{q}^{(t+1)} &=& \nu\,\mathbf{q}^{(t)} + \gamma\,\nabla f\left(\mathbf{x}^{(t)}\right)\,,\nonumber\\ \mathbf{x}^{(t+1)} &=& \mathbf{x}^{(t)} - \mathbf{q}^{(t+1)} \,,\nonumber \end{eqnarray} by $\mathbf{m}^{(t)} =\mathbf{q}^{(t)} / \gamma$ and $\mu = \nu/ \gamma$. 

Furthermore, NAG (Nesterov accelerated gradient) is to compute the gradient with respect to the approximate future position of parameters rather than the current position: \begin{eqnarray} \mathbf{m}^{(t+1)} &=& \mu\,\mathbf{m}^{(t)} + \nabla f\left(\mathbf{x}^{(t)}-\gamma\,\mu\,\mathbf{m}^{(t)}\right)\,,\nonumber\\ \mathbf{x}^{(t+1)} &=& \mathbf{x}^{(t)} - \gamma\,\mathbf{m}^{(t+1)} \,.\nonumber \end{eqnarray} By replacing $\mathbf{x}^{(t)}\leftarrow \mathbf{x}^{(t)}-\gamma\,\mu\,\mathbf{m}^{(t)}$, the pytorch implementation of NAG is of the form \begin{eqnarray}\label{Nesterov} \mathbf{m}^{(t+1)} &=& \mu\,\mathbf{m}^{(t)} + \nabla f\left(\mathbf{x}^{(t)}\right)\,,\nonumber\\ \mathbf{x}^{(t+1)} &=& \mathbf{x}^{(t)} - \gamma\,\left[\nabla f\left(\mathbf{x}^{(t)}\right)+\mu\,\mathbf{m}^{(t+1)}\right]\,. \tag{2}\end{eqnarray} In sum, SGD with momentum (1) updates $\mathbf{x}^{(t)}$ by EWMV $\mathbf{m}^{(t+1)}$ while NAG (2) updates $\mathbf{x}^{(t)}$ by $\nabla f\left(\mathbf{x}^{(t)}\right)+\mu\,\mathbf{m}^{(t+1)}$.

Adam

Besides the EWMV of gradients as in SGD, Adam also adopts adaptive learning rates controlled by the EWMV of squared gradients: \begin{eqnarray} \mathbf{m}^{(t+1)} &= & \beta_1\,\mathbf{m}^{(t)} + \left(1-\beta_1\right) \nabla f\left(\mathbf{x}^{(t)}\right)\,,\nonumber\\ \mathbf{v}^{(t+1)} &=& \beta_2\,\mathbf{v}^{(t)} + \left(1-\beta_2\right) \nabla f\left(\mathbf{x}^{(t)}\right) \odot \nabla f\left(\mathbf{x}^{(t)}\right)\,,\nonumber\\ \hat{\mathbf{m}}^{(t+1)} &=& \frac{\mathbf{m}^{(t+1)}}{1-\beta_1^{t+1}}\,,\nonumber\\ \hat{\mathbf{v}}^{(t+1)} &=& \frac{\mathbf{v}^{(t+1)}}{1-\beta_2^{t+1}}\,,\nonumber\\ \mathbf{x}^{(t+1)} &=& \mathbf{x}^{(t)} - \gamma\,\hat{\mathbf{m}}^{(t+1)} \oslash \,\left({\sqrt{\hat{\mathbf{v}}^{(t+1)} }+\epsilon}\right)\,. \tag{3}\end{eqnarray}
Remarks:
  • The operations of product, division and square root above are all element-wise.
  • Each component $\mathbf{x}^{(t)}_i$ has its own adaptive learning rate $\gamma / \sqrt{\hat{\mathbf{v}}^{(t)}_i}$.
  • The bias corrections in the third and forth lines is argued as follows: note that  $\mathbf{m}^{(t+1)} = \left(1-\beta_1\right)\sum_{\tau=0}^t \beta_1^{t-\tau}\, \nabla f\left(\mathbf{x}^{(\tau)}\right)$. If $\nabla f\left(\mathbf{x}^{(\tau)}\right)$ forms a stationary time series, $\mathbb{E}\left[\nabla f\left(\mathbf{x}^{(\tau)}\right)\right]=\mathbf{g}$. As a result, $\mathbb{E}\left[\mathbf{m}^{(t+1)}\right] = \mathbf{g}\left(1-\beta_1\right)\sum_{\tau=0}^t \beta_1^{t-\tau}=\mathbf{g}\left(1-\beta_1^{t+1}\right)$.
Some other optimizers including Adagrad, Adadelta, RMSprop can be viewed as simplified verisons of Adam:
  • RMSprop: no momentum ($\beta_1=0$) and no bias corrections. \begin{eqnarray} \mathbf{v}^{(t+1)} &=& \beta_2\,\mathbf{v}^{(t)} + \left(1-\beta_2\right) \nabla f\left(\mathbf{x}^{(t)}\right) \odot \nabla f\left(\mathbf{x}^{(t)}\right)\,,\nonumber\\ \mathbf{x}^{(t+1)} &=& \mathbf{x}^{(t)} - \gamma\, \nabla f\left(\mathbf{x}^{(t)}\right) \oslash \,\left({\sqrt{{\mathbf{v}}^{(t+1)}}+\epsilon}\right)\,.\nonumber \end{eqnarray}
  • Adadelta: no momentum ($\beta_1=0$) and no bias corrections. A new variable $\boldsymbol{\delta}$ and its EWMA are introduced  $\boldsymbol{\Delta}$: \begin{eqnarray} \mathbf{v}^{(t+1)} &=& \beta_2\,\mathbf{v}^{(t)} + \left(1-\beta_2\right) \nabla f\left(\mathbf{x}^{(t)}\right) \odot \nabla f\left(\mathbf{x}^{(t)}\right)\,,\nonumber\\ \boldsymbol{\delta}^{(t+1)} &=& \sqrt{\boldsymbol{\Delta}^{(t)}+\epsilon}\oslash \,\left({\sqrt{{\mathbf{v}}^{(t+1)}}+\epsilon}\right)\odot \nabla f\left(\mathbf{x}^{(t)}\right)\,,\nonumber\\ \mathbf{x}^{(t+1)} &=& \mathbf{x}^{(t)} - \gamma\,\boldsymbol{\delta}^{(t+1)}\,,\nonumber\\ \boldsymbol{\Delta}^{(t+1)} &=& \beta_2\,\boldsymbol{\Delta}^{(t)} + \left(1-\beta_2\right) \boldsymbol{\delta}^{(t+1)}\odot \boldsymbol{\delta}^{(t+1)}\,.\nonumber \end{eqnarray} Roughly speaking, the intuition is inspired by Newton method:  $\boldsymbol{\delta}\propto\mathbf{H}^{-1}\mathbf{g}$ and $\mathbf{H}^{-1}\propto\boldsymbol{\delta} \oslash \mathbf{g}$, iteratively.
  • Adagrad: no momentum ($\beta_1=0$) and no bias corrections. Squared gradients are simply summed rather than EWMA, which eventually makes adaptive learning rate vanish. \begin{eqnarray} \mathbf{v}^{(t+1)} &=& \sum_{\tau=0}^t \nabla f\left(\mathbf{x}^{(\tau)}\right)\odot \nabla f\left(\mathbf{x}^{(\tau)}\right)\,,\nonumber\\ \mathbf{x}^{(t+1)} &=& \mathbf{x}^{(t)} - \gamma\, \nabla f\left(\mathbf{x}^{(t)}\right) \oslash \,\left({\sqrt{{\mathbf{v}}^{(t+1)}}+\epsilon}\right)\,.\nonumber \end{eqnarray}



Location: 美国加利福尼亚州帕罗奥图

Comments

Post a Comment

Popular posts from this blog

529 Plan

This post is for knowledge sharing only. It is not intended to be investment or tax advice. 529 Plans are tax-advantaged accounts specific for education saving: Contribution are made with after-tax dollars. Growth within the account is tax-free. Withdraw for qualified education expenses is also tax free. Roth IRA First 529 Plans are very similar to Roth IRA . But Roth IRA withdraw under  the 5-year rule  is tax free for any purpose. Therefore, unless for the state tax deduction in some states, it is always better to max out Roth IRA first (through backdoor and mega backdoor  for high income earners) before funding a 529 plan. Note: there is NO California state tax deduction for any 529 plan. 529 or Not? Here are some considerations in reality before funding a 529 plan: What if no qualified education expenses In the worst case that there will be no qualified education expenses, you can still take money out for non-qualified expenses, but you have to pay: federal income tax + 10% federa
Read more

How to offset W2 tax

This post is for knowledge sharing only. It is not intended to be tax or investment advice. 1. Contribute to pre-tax 401K and HSA As well known, pre-tax 401K and health saving account (HSA) are the only a few tax shelters for W2 workers.  2. Tax-loss harvesting If your total capital losses exceed your capital gains in a tax year, you can deduct up to \$3,000 (married filing jointly) from your ordinary income. If your losses are more than $3,000, you can carry over the remaining amount to future years, continuing to offset your income until all the losses are used up. A popular method to generate these deductible losses is  tax-loss harvesting . This involves selling a security at a loss to offset gains or reduce ordinary income, and optionally purchasing a similar, but not "substantially identical", security to avoid missing out on the market. However, be aware of the  wash-sale rule , which disallows claiming a loss if you buy the same or a substantially identical security
Read more

Retirement Accounts

Image
This post is for knowledge sharing only. It is not intended to be investment or tax advice. 0. Account Overview  Table 1 Common retirement  accounts in U.S. I summarizes the common retirement accounts in Table 1:  The second row in Table 1 lists the company-sponsored accounts that are offered through employers. The third row in Table 1 lists the individual retirement accounts (IRA) that is unrelated to employments. The columns in Table 1 are about different tax advantages as described below. WARNING: because of the tax advantages, there are also limitations and specific rules imposed by IRS for early withdrawal before the retirement age. For accounts listed in the second column,  Contributions are made with before-tax dollars . The money taken out will be taxed as regular income in the year of withdrawal. For accounts listed in the third column,  Contributions are made with after-tax dollars . The money taken out is  tax free . For after-tax 401K in the fourth column, Contributions are
Read more