Home
Deep Learning For Vision

Gradient Descent

 

Gradient descent is a fundamental optimization technique widely used in deep learning and machine learning to minimize functions, typically the loss or error function, by iteratively moving towards the minimum value.

1. Concept and Principle

  • Gradient descent solves optimization problems of the form:

    min⁡wf(w)\min_{w} f(w)

    where f(w)f(w) is a differentiable function (often a loss or cost function in machine learning).

  • The algorithm proceeds by moving in the direction of the negative gradient, which points towards the fastest local decrease of the function.

2. Update Rule

  • At each iteration, parameters are updated as:

    wnext=wcurrent−α∇f(wcurrent)w_{\text{next}} = w_{\text{current}} - \alpha \nabla f(w_{\text{current}})

    where:

    • ww = parameter vector

    • α\alpha = learning rate (step size)

    • ∇f(w)\nabla f(w) = gradient of ff at ww

  • If the gradient is zero, the update stops and the minimum (local or global) is found.

3. Algorithm Steps

  1. Initialize the parameters randomly.

  2. Compute the gradient ∇f(w)\nabla f(w) of the loss with respect to the parameters.

  3. Update the parameters using the rule above.

  4. Repeat steps 2-3 until convergence or for a set number of iterations.

Pseudo-code

python
initialize w
for i in range(num_iterations):
    grad = gradient_of_loss_function(w)
    w = w - learning_rate * grad
return w

4. Variants

  • Batch Gradient Descent: The gradient is computed using the whole dataset at each iteration.

  • Stochastic Gradient Descent (SGD): The gradient is computed using one randomly chosen example at a time.

  • Mini-batch Gradient Descent: The gradient is computed using a small subset (batch) of the data per iteration.

5. Example

To minimize the quadratic function:

Q(x,y)=(x−2)2+(y−3)2Q(x, y) = (x-2)^2 + (y-3)^2

The gradient is:

∇Q(x,y)=[2(x−2), 2(y−3)]\nabla Q(x, y) = [2(x-2),\ 2(y-3)]

The update steps are:

x←x−α⋅2(x−2)x \leftarrow x - \alpha \cdot 2(x-2) y←y−α⋅2(y−3)y \leftarrow y - \alpha \cdot 2(y-3)

By repeating the above updates, (x,y)(x, y) converge to (2,3)(2, 3).

6. Applications

  • Training machine learning models: Linear regression, logistic regression, neural networks.

  • Minimizing error/loss: Fitting the best solution to the data.

7. Choosing Learning Rate

  • A too-small learning rate leads to slow convergence.

  • A too-large learning rate may cause divergence or oscillations.

8. Summary

  • Gradient descent iteratively moves towards the minimum by following the negative gradient.

  • It forms the backbone of model training in deep learning and machine learning.