# Gradient Descent :
There are three variants of gradient descent, which differ in how much data we use to compute the gradient of the objective function. Depending on the amount of data, we make a trade-off between the accuracy of the parameter update and the time it takes to perform an update.
- Batch Gradient Descent
- Stochastic Gradient Descent
- Mini-batch Gradient Descent

## Batch gradient descent

Vanilla gradient descent, aka batch gradient descent, computes the gradient of the cost function w.r.t. to the parameters 
θ for the entire training dataset:

$\theta = \theta - \eta \cdot \nabla_\theta J( \theta)$

As we need to calculate the gradients for the whole dataset to perform just one update, batch gradient descent can be very slow and is intractable for datasets that don't fit in memory. Batch gradient descent also doesn't allow us to update our model online, i.e. with new examples on-the-fly.

## Stochastic gradient descent

Stochastic gradient descent (SGD) in contrast performs a parameter update for each training example 
$x^{(i)}$ and label $y^{(i)}$ 

$\theta = \theta - \eta \cdot \nabla_\theta J( \theta; x^{(i)}; y^{(i)})$

Batch gradient descent performs redundant computations for large datasets, as it recomputes gradients for similar examples before each parameter update. SGD does away with this redundancy by performing one update at a time. It is therefore usually much faster and can also be used to learn online.

## Mini-batch gradient descent

Mini-batch gradient descent finally takes the best of both worlds and performs an update for every mini-batch of 
n  training examples:
    
$\theta = \theta - \eta \cdot \nabla_\theta J( \theta; x^{(i:i+n)}; y^{(i:i+n)})$

This way, it 
- Reduces the variance of the parameter updates, which can lead to more stable convergence; and 
- Can make use of highly optimized matrix optimizations common to state-of-the-art deep learning libraries that make computing the gradient w.r.t. a mini-batch very efficient. 
- Common mini-batch sizes range between 50 and 256, but can vary for different applications. 
- Mini-batch gradient descent is typically the algorithm of choice when training a neural network and the term SGD usually is employed also when mini-batches are used. 

## Conclusion

We have a dataset of size N  .
1. In Batch GD we consider all the data point (all N data points)
2. In SGD we consider only 1 datapoint per epoch 
3. In Mini-Batch` SGD we consider k datapoints per epoch ( k < N)

# Gradient descent optimization algorithms

1. Momentum
2. Nesterov accelerated gradient
3. Adagrad
4. Adadelta
5. RMSprop
6. Adam
7. Nadam
8. AMSGrad
9. Weigth Decay

##  SGD with Momentum : Sochastic Gradient Descent

- It takes two steps one 0.9 times the history and 0.1 times the current gradient

SGD has trouble navigating ravines, i.e. areas where the surface curves much more steeply in one dimension than in another , which are common around local optima. In these scenarios, SGD oscillates across the slopes of the ravine while only making hesitant progress along the bottom towards the local optimum as in Image 2.

Momentum is 0.1 of the derivative and 0.9 of it is just the same direction I went last time. 

Challenges : Overshots its objects and then had to take a U-turn.

Image 2: without Momentum

Image 3 : with Momentum


Momentum is a method that helps accelerate SGD in the relevant direction and dampens oscillations as can be seen in Image 3. It does this by adding a fraction γ  of the update vector of the past time step to the current update vector:

$v_t = \gamma v_{t-1} + \eta \nabla_\theta J( \theta)$ 

$\theta = \theta - v_t $

Note: Some implementations exchange the signs in the equations. The momentum term γ  is usually set to 0.9 or a similar value.


```python
from IPython.display import YouTubeVideo

def display_yotube_video(url, **kwargs):
    """
    Displays a Youtube video in a Jupyter notebook.
    
    Args:
        url (string): a link to a Youtube video.
        **kwargs: further arguments for IPython.display.YouTubeVideo
    
    Returns:
        YouTubeVideo: a video that is displayed in your notebook.
    """
    id_ = url.split("=")[-1]
    return YouTubeVideo(id_, **kwargs)

display_yotube_video("https://youtu.be/uQtTwhpv7Ew?t=6520", width=1200, height=800)
```










## Nesterov Momentum
Look before you leap , look ahead gradient 

- It takes two steps one 0.9 times the history and 0.1 times the gradient step state.
- It takes shorter U-turns
- NAG first makes a big jump in the direction of the previous accumulated gradient (brown vector), measures the gradient and then makes a correction (red vector), which results in the complete NAG update (green vector).



- https://www.youtube.com/watch?v=sV9aiEsXanE

## Adagrad and RMSPROP

- In Adagrad we use different learning rates for every parameter at time step t.
- learning rate = η
- Backpropogation :
    $\theta_{t+1, i} = \theta_{t, i} - \dfrac{\eta}{\sqrt{G_{t, ii} + \epsilon}} \cdot g_{t, i}$
- $\epsilon$ is a smoothing term that avoids division by zero (usually on the order of 1e-8) 
- $G_{t}$ contains the sum of the squares of the past gradients w.r.t. to all parameters $\theta$

## Adadelta

- Adadelta is an extension of Adagrad that seeks to reduce its aggressive, monotonically decreasing learning rate. 
- Instead of accumulating all past squared gradients, Adadelta restricts the window of accumulated past gradients to some fixed size w
- prevent this $G_{t}$ to become very big , as this reduces the learning rate .
- $G_{t}$ in Adadelta is weighted moving average and not sum of gradeint sqaure like adagrad.
- RMSprop and Adadelta have both been developed independently around the same time stemming from the need to resolve Adagrad's radically diminishing learning rates. RMSprop in fact is identical to the first update vector of Adadelta that we derived above

## SGD and SGD+Momentum

## Momentum:
Accelerate SGD in the relevant direction and dampen side-to-side oscillations
It does this by combining a decaying average of previous gradients with the current gradient




<span style='background:black; color:white'> SGD  </span>

<span style='background:blue;color:white'> SGD+Momentum  </span>



## Momentum and ADAGRAD

## ADAGRAD:
The idea is that you keep the running sum of squared gradients during optimization. In this case, we have no momentum term, but an expression g that is the sum of the squared gradients.



## ADAGRAD and RMSPROP

There is a slight variation of AdaGrad called RMSProp that addresses the problem that AdaGrad has. With RMSProp we still keep the running sum of squared gradients but instead of letting that sum grow continuously over the period of training we let that sum actually decay.
In RMSProp we multiply the sum of squared gradients by a decay rate α and add the current gradient weighted by (1- α). The update step in the case of RMSProp looks exactly the same as in AdaGrad where we divide the current gradient by the sum of squared gradients to have this nice property of accelerating the movement along the one dimension and slowing down the movement along the other dimension.





<span style='background:black; color:white'> SGD  </span>

<span style='background:blue;color:white'> SGD+Momentum  </span>

<span style='background:red;color:white'> RMSPROP </span>



##  Adam Optimizer

The main part of the algorithm consists of the following three equations.



The first equation looks a bit like the SGD with momentum. In the case, the term m would be the velocity and β1 the friction term. In the case of Adam, we call m the first momentum and β1 is just a hyperparameter.

The difference to SGD with momentum, however, is the factor (1- β1), which is multiplied with the current gradient.

The second part of the equations, on the other hand, can be regarded as RMSProp, in which we are keeping the running sum of squared gradients. Also, in this case, there is the factor (1-β2) which is multiplied with the squared gradient.

The term v in the equation is called as the second momentum, and β2 is also just a hyperparameter. The final update equation can be seen as a combination of RMSProp and SGD with Momentum.

So far, Adam has integrated the nice features of the two previous optimization algorithms, but here’s a little problem, and that’s the question of what happens in the beginning.

At the very first time step, the first and second momentum terms are initialized to zero. After the first update of the second momentum, this term is still very close to zero. When we update the weight parameters in the last equation, we divide by a very small second momentum term v, resulting in a very large first update step.

This first very large update step is not the result of the geometry of the problem, but it is an artifact of the fact that we have initialized the first and second momentum to zero. To solve the problems of large first update steps, Adam includes a correction clause:



You can see that after the first update of the first and second momentum m and v we make an unbiased estimate of these momentums by taking into account the current time step t. These correction terms make the values of the first and second momentum to be higher in the beginning than in the case without the bias correction.

As a result, the first update step of the neural network parameters does not get that large and we don’t mess up our training in the beginning. The additional bias corrections give us the full form of Adam Optimizer.

<span style='background:black; color:white'> SGD  </span>

<span style='background:blue;color:white'> SGD+Momentum  </span>

<span style='background:red;color:white'> RMSPROP </span>

<span style='background:purple;color:white'> ADAM </span>



- https://www.deeplearning-academy.com/p/ai-wiki-optimization-algorithms

## Nadam

As we have seen before, Adam can be viewed as a combination of RMSprop and momentum: 
- RMSprop contributes the exponentially decaying average of past squared gradients vt,
- while momentum accounts for the exponentially decaying average of past gradients mt. 
- We have also seen that Nesterov accelerated gradient (NAG) is superior to vanilla momentum.
- Nadam (Nesterov-accelerated Adaptive Moment Estimation) thus combines Adam and NAG. In order to incorporate NAG into Adam, we need to modify its momentum term mt.

## ADAGRAD

In settings where Adam converges to a suboptimal solution, it has been observed that some minibatches provide large and informative gradients, but as these minibatches only occur rarely, exponential averaging diminishes their influence, which leads to poor convergence. The authors provide an example for a simple convex optimization problem where the same behaviour can be observed for Adam.

To fix this behaviour, the authors propose a new algorithm, AMSGrad that uses the maximum of past squared gradients 
vt rather than the exponential average to update the parameters. vt is defined the same as in Adam above:

$v_t = \beta_2 v_{t-1} + (1 - \beta_2) g_t^2$

Instead of using vt  (or its bias-corrected version ^vt) directly, we now employ the previous 
vt−1 if it is larger than the current one:

$\hat{v}_t = \text{max}(\hat{v}_{t-1}, v_t)$

This way, **AMSGrad results in a non-increasing step size**, which avoids the problems suffered by Adam. For simplicity, the authors also remove the debiasing step that we have seen in Adam. The full AMSGrad update without bias-corrected estimates can be seen below:

$m_t = \beta_1 m_{t-1} + (1 - \beta_1) g_t  $

$v_t = \beta_2 v_{t-1} + (1 - \beta_2) g_t^2 $

$\hat{v}_t = \text{max}(\hat{v}_{t-1}, v_t)  $

$\theta_{t+1} = \theta_{t} - \dfrac{\eta}{\sqrt{\hat{v}_t} + \epsilon} m_t$

## Additional strategies for optimizing SGD

### Shuffling and Curriculum Learning

Generally, we want to avoid providing the training examples in a meaningful order to our model as this may bias the optimization algorithm. Consequently, it is often a good idea to shuffle the training data after every epoch.

On the other hand, for some cases where we aim to solve progressively harder problems, supplying the training examples in a meaningful order may actually lead to improved performance and better convergence. The method for establishing this meaningful order is called Curriculum Learning .

Zaremba and Sutskever were only able to train LSTMs to evaluate simple programs using Curriculum Learning and show that a combined or mixed strategy is better than the naive one, which sorts examples by increasing difficulty.

### Batch Normalization

Another good standard approach to reducing overfitting is Batch Normalization.

In general, the inputs to your neural network should always be normalized. Normalization is a process where given a set of data, you subtract from each element the mean value for that data set and divide it by the data set's standard deviation. By doing so, we put the input values onto the same "scale", in that all the values have been normalized into units of "# of standard deviations from the mean".

The reason we would want to put our inputs onto the same scale is because unbalanced inputs with a large range of magnitudes can typically cause instability in neural networks. An extremely large input can often cascade down through the layers. Typically such an imbalance creates gradients that are also wildly imbalanced, and this makes the optimization process difficult to prevent things like explosion. It also creates imbalanced weights. Normalizing inputs avoids this problem.

Often times with images, we don't worry about dividing by the standard deviation, but just subtract the mean.

Occasionally, these instabilities can arise during training. Imagine that at some point during training, we end up with one extremely large weight. This extremely large weight will then produce an extremely large output value for some element of the output vector, and this imbalance will again pass through the neural network and make it unstable.

One idea is to normalize the activation outputs. Unfortunately, this won't prevent SGD from trying to create an imbalanced weight again during the next back-propagation, and trying to solve the problem this way will just cause SGD to continuously try to undo this activation layer normalization. 

Batch normalize extends this idea with two additions:

- after normalizing the activation layer, let's multiply the outputs by an arbitrarily set parameter, and add to that value an additional parameter, therefore setting a new standard deviation and mean

- Make all four of these values (the mean and standard deviation for normalization, and the two new parameters to set arbitrary mean and standard deviations after the normalization) trainable.

This ensures that the weights don't tend to push very high or very low (since the normalization is included in the gradient calculations, so the updates are aware of the normalization). But it also ensures that if a layer does need to change the overall mean or standard deviation in order to match the output scale, it can do so.

By default, you should always include batch normalization, and all modern neural networks do so because:

- Adding batchnorm to a model can result in 10x or more improvements in training speed
- Because normalization greatly reduces the ability of a small number of outlying inputs to over-influence the training, it also tends to reduce overfitting.

### Dropout
You'll notice in observing our metrics while training a Vgg model for Cats and Dogs that our training accuracy is usually lower than our validation. This points to underfitting, and the source of this in Vgg is relatively simple.

If you observe the Vgg layers in Keras, you'll notice a layer called Dropout. Dropout (which only happens during training) occurs after the activation layers, and randomly sets activations to zero. Why would we want to randomly delete parts of neural network? It turns out that this allows us to prevent overfitting. We can't overfit exactly to our training data when we're consistently throwing away information learned along the way. This allows our neural network to learn to generalize.

In the case of Vgg, the Dropout rate is set to 0.5. This seems quite large, and given the complexity of classification for Imagenet, it seems reasonable to want to make our dropout rate this high. However, for something much simpler like Cats and Dogs, we can see that we're underfitting, and we might have more success by retaining more information and lowering our dropout rate, and retraining.

### Gradient noise

Neelakantan add noise that follows a Gaussian distribution $N(0, \sigma^2_t)$ to each gradient update:

$g_{t, i} = g_{t, i} + N(0, \sigma^2_t)$

They anneal the variance according to the following schedule:
    
$\sigma^2_t = \dfrac{\eta}{(1 + t)^\gamma}$

## Weigth Decay

### What is Weigth Decay ? And why do we care ?

- We do a lot of feature engineering and one thing which we do very regularly is to reduce the paramters. 
- So what is so wrong in this approach ? So why do we care? Why would I want to use more parameters? 
- Because more parameters means more nonlinearities, more interactions, more curvy bits. 
- Real life is full of curvy bits. Real life does not look like a straight line. But we don't want them to be more curvy than necessary or more interacting than necessary. Therefore let's use lots of parameters and then penalize complexity.
- So one way to penalize complexity is let's sum up the value of your parameters.Now that doesn't quite work because some parameters are positive and some are negative. So what if we sum up the square of the parameters, and that's actually a really good idea.
- Let's create a model, and in the loss function we're going to add the sum of the square of the parameters.
- Let's actually create a model, and in the loss function we're going to add the sum of the square of the parameters. Now here's a problem with that though. Maybe that number is way too big, and it's so big that the best loss is to set all of the parameters to zero. That would be no good.
- So we want to make sure that doesn't happen, so therefore let's not just add the sum of the squares of the parameters to the model but let's multiply that by some number that we choose.That number that we choose is called wd (weigth decay).
- loss function and we're going to add to it the sum of the squares of parameters multiplied by some number wd.

### Explanation with little Maths :

- we have a cost or error function **E(w)** that we want to minimize. Gradient descent tells us to modify the weights w in the direction of steepest descent in E. This is called backpropogation.
   -  $\begin{equation}w_i \leftarrow w_i-lr\frac{\partial E}{\partial w_i},\end{equation}$
- where lr is the learning rate, and if it's large you will have a correspondingly large modification of the weights wi (in general it shouldn't be too large, otherwise you'll overshoot the local minimum in your cost function).
- In order to effectively limit the number of free parameters in your model so as to avoid over-fitting, it is possible to regularize the cost function remember more parameters means more nonlinearities, more interactions, more curvy bits.Real life is full of curvy bits.
- An easy way to do that is by introducing a zero mean Gaussian prior over the weights, which is equivalent to changing the cost function to
    - $\widetilde{E}(\mathbf{w})=E(\mathbf{w})+\frac{wd}{2}\mathbf{w}^2$
- In practice this penalizes large weights and effectively limits the freedom in your model. The regularization parameter wd determines how you trade off the original cost E with the large weights penalization.
- Applying gradient descent to this new cost function we obtain: (its just diffrentiation of new loss **$\widetilde{E}(\mathbf{w})$**)
    - $\begin{equation}w_i \leftarrow w_i-lr\frac{\widetilde{E}(\mathbf{w})}{\partial w_i} \end{equation}$ Substitute the value of **$\widetilde{E}(\mathbf{w})$** from above
    - $\begin{equation}w_i \leftarrow w_i-lr\frac{\partial E}{\partial w_i}-lr . wd. w_i.\end{equation}$
- The new term **−lr.wd.wi** coming from the regularization causes the weight to decay in proportion to its size.
- When it's in this form ($wd . w^2$) where we add the square to the loss function, that's called L2 regularization.
- When it's in this form ($wd . w$) where we subtract  times weights from the gradients, that's called **weight decay**.


```python
from IPython.display import IFrame

IFrame(src="https://ruder.io/optimizing-gradient-descent/", width=800, height=400)
```











```python
IFrame(src="https://cs231n.github.io/neural-networks-3/", width=800, height=400)
```











```python
IFrame(src="http://wiki.fast.ai/index.php/Lesson_3_Notes", width=800, height=400)
```














22eff3e57a3d1da82baab42bd9f61a6bf72e0ab3
ipynb
Jupyter Notebook
Documents/Pytorch/Optimizers.ipynb
IJyotir/cards
af4939482553fd40d55d4655268d69ac8a639f87
MIT
Documents/Pytorch/Optimizers.ipynb
IJyotir/cards
af4939482553fd40d55d4655268d69ac8a639f87
MIT
Documents/Pytorch/Optimizers.ipynb
IJyotir/cards
af4939482553fd40d55d4655268d69ac8a639f87
MIT
Qwen/Qwen-72B
1. YES
2. YES