1. Gradient Descent (GD):

Image description: In Gradient Descent, model parameters start randomly and are updated iteratively to minimize the cost function. The step size decreases as the cost approaches its minimum (first image). A high learning rate can cause the algorithm to overshoot the minimum and end up on the opposite side of a valley, potentially even higher than the initial position. This can lead to divergence, with the algorithm producing increasingly larger values and failing to find an optimal solution. In non-ideal scenarios, the cost function may have irregular shapes like holes, ridges, or plateaus, making convergence to the minimum challenging. In the case of the third image with local and global minimum structures, starting the algorithm on the left may lead to convergence to a local minimum, which is inferior to the global minimum. Conversely, starting on the right at the plateau could prolong the convergence process significantly. Moreover, stopping too early may prevent reaching the global minimum altogether.

1. Objective: Gradient Descent is an iterative optimization algorithm used to minimize a given cost function \(J(\theta)\) by adjusting the parameters \(\theta\) iteratively.
2. Components:
   • Cost Function (Loss Function): \(J(\theta_t)\) represents the cost function or loss function that measures how well the model performs on the training data with respect to its parameters \(\theta\).
   • Gradient: The gradient of the cost function \(J(\theta)\) with respect to the parameters \(\theta\), denoted by \(\nabla J(\theta)\), represents the direction of the steepest ascent. The negative gradient \(-\nabla J(\theta)\) points in the direction of the steepest descent, i.e., the direction in which the function decreases most rapidly.
   • Learning rate (\(\eta\)): \(\eta\) is a hyperparameter known as the learning rate. It determines the size of the steps taken in the parameter space during each iteration of the optimization process.
3. Steps:
   • Initialization: Initialize the parameters \(\theta\) randomly or with certain pre-defined values.
   • Compute Gradient: Calculate the gradient of the cost function \(J(\theta)\) with respect to the parameters \(\theta\) at the current parameter values
   • Update Parameters: Update the parameters \(\theta\) in the opposite direction of the gradient by taking a step proportional to the negative gradient and the learning rate. This step is expressed by the formula: $$\theta_{t+1} = \theta_t - \eta \nabla J(\theta_t)$$ where
     • \(\theta_{t+1}\) is the updated value of parameters at iteration \(t+1\).
     • \(\theta_t\) is the current value of parameters at iteration \(t\).
     • \(\nabla J(\theta_t)\) is the
     • \(\eta\) is the learning rate
   • Repeat
4. Convergence: Convergence occurs when the algorithm reaches a point where further updates to the parameters do not significantly reduce the value of the cost function.
5. Summary: Gradient Descent iteratively updates the parameters \(\theta\) in the direction of the steepest descent of the cost function, aiming to minimize the cost function and thereby optimize the model.
6. Variants: Various variants of Gradient Descent, such as Stochastic Gradient Descent (SGD), Mini-batch Gradient Descent, Momentum, Adam, and RMSprop, introduce modifications to the basic algorithm to improve convergence speed, stability, and efficiency.

2. Stochastic Gradient Descent (SGD):

1. Objective: SGD is an optimization algorithm commonly used in machine learning and deep learning for training models. It aims to minimize a given loss function by iteratively updating the model parameters.
2. Basic Idea:: Instead of computing the gradient of the loss function over the entire dataset (as in batch gradient descent), SGD computes the gradient over a single random training example at each iteration.
3. Algorithm:
   • Initialization: Start with initial parameter values \(\theta_0\).
   • Loop: Repeat until convergence or for a fixed number of iterations:
     • Randomly shuffle the training dataset.
     • For each training example \(i\) in the dataset:
       • Compute the gradient of the loss function with respect to the parameters using the current example: \(\nabla J(\theta_{t, i})\).
       • Update the parameters using the gradient descent update rule:
       $$\theta_{t+1} = \theta_t - \eta \nabla J(\theta_{t,i})$$ where:
       • \(\theta_t\) is the parameter vector at iteration \(t\).
       • \(\eta\) is the learning rate, determining the step size.
4. Key Aspects:
   • Randomness: SGD introduces randomness by using a random training example at each iteration. This randomness helps escape local minima and can lead to faster convergence, especially in large datasets.
   • Efficiency: Since only one training example is processed per iteration, SGD is computationally efficient and can handle large datasets that may not fit into memory.
   • Noisy Updates: Due to the randomness, SGD updates can be noisy, leading to oscillations around the optimal solution. However, this noise can sometimes help the optimization process by escaping sharp local minima.
   • Learning Rate Tuning: The learning rate \(\eta\) plays a crucial role in SGD. Choosing an appropriate learning rate is essential for convergence. It may need to be tuned during training using techniques like learning rate schedules or adaptive learning rate methods.
5. Formula: The update rule for SGD using a single training example \(i\) can be represented as: $$\theta_{t+1} = \theta_{t} - \eta \nabla J(\theta_{t,i})$$ where:
   • \(\theta_t\) is the parameter vector at iteration \(t\).
   • \(\eta\) is the learning rate.
   • \(\nabla J(\theta_{t,i})\) is the gradient of the loss function with respect to the parameters computed using the \(i-\)th training example.
6. Advantages:
   • Efficiency: SGD is computationally efficient, making it suitable for large-scale datasets.
   • Generalization: It often leads to better generalization since it avoids overfitting by updating parameters frequently with different examples.
   • Parallelism: SGD is inherently parallelizable, allowing for efficient implementation on parallel computing architectures.
7. Disadvantages:
   • Noisy Updates: The randomness in SGD updates can lead to noisy convergence, making it challenging to find the exact optimal solution.
   • Learning Rate Tuning: Proper tuning of the learning rate is crucial for stable convergence. An inappropriate learning rate can lead to slow convergence or divergence.
   • Sensitive to Scaling: SGD can be sensitive to feature scaling, requiring careful preprocessing of the input data.

3. Mini-batch Gradient Descent:

1. Overview: Mini-batch Gradient Descent divides the training data into small batches of size \(n\). Instead of computing the gradient on the entire dataset (GD) on on a single data point (SGD), MBGD computes the gradient on a mini-batch of training examples.
2. Formulation: Let's consider a dataset with \(m\) training examples. The cost function \(J(\theta)\) measures the difference between the model predictions and the actual targets. The update rule for Mini-batch Gradient Descent at iteration \(t\) is given by:
$$\theta_{t+1} = \theta_t - \eta \nabla J(\theta_{t,i:i+n})$$ where:
• \(\theta_t\) is the parameter vector at iteration \(t\).
• \(\eta\) is the learning rate.
• \(\nabla J(\theta_{t,i:i+n})\) is the gradient of the cost function \(j(\theta)\) computed on the mini-batch \(i:i+n\).
3. Algorithm Steps:
   • Initialization: Initialize the model parameters \(\theta\) and hyperparameters like the learning rate \(\eta\).
   • Mini-batch Formation: Randomly shuffle the training data and divide it into mini-batches of size \(n\). If the dataset size is not divisible by \(n\), the last mini-batch may have fewer examples.
   • Gradient Computation: For each mini-batch \(i : i+n\), compute the gradient of the cost function \(J(\theta)\) with respect to the parameters \(\theta\):
   $$\nabla J(\theta_{t,i:i+n}) = \frac{1}{n} \sum_{j=i}^{i+n} \nabla J(\theta_{t},x_j, y_j)$$ where (\(x_j,y_j\)) are the input features and corresponding target labels in the min-batch.
   • Parameter Update: Update the parameter \(\theta\) using the computed gradient:
   $$\theta_{t+1} = \theta_t - \eta \nabla J(\theta_{t,i:i+n})$$
   • Repeat: Repeat steps (c) and (d) for a fixed number of iterations or until convergence criteria are met.
4. Benefits of Mini-batch Gradient Descent:
   • Efficiency: MBGD utilizes vectorized operations, making it computationally efficient compared to SGD.
   • Stability: It offers more stable convergence than SGD as it considers a mini-batch of examples.
   • Memory Usage: It allows for efficient memory usage by processing only a subset of data at a time.
5. Hyperparameter Tuning:
   • Batch Size \(n\): The choice of mini-batch size affects the convergence speed and memory requirements.
   • Learning Rate \(\eta\): The learning rate determines the step size during parameter updates and impacts convergence.

4. Momentum:

Here's a detailed explanation of Momentum along with the formulas involved:

1. Update Formulas:
   • Momentum introduces a variable \(v\) which accumulates the gradients of the past steps.
   • The update for \(v\) at each iteration \(t\) is given by:
   $$v_{t+1}= \beta v_t + (1-\beta) \nabla J(\theta_t)$$ where:
   • \(v_t\) is the momentum at time step \(t\),
   • \(\nabla J(\theta_t)\) is the gradient of the cost function \(J\) with respect to the parameters \(\theta\) at time step \(t\),
   • \(\beta\) is the momentum parameter, typically set to a value close to 1, e.g., 0.9.
   • Then, the parameter \(\theta\) are updated using the momentum term: $$\theta_{t+1} = \theta_t - \eta v_{t+1}$$ where \(\eta\) is the learning rate.
2. Explanation of Formulas:
   • The first term in the update equation for \(v\) is the momentum term (\(\beta v_t\)), which is the previous momentum scaled by the momentum parameter \(\beta\).
   • The second term in the update equation is the gradient of the cost function scaled by (1-\(\beta\)), which gives the contribution of the current gradient.
   • The momentum term effectively remembers the direction of previous gradients and reinforces the current direction if gradients keep pointing in the same direction, thus helping to speed up convergence.
   • If the gradients keep changing direction (e.g., during oscillations), the momentum term helps to smooth out these oscillations by accumulating gradients in a consistent direction.
3. Advantages of Momentum:
   • Helps accelerate convergence, especially in the presence of high curvature or noisy gradients.
   • Dampens oscillations and overshooting in the optimization process, leading to more stable and efficient training.
   • Helps to escape local minima or saddle points by accumulating momentum to push through flat regions.
4. Choosing the Momentum Parameter \(\beta\):
   • The momentum parameter \(\beta\) typically ranges from 0.8 to 0.999.
   • A higher value of \(\beta\) takes the algorithm more "momentum-heavy," which can help in smoothing our oscillations but might overshoot minima.
   • A lower value of \(\beta\) makes the algorithm more responsive to recent gradients but might slow down convergence.

5. Adam (Adaptive Moment Estimation):

Algorithm Overview:

1. Initialization: First Initialize parameters:
   • \(\theta_0\): Model parameters (weights and biases).
   • \(m_0\) = 0: Initial first moment vector (mean),
   • \(v_0\) =0: Initial second moment vector (uncentered variance).
   • \(\beta_1, \beta_2 \in [0,1)\): Exponential decay rates for moment estimates.
   • \(\eta\): Learning rate.
   • \(\epsilon\): small constant to prevent division by zero. Defaults to 1e-8.
2. Update at each time step \(t\):
   • Compute gradient:
   $$g_t = \nabla J(\theta_t)$$ where \(J\) is the loss function.
   • Update biased first moment estimate:
   $$m_t = \beta_1\cdot m_{t-1} +(1-\beta_1)\cdot g_t$$
   • Update biased second raw moment estimate:
   $$v_t = \beta_2 \cdot v_{t-1} + (1-\beta_2)\cdot g_t^2$$
   • Correct bias in first moment:
   $$\hat{m}_t = \frac{m_t}{1-\beta_1^t}.$$
   • Correct bias in second moment:
   $$\hat{v}_t = \frac{v_t}{1-\beta_2^t}$$
   • Update parameters:
   $$\theta_{t+1} = \theta_t - \eta\cdot \frac{\hat{m}_t}{\sqrt{\hat{v}_t}+\epsilon} $$

Detailed Explanation of Formulas:

1. First Moment Estimation (Mean):
$$m_t = \beta_1 \cdot m_{t-1} +(1-\beta_1)\cdot g_t$$ where:
• \(m_t\): Biased first moment estimate (mean of gradients)
• \(\beta_1\): Exponential decay rate for the first moment.
• \(g_t\): Gradient at time step.
2. Second Moment Estimation (Uncentered Variance):
$$v_t = \beta_2 \cdot v_{t-1}+(1-\beta_2)\cdot g_t^2$$ where:
• \(v_t\): Biased second raw moment estimate (uncentered variance of gradients).
• \(\beta_2\): Exponential decay rate for the second moment.
• \(g_t^2\): Element-wise square of the gradient at time step \(t\).
3. Bias Correction:
$$\hat{m}_t = \frac{m_t}{1-\beta_1^t}$$ and $$\hat{v}_t = \frac{v_t}{1-\beta_2^t}.$$ where:
• Corrects bias in the first and second moment estimates, especially during the initial time steps when \(m_t\) and \(v_t\) are biased towards zero.
4. Parameter Update:
$$\theta_{t+1} = \theta_t -\eta \cdot \frac{\hat{m}_t}{\sqrt{\hat{v}_t}+\epsilon}.$$ where:
• Corrects bias in the first and second moment estimates, especially during the initial time steps when \(m_t\) and \(v_t\) are biased towards zero.
5. Parameter Update:
$$\theta_{t+1} = \theta_t - \eta\cdot \frac{\hat{m}_t}{\sqrt{\hat{v}_t}+\epsilon}.$$
• Updates the model parameters using the corrected first and second moment estimates.
• \(\eta\): Learning rate.
• \(\epsilon\): Small constant to prevent division by zero.

Key Features:

• Adaptive Learning Rate: The learning rate is adjusted for each parameter based on the estimates of the first and second moments of the gradients.
• Bias Correction: Adam corrects the bias in the moment estimates, especially at the beginning of training.
• Momentum: The first moment term \(m_t\) acts like a momentum term, allowing the algorithm to accelerate in the relevant direction and dampen oscillations.
• Efficiency: Adam is computationally efficient and requires little memory.

6. RMSprop (Root Mean Square Propagation):

Overview: RMSprop is an extension of the gradient descent optimization algorithm that aims to improve convergence speed and stability, especially in the presence of sparse gradients or noisy data. It accomplishes this by adjusting the learning rates of each parameter individually based on the magnitude of recent gradients.

Algorithm Steps:

1. Initialize Parameters: Initialize model parameters \(\theta\), typically randomly or using pre-trained values. Initialize a decay rate \(\beta\), usually close to 1, and a small constant \(\epsilon\) for numerical stability.
2. Initialize Variables: Initialize an accumulation variable \(v\) to store the exponentially weighted moving average (EWMA) of squared gradients.
3. Compute Gradients: Compute the gradients of the loss function with respect to the parameters \(\nabla J(\theta)\) using backpropagation.
4. Update Accumulation: Update the accumulation variable \(v\) by taking an EWMA of the squared gradients:
$$v = \beta v+(1-\beta)(\nabla J(\theta))^2$$ where \(\beta\) is the decay rate \((\nabla J(\theta))^2\) represents element-wise squaring of the gradients.
5. Update Parameters: Update the parameters \(\theta\) using the RMSprop update rule:
$$\theta = \theta - \eta \frac{\nabla J(\theta)}{\sqrt{v}+\epsilon}$$ where \(\eta\) is the learning rate and \(\epsilon\) is a small constant added for numerical stability to avoid division by zero.

Detailed Explanation:

1. Accumulation of Squared Gradients \(v\): RMSprop maintains an exponentially decaying average of squared gradients using the parameter \(\beta\). This moving average helps smooth out the gradient updates and adaptively adjust the learning rates.
2. Normalization of Gradients: Before updating the parameters, RMSprop normalizes the gradients by dividing them by the square root of the accumulated squared gradients plus a small constant \(\epsilon\). This Normalization scales down the learning rates for parameters with large gradients and vice versa.
3. Adaptive Learning Rates: By adjusting the learning rates based on the magnitude of gradients, RMSprop adapts to the geometry of the loss function and speeds up convergence, especially in deep neural networks with complex and non-convex surfaces.

Key Advantages:

1. Adaptive Learning Rates: RMSprop adapts the learning rates for each parameter individually based on the recent gradient history, leading to faster convergence and improved stability.
2. Sparse Data Handling: The algorithm performs well with sparse data or noisy gradients, thanks to its adaptive nature and normalization of gradients.
3. Robustness: RMSprop is robust to variations in hyperparameters and works well across different architectures and datasets.

Summary: