What is gradient descent?

Theoretical Background

Gradient descent is a first-order iterative optimization algorithm for finding the minimum of a function. The key idea is to use the gradient (or approximate) of the function to move in the direction of steepest descent, iteratively updating the model parameters to reduce the cost function.

• Batch Gradient Descent: Updates occur after processing the entire dataset. It provides a direct path to the minimum, but requires extensive computation and memory, making it less ideal for very large datasets.

• Stochastic Gradient Descent (SGD): Updates occur after each individual example, leading to faster iterations but more variance in the convergence path. It is well-suited for online learning and large-scale problems.

• Mini-batch Gradient Descent: Updates occur after processing a subset of the data. It is a compromise between batch and stochastic methods, offering faster convergence than batch and more stability than stochastic.

Practical Applications

• In deep learning, mini-batch gradient descent is commonly used because it efficiently uses the GPU memory with parallel processing.
• SGD is often used in online learning scenarios where data arrives in a stream.
• Batch gradient descent is typically used when computational resources are not a constraint and full dataset processing is feasible.

Code Example

# Example of Mini-batch Gradient Descent
import numpy as np

# Hypothetical loss function (y = x^2)
def loss_function(x):
    return x**2

def gradient(x):
    return 2*x

# Parameters for gradient descent
learning_rate = 0.1
iterations = 100
batch_size = 20

# Initial value
x = np.random.rand()

for i in range(iterations):
    grad = gradient(x)
    x -= learning_rate * grad

print(f"Optimized x value: {x}")

External References

• An overview of gradient descent optimization algorithms
• CS231n: Convolutional Neural Networks for Visual Recognition

Diagram

graph LR
A[Start] --> B[Initialize Parameters]
B --> C{Gradient Descent Type}
C -->|Batch| D[Compute Gradient on Entire Dataset]
C -->|Stochastic| E[Compute Gradient on One Sample]
C -->|Mini-batch| F[Compute Gradient on Subset]
D --> G[Update Parameters]
E --> G
F --> G
G --> H[Check Convergence]
H -->|Yes| I[Stop]
H -->|No| C