Gradient descent is a fundamental optimization technique within machine learning and other fields. It was introduced by the physicist Peter Molnar in 1964 and later independently rediscovered by other researchers.

Intuition

The basic idea of gradient descent is to iteratively update model parameters in the direction that minimizes a performance metric, often represented by a cost function or loss function.

Mathematically, this process is characterized by the gradient of the cost function, computed using backpropagation in the case of neural networks.

Formulation

Let $J(\boldsymbol{\theta})$ be the cost function and $\boldsymbol{\theta}$ be the parameter vector.

The update rule for each parameter can be expressed as:

$$\theta_j := \theta_j - \alpha \frac{\partial J(\boldsymbol{\theta})}{\partial \theta_j}$$

Here, $\alpha$ is the learning rate and $\frac{\partial J(\boldsymbol{\theta})}{\partial \theta_j}$ is the partial derivative of the cost function with respect to the parameter $\theta_j$.

Visual Analogy

One can visualize gradient descent as a person trying to find the bottom of a valley (the cost function).

The individual takes small steps downhill (representing parameter updates), guided by the slope (the gradient) and the step size $\alpha$.

Mode of Operation

• Batch Gradient Descent: Computes the gradient for the entire dataset and takes a step. This can be slow for large datasets due to its high computational cost.

• Stochastic Gradient Descent (SGD): Computes the gradient for each data point and takes a step. It’s faster but more noisy.

• Mini-batch Gradient Descent: Computes the gradient for small batches of data, offering a compromise between batch and stochastic methods.

Considerations

Learning Rate

Selecting an appropriate learning rate is crucial.

• If it’s too large, overshoot may occur, and the algorithm could fail to converge.
• If it’s too small, the algorithm might be slow or get trapped in local minima.

Convergence

Stopping criteria, such as a predefined number of iterations or a threshold for the change in the cost function, are employed to determine when the algorithm has converged.

Local Minima

While gradient descent provides no guarantee of finding the global minimum, in practice, it often suffices to reach a local minimum.

Code Example: Batch Gradient Descent

Here is the Python code:

def batch_gradient_descent(X, y, theta, alpha, iterations):
    m = len(y)  # Number of training examples
    
    for _ in range(iterations):
        error = X.dot(theta) - y  # Compute the error
        gradient = X.T.dot(error) / m  # Compute the gradient
        theta -= alpha * gradient  # Update parameters
    
    return theta

Beyond the Basics

• Momentum: Incorporates the running average of past gradients to accelerate convergence in the relevant directions.
• Adaptive Learning Rates: Algorithms like AdaGrad, RMSProp, and Adam adjust learning rates adaptively for each parameter.
• Beyond the Gradient: Evolutionary algorithms, variational methods, and black-box optimization techniques are avenues for optimization beyond the gradient.