Optimization - Gradient Descent

calendar_today May 7, 2025 schedule 12 min read

1. Welcome and Icebreaker:

Fun Question: Imagine you’re on a foggy mountain and want to reach the lowest valley. You can only feel the slope under your feet. How would you decide which way to step?
Share: Can anyone think of a time they tried to find the “best” way to do something by making small adjustments and seeing if it improved things?

2. Outline the Session:

Agenda:
1. Welcome & Icebreaker (5 min)
2. What is Optimization in Machine Learning? (15 min)
3. Introducing Gradient Descent: The Core Idea (20 min)
4. The Learning Rate (15 min)
5. Types of Gradient Descent: Batch, Mini-batch, Stochastic (20 min)
6. Live Coding: Implementing Gradient Descent for Linear Regression (25 min)
7. Task: Conceptual Questions & Modifying Code (15 min)
8. Q&A and Wrap-up (5 min)
Learning Outcomes: By the end of this session, you will be able to:
- Explain the role of optimization in machine learning.
- Describe the intuition and mechanics of the Gradient Descent algorithm.
- Understand the importance of the learning rate.
- Differentiate between Batch, Mini-batch, and Stochastic Gradient Descent.
- Implement a basic Gradient Descent algorithm in Python.
Structure: We’ll start with the “why” of optimization, then dive into the “how” of Gradient Descent with concepts, variations, and a practical coding example.
Interactivity: This is a core ML algorithm! Please ask questions, share your understanding, and engage with the coding part. Your active participation will make it click.

3. Concept Explanation:

What is Optimization in Machine Learning?

At its heart, training a machine learning model is an optimization problem. We have a model (e.g., a linear regressor, a neural network) with some adjustable parameters (also called weights or coefficients). We also have a cost function (or loss function) that measures how well our model performs on the training data. A high cost means poor performance (e.g., large errors in prediction), and a low cost means good performance.

The goal of optimization in ML is to find the set of model parameters that minimizes the cost function. By minimizing the cost, we are essentially making our model as accurate as possible on the data it has seen.

Think of it like tuning a radio. The position of the tuning knob is the parameter. The clarity of the sound is inversely related to the “cost” (static is high cost, clear music is low cost). You adjust the knob (parameter) to minimize the static (cost) and get the best signal.

Key Components:

Parameters (θ): The values our model uses to make predictions. These are what we adjust.
Cost Function (J(θ)): A function that takes the parameters and the training data, and outputs a single number representing the “error” or “cost” of using those parameters.
- Example for Linear Regression: Mean Squared Error (MSE) J(θ) = (1/2m) * Σ(h_θ(x_i) - y_i)^2, where h_θ(x_i) is the prediction for example i and y_i is the true value.
Optimization Algorithm: The method used to find the θ that minimizes J(θ).

Introducing Gradient Descent: The Core Idea

Gradient Descent is one of the most popular and foundational optimization algorithms used in machine learning. It’s an iterative algorithm that takes steps in the direction of the steepest decrease of the cost function.

Remember our discussion on gradients? The gradient ∇J(θ) of the cost function J(θ) points in the direction of the steepest increase of J. Therefore, to decrease J, we should move in the opposite direction of the gradient, i.e., -∇J(θ).

The Algorithm:

Initialize parameters (θ): Start with some initial values for the model parameters (e.g., zeros, or small random numbers).
Repeat until convergence: a. Calculate the gradient: Compute ∇J(θ), which is the vector of partial derivatives of the cost function with respect to each parameter [∂J/∂θ_0, ∂J/∂θ_1, ..., ∂J/∂θ_n]. b. Update parameters: Adjust each parameter θ_j by taking a step in the negative gradient direction: θ_j := θ_j - α * (∂J/∂θ_j) Where: * θ_j is the j-th parameter. * α (alpha) is the learning rate, a small positive number that controls the size of the step we take. * ∂J/∂θ_j is the partial derivative of the cost function with respect to θ_j.

Intuition (Foggy Mountain Analogy):

You are on a foggy mountain (J(θ) is the height at your current position θ).
You want to reach the lowest valley (minimize J(θ)).
You can only feel the slope of the ground beneath your feet (this is the gradient ∇J(θ)).
To go downhill, you step in the direction opposite to the steepest uphill slope (i.e., in the direction of -∇J(θ)).
The size of your step is the learning rate α.
You repeat this process, taking step after step, hopefully descending into a valley.

Stopping: We may stop when parameter changes or loss improvements become small, or when a maximum number of iterations is reached. These are stopping criteria, not proof that the global minimum has been found; training can stop on a plateau or before reaching a useful solution.

The Learning Rate (α)

The learning rate α is a crucial hyperparameter in Gradient Descent. It determines how big of a step we take in each iteration.

If α is too small: Gradient descent will be very slow to converge. It will take tiny steps, requiring many iterations to reach the minimum.
If α is too large: Gradient descent might overshoot the minimum. It could oscillate around the minimum or even diverge (the cost function might increase instead of decrease).
With a suitable α: Gradient descent may make stable progress toward a minimum, but the result depends on the objective, initialization, and learning-rate schedule.

Choosing the right learning rate often involves experimentation. Common practice is to try several values (e.g., 0.001, 0.003, 0.01, 0.03, 0.1, 0.3, 1) and see which one works best for the specific problem by monitoring the cost function over iterations. Sometimes, adaptive learning rates are used, where α changes during training.

Types of Gradient Descent

The way we calculate the gradient ∇J(θ) (specifically, how much data we use to calculate it in each step) leads to different variants of Gradient Descent:

Batch Gradient Descent (BGD):
- In each iteration, the gradient is calculated using the entire training dataset.
- Pros: For a differentiable convex objective with suitable smoothness and learning-rate conditions, full-batch gradient descent can converge to a global minimum. For non-convex objectives, convergence is not guaranteed to a local minimum; a stationary point can also be a saddle.
- Cons: Can be very slow and computationally expensive for large datasets because it processes all training examples before making a single update.
- The update rule is: θ := θ - α * ∇J_all(θ) where ∇J_all is the gradient over all m training examples.
Stochastic Gradient Descent (SGD):
- In each iteration, the gradient is calculated using only a single training example chosen randomly (or sequentially).
- Pros: Much faster iterations than BGD, especially for large datasets. Can escape shallow local minima more easily due to the noisy updates.
- Cons: The path to the minimum is much noisier (the cost function will fluctuate). It might not converge exactly to the minimum but will typically get very close. The learning rate often needs to be slowly decreased over time to help convergence.
- The update rule for the i-th example: θ := θ - α * ∇J_i(θ) where ∇J_i is the gradient for the i-th example.
Mini-Batch Gradient Descent (MBGD):
- A compromise between BGD and SGD. In each iteration, the gradient is calculated using a small batch of training examples (e.g., 32, 64, 128 examples).
- Pros: More stable convergence than SGD. Computationally more efficient than BGD (allows for vectorization benefits from processing a batch). Often the preferred method in practice, especially for training neural networks.
- Cons: Introduces an additional hyperparameter (batch size). The updates are still somewhat noisy compared to BGD.
- The update rule for a mini-batch B: θ := θ - α * ∇J_B(θ) where ∇J_B is the gradient over the examples in the mini-batch.

Choosing the type:

If the dataset is small (e.g., < 2000 examples), Batch GD might be feasible.
For larger datasets, Mini-batch GD is usually the go-to. SGD can be used but often requires more careful tuning of the learning rate schedule.

Common Pitfalls:

Non-convex Objectives: Neural-network objectives can have local minima and saddle points. Gradient descent may reach a stationary point or fail to converge with unsuitable settings; it is not guaranteed to find a local or global minimum. Momentum and random restarts can help in some cases, but do not provide a general guarantee.
Feature Scaling: If features have very different scales (e.g., one feature from 0-1, another from 0-1000), the cost function surface can become elongated, slowing down GD. It’s crucial to scale features (e.g., normalization or standardization) before applying GD.
Vanishing/Exploding Gradients: In deep neural networks, gradients can become extremely small (vanish) or extremely large (explode) as they are propagated backward, hindering learning. Techniques like careful initialization, non-saturating activation functions, and batch normalization address this.

4. Live Coding Demonstration: Gradient Descent for Linear Regression

We’ll implement Batch Gradient Descent from scratch to find the parameters (slope m and intercept c) for a simple linear regression model y = mx + c.

Cost Function (MSE): J(m, c) = (1/N) * Σ(y_i - (mx_i + c))^2 (using N instead of 2m for simplicity here, factor of 1/2 is for calculus convenience, doesn’t change minimum location)

Partial Derivatives:

∂J/∂m = (-2/N) * Σ x_i * (y_i - (mx_i + c))
∂J/∂c = (-2/N) * Σ (y_i - (mx_i + c))

Update Rules:

m := m - α * ∂J/∂m
c := c - α * ∂J/∂c

import numpy as np
import matplotlib.pyplot as plt

# Generate some sample data for linear regression
np.random.seed(42)
X = 2 * np.random.rand(100, 1)  # Feature (e.g., hours studied)
y = 4 + 3 * X + np.random.randn(100, 1) # Target (e.g., exam score) y = 4 + 3x + noise

# Add a column of ones to X for the intercept term (bias) - an alternative way to handle c
# X_b will be [1, x_value] for each row. Parameters will be [c, m]
X_b = np.c_[np.ones((100, 1)), X] # Add x0 = 1 to each instance

# --- Batch Gradient Descent --- 
learning_rate = 0.1
n_iterations = 1000
m_samples = 100 # Number of training examples

# Initialize parameters (theta will contain c and m)
# theta[0] = c (intercept), theta[1] = m (slope)
theta = np.random.randn(2, 1) # Random initialization [c; m]

cost_history = []
theta_history = [] # To store parameters at each step for visualization

print(f"Initial theta (c, m): {theta.ravel()}")

for iteration in range(n_iterations):
    # 1. Calculate predictions
    # predictions = X_b.dot(theta)  is equivalent to m*X + c if X_b has [1, X] and theta is [c; m]
    predictions = X_b.dot(theta)
    
    # 2. Calculate error
    errors = predictions - y
    
    # 3. Calculate cost (MSE)
    cost = (1/m_samples) * np.sum(errors**2)
    cost_history.append(cost)
    theta_history.append(theta.copy()) # Store a copy
    
    # 4. Calculate gradients
    # gradient for c (theta[0]): (2/m_samples) * X_b[:,0].T.dot(errors) but X_b[:,0] is all 1s
    # gradient for m (theta[1]): (2/m_samples) * X_b[:,1].T.dot(errors)
    # More general: gradients = (2/m_samples) * X_b.T.dot(errors)
    gradients = (2/m_samples) * X_b.T.dot(errors)
    
    # 5. Update parameters
    theta = theta - learning_rate * gradients
    
    if iteration % 100 == 0:
        print(f"Iteration {iteration}: Cost = {cost:.4f}, Theta (c, m) = {theta.ravel()}")

print(f"Final theta (c, m): {theta.ravel()}")
print(f"Expected theta (c, m) approx: [4, 3]")

# Plotting the cost function over iterations
plt.figure(figsize=(12, 5))
plt.subplot(1, 2, 1)
plt.plot(range(n_iterations), cost_history)
plt.xlabel("Iteration")
plt.ylabel("Cost (MSE)")
plt.title("Cost Function Convergence")

# Plotting the data and the learned regression line
plt.subplot(1, 2, 2)
plt.scatter(X, y, alpha=0.7, label='Data')
X_line = np.linspace(float(X.min()), float(X.max()), 100).reshape(-1, 1)
X_line_b = np.c_[np.ones((len(X_line), 1)), X_line]
plt.plot(X_line, X_line_b.dot(theta), color='red', label='Gradient Descent Fit')

# For comparison, let's calculate the optimal solution using the Normal Equation
X_for_normal = np.c_[np.ones((100, 1)), X]
theta_normal_equation = np.linalg.inv(X_for_normal.T.dot(X_for_normal)).dot(X_for_normal.T).dot(y)
plt.plot(X_line, X_line_b.dot(theta_normal_equation), color='green', linestyle='--', label='Normal Equation Fit')
print(f"Theta from Normal Equation (c,m): {theta_normal_equation.ravel()}")

plt.xlabel("X (Feature)")
plt.ylabel("y (Target)")
plt.title("Linear Regression Fit")
plt.legend()
plt.tight_layout()
plt.show()

# --- (Optional) Visualization of parameter updates ---
# This can be more complex, showing how (c,m) moved on a contour plot of the cost function

Explanation of Code:

Data Generation: We create synthetic data with a known linear relationship (y = 4 + 3x + noise).
X_b: We add a column of ones to X. If theta = [c, m]^T and X_b = [1, x], then X_b.dot(theta) calculates 1*c + x*m = c + mx, which is our linear model. This is a common trick to handle the intercept term within matrix multiplication.
Initialization: theta (containing c and m) is initialized randomly. learning_rate and n_iterations are set.
Iteration Loop:
- predictions = X_b.dot(theta): Calculate y_hat for all data points.
- errors = predictions - y: Calculate the difference.
- cost = ...: Calculate Mean Squared Error.
- gradients = (2/m_samples) * X_b.T.dot(errors): This is the vectorized form for calculating both ∂J/∂c and ∂J/∂m simultaneously. X_b.T.dot(errors) effectively performs the summations required in the gradient formulas.
- theta = theta - learning_rate * gradients: Update parameters.
Output & Plotting: We print the final parameters and plot the cost history (should decrease) and the fitted line against the data.
Normal Equation (for comparison): The Normal Equation is an analytical solution for linear regression (theta = (X^T X)^(-1) X^T y). We use it to see how close our GD result is to the optimal one.

Experiment: Try changing the learning_rate. If it’s too high (e.g., 0.5 or 1 for this data), you might see the cost explode. If too low (e.g., 0.001), convergence will be slow.

5. Tasks:

Conceptual Questions:

What would happen if you initialized all your parameters theta to zero in Gradient Descent for linear regression? Would it still work? Why or why not?
Explain in your own words the difference between Batch GD, Mini-batch GD, and SGD. What are the trade-offs?
If your cost function is decreasing very slowly after many iterations, what are two things you could try to change in your Gradient Descent setup?
Why is feature scaling important for Gradient Descent?

Code Modification/Experimentation (using the provided Python code):

Learning Rate: Change the learning_rate to a much smaller value (e.g., 0.005) and a much larger value (e.g., 0.9). Observe how the cost function plot changes and how many iterations it takes to get a good fit (or if it diverges).
Number of Iterations: With a reasonable learning rate (e.g., 0.1), reduce n_iterations significantly (e.g., to 50). How does this affect the final fitted line?
(Optional) Stochastic Gradient Descent: Try to modify the Batch GD code to implement Stochastic Gradient Descent. You’ll need to loop through individual training examples in each iteration (or epoch) and update theta based on the gradient from that single example. You might need to run it for more epochs (passes through the entire dataset).

6. Q&A and Wrap-up:

Open floor for questions about Gradient Descent, its variants, implementation details, or challenges.
Reiterate: Gradient Descent is a general optimization tool. We showed it for linear regression, but the same principles apply to logistic regression, neural networks, etc., just with different cost functions and gradient calculations.
Preview: We’ll see more advanced optimization algorithms and how GD is used in training more complex models.