tochastic Gradient Descent (SGD)

16. Stochastic Gradient Descent (SGD)

Stochastic Gradient Descent (SGD) is an optimization algorithm used to minimize an objective function in machine learning and deep learning. It is a variant of the gradient descent algorithm but differs in the way it computes the gradient.

In standard Gradient Descent (GD), the gradient of the objective function is calculated using the entire dataset, which can be computationally expensive when the dataset is large. On the other hand, in Stochastic Gradient Descent, the gradient is computed using a single data point (or a small batch of data points) at each iteration, which significantly reduces the computational cost and makes it more efficient for large datasets.

---

16.1 Stochastic Gradient Descent (SGD) Algorithm

The basic update rule for SGD is:

$${\mathbf{x}}_{k+1}={\mathbf{x}}_k-\eta \mathrm{\nabla }f({\mathbf{x}}_k,{\mathbf{x}}_i)$$

Where:
- ${\mathbf{x}}_k$ is the current parameter vector at iteration $k$,
- $\eta$ is the learning rate (step size),
- $\mathrm{\nabla }f({\mathbf{x}}_k,{\mathbf{x}}_i)$ is the gradient of the objective function with respect to the $k$-th data point ${\mathbf{x}}_i$,
- ${\mathbf{x}}_{k+1}$ is the updated parameter vector.

Instead of computing the gradient using the entire dataset, SGD computes the gradient for a single data point ${\mathbf{x}}_i$ at each iteration.

---

16.2 Advantages of SGD

1. Efficiency:

2. SGD is much faster than regular gradient descent when the dataset is large, as it updates the parameters after looking at only one sample at a time.

3. Online Learning:

4. SGD can be used for online learning, where the model is trained incrementally as new data comes in.

5. Convergence:

6. While SGD can be noisy due to the randomness introduced by using a single data point at a time, this noise can sometimes help escape local minima in non-convex optimization problems (e.g., in neural networks).

7. Memory Efficiency:

8. Since SGD only needs one data point at a time, it requires less memory compared to batch gradient descent, which needs to store the entire dataset for each gradient calculation.

---

16.3 Challenges with SGD

1. Noisy Convergence:

2. Because of the randomness, the algorithm tends to oscillate around the optimal solution and may not converge smoothly to the global minimum. However, this can be mitigated by using techniques like learning rate schedules or momentum.

3. Choosing a Proper Learning Rate:

4. A large learning rate can cause the algorithm to overshoot the minimum, while a small learning rate may result in slow convergence. Learning rate decay is often used to adapt the learning rate over time.

5. Local Minima:

6. SGD can get stuck in local minima, especially in highly non-convex objective functions like those encountered in deep learning models.

---

16.4 Variants of SGD

1. Mini-batch Gradient Descent:

2. A compromise between batch gradient descent and stochastic gradient descent. Instead of computing the gradient for a single data point, the gradient is computed for a small batch of data points. This often leads to faster convergence while still retaining the benefits of stochastic updates.

3. Momentum:

4. Momentum helps accelerate SGD in the relevant direction and dampens oscillations. The update rule with momentum is:

[
\mathbf{v}{k+1} = \beta \mathbf{v}_k + (1 - \beta) \nabla f(\mathbf{x}_k)
]
[
\mathbf{x}} = \mathbf{xk - \eta \mathbf{v}
]

Where $\beta$ is a momentum coefficient. This method helps in smoother convergence by "remembering" the previous gradients.

1. Adam (Adaptive Moment Estimation):
2. Adam combines the advantages of both momentum and adaptive learning rate methods. It computes adaptive learning rates for each parameter by considering both the first and second moments of the gradients.

The update rule is:

[
\mathbf{m}{k+1} = \beta_1 \mathbf{m}_k + (1 - \beta_1) \nabla f(\mathbf{x}_k)
]
[
\mathbf{v}} = \beta_2 \mathbf{vk + (1 - \beta_2) \nabla f(\mathbf{x}_k)^2
]
[
\mathbf{x}} = \mathbf{xk - \eta \frac{\mathbf{m}}}{\sqrt{\mathbf{v}_{k+1}} + \epsilon
]

Where ${\beta }_1$ and ${\beta }_2$ are hyperparameters controlling the decay rates of the moving averages of the gradient and its square, and $ϵ$ is a small constant to prevent division by zero.

---

16.5 Example of SGD: Minimizing a Simple Function

Let’s consider a simple example of minimizing the quadratic function $f(x)=x^2$ using Stochastic Gradient Descent.

1. Objective Function: $f(x)=x^2$
2. Gradient: $\mathrm{\nabla }f(x)=2x$
3. Learning Rate: $\eta =0.1$
4. Initial Guess: $x_0=3$

Iteration 1:
- Compute the gradient: $\mathrm{\nabla }f(3)=2\times 3=6$
- Update: $x_1=3-0.1\times 6=2.4$

Iteration 2:
- Compute the gradient: $\mathrm{\nabla }f(2.4)=2\times 2.4=4.8$
- Update: $x_2=2.4-0.1\times 4.8=1.92$

And so on. After several iterations, $x$ converges to 0, which is the global minimum.

---

16.6 Practice Problem: SGD

1. Use SGD to minimize the function $f(x)=x^4-3x^3+2x^2$ starting from $x_0=2$ with a learning rate $\eta =0.05$.

---

17. Dimensionality Reduction and PCA (Principal Component Analysis)

Dimensionality reduction refers to techniques used to reduce the number of features in a dataset while retaining as much information as possible. It's especially useful for visualizing high-dimensional data or speeding up machine learning algorithms.

Principal Component Analysis (PCA) is one of the most commonly used dimensionality reduction techniques. PCA is a linear transformation that projects data onto a smaller subspace (lower dimension), maximizing the variance in the data.

---

17.1 PCA Overview

PCA works by finding a new set of orthogonal axes (principal components) in the data space. The goal is to project the data onto these axes, such that the first principal component captures the most variance in the data, the second captures the second most, and so on.

1. Covariance Matrix:
2. The first step in PCA is to compute the covariance matrix of the dataset, which tells us how the features of the data vary together.

[
\mathbf{C} = \frac{1}{n-1} \sum_{i=1}^{n} (\mathbf{x}_i - \mathbf{\mu})(\mathbf{x}_i - \mathbf{\mu})^T
]
Where $\mu$ is the mean of the dataset, and ${\mathbf{x}}_i$ is a data point.

1. Eigenvalues and Eigenvectors:

2. The next step is to compute the eigenvalues and eigenvectors of the covariance matrix. The eigenvectors represent the principal components, and the eigenvalues represent the amount of variance captured by each principal component.

3. Projection:

4. Finally, the data is projected onto the principal components, reducing its dimensionality.

---

17.2 Example of PCA

Let’s consider a dataset with two features (dimensions):

$$\mathbf{X}=\left[\begin{array}{cc}1& 2\\ 2& 3\\ 3& 4\\ 4& 5\end{array}\right]$$

1. Compute the covariance matrix.
2. Compute the eigenvalues and eigenvectors of the covariance matrix.
3. Project the data onto the first principal component.

---

17.3 Practice Problem: PCA

1. Perform PCA on a dataset with three features:
   [
   \mathbf{X} = $$\left[\begin{array}{ccccccccc}1& 2& 34& 5& 67& 8& 910& 11& 12\end{array}\right]$$
   ]
   and reduce it to 2 dimensions.

---

Would you like solutions for these problems, or would you like to continue with Optimization for Support Vector Machines?