Optimization
ipynb38 kBPython · 13 cellsExtra material of IN400
1. Calculus Essentials: Derivatives & Gradients
Overview
In Machine Learning, we optimize a model by minimizing a Loss Function . To do this, we need to know which direction to move the weights — this is where derivatives and gradients come in.
Single Variable: Derivative
- Derivative (): Measures the slope (rate of change) of a function at a point.
- Interpretation:
- If → function is increasing → move left (decrease ) to minimize
- If → function is decreasing → move right (increase ) to minimize
- If → potential minimum (or maximum, or saddle point)
Example: For , the derivative is
Multiple Variables: Gradient
-
Gradient (): A vector of partial derivatives for functions with multiple variables.
-
Formula:
-
Direction: Points in the direction of steepest ascent (uphill).
The Update Rule (Core Formula)
To minimize loss, we move in the opposite direction of the gradient:
where:
- (eta) = Learning Rate (step size, typically 0.001 to 0.1)
- = gradient of the loss function
- The minus sign = move downhill
import numpy as np
import matplotlib.pyplot as plt
# Example: f(x) = x^2 (simple parabola)
def f(x):
return x**2
def derivative_f(x):
"""Derivative: f'(x) = 2x"""
return 2 * x
# Test at different points
test_points = [3, 0, -5]
print("Understanding Derivatives:")
print("=" * 50)
for x_val in test_points:
slope = derivative_f(x_val)
print(f"\nAt x = {x_val}:")
print(f" Function value: f({x_val}) = {f(x_val)}")
print(f" Slope (derivative): f'({x_val}) = {slope}")
if slope > 0:
print(f" → Slope is POSITIVE → Move LEFT to minimize")
elif slope < 0:
print(f" → Slope is NEGATIVE → Move RIGHT to minimize")
else:
print(f" → Slope is ZERO → This is the MINIMUM!")
# Show one gradient descent step
learning_rate = 0.1
x_new = x_val - learning_rate * slope
print(f" Next step (η=0.1): x_new = {x_val} - 0.1 × {slope} = {x_new}")
# Visualization
x_range = np.linspace(-6, 6, 100)
plt.figure(figsize=(10, 6))
plt.plot(x_range, f(x_range), "b-", linewidth=2, label="f(x) = x²")
plt.scatter(
test_points,
[f(x) for x in test_points],
color="red",
s=100,
zorder=5,
label="Test points",
)
plt.axhline(y=0, color="k", linestyle="--", alpha=0.3)
plt.axvline(x=0, color="k", linestyle="--", alpha=0.3)
plt.grid(True, alpha=0.3)
plt.xlabel("x")
plt.ylabel("f(x)")
plt.title("Derivative tells us which direction to move")
plt.legend()
plt.show()2. Gradient Descent Variants
Overview
Gradient Descent is the fundamental algorithm for training machine learning models. It iteratively updates parameters to minimize the loss function. The key difference between variants is how many samples we use to estimate the gradient.
2.1 Batch Gradient Descent (Full Batch)
Definition
Uses ALL training samples ( samples) to compute the gradient at each iteration.
Gradient Formula
Characteristics
- ✅ Pros:
- Most accurate gradient estimate
- Smooth, stable convergence
- Guaranteed to reach minimum for convex functions
- ❌ Cons:
- Very slow for large datasets (must process all data per update)
- High memory usage
- Can get stuck in local minima for non-convex functions
When to Use
- Small datasets (< 10,000 samples)
- When you need very stable convergence
- When computational cost is not a concern
2.2 Stochastic Gradient Descent (SGD)
Definition
Uses ONE randomly selected sample at each iteration.
Gradient Formula
where is a randomly chosen index at iteration .
Characteristics
- ✅ Pros:
- Very fast updates (processes 1 sample at a time)
- Low memory usage
- Can escape local minima due to noise
- Good for online learning
- ❌ Cons:
- Noisy gradient estimates
- Erratic, zig-zagging path
- Never truly "converges" (oscillates around minimum)
- Harder to parallelize
When to Use
- Very large datasets (millions of samples)
- Online learning (streaming data)
- When you want to escape local minima
2.3 Mini-Batch Gradient Descent
Definition
Uses a small batch of samples (typically 16, 32, 64, or 128).
Gradient Formula
where is a random batch of size at iteration .
Characteristics
- ✅ Pros:
- Best of both worlds (speed + stability)
- Good gradient estimates with less noise than SGD
- Efficiently uses GPU/parallel processing
- Most commonly used in practice
- ❌ Cons:
- Requires tuning batch size
- Still has some noise (less than SGD)
When to Use
- Default choice for most problems
- Deep learning (neural networks)
- When using GPUs
Comparison Table
| Variant | Samples/Update | Speed | Accuracy | Noise | Use Case |
|---|---|---|---|---|---|
| Batch | All () | Slow | High | None | Small datasets |
| SGD | 1 | Fast | Low | High | Huge datasets, online |
| Mini-Batch | (e.g., 32) | Medium | Medium | Low | Most ML problems |
Learning Rate ()
- Too large: Overshoots minimum, diverges
- Too small: Converges very slowly
- Typical values: 0.001, 0.01, 0.1 (depends on problem)
- Advanced: Use learning rate schedules (decrease over time)
# ===================================
# BATCH GRADIENT DESCENT
# ===================================
print("=" * 60)
print("BATCH GRADIENT DESCENT (Uses ALL samples)")
print("=" * 60)
# Simple regression problem: y = 2x + noise
np.random.seed(42)
X = np.array([1, 2, 3, 4, 5]) # inputs
y = np.array([2.1, 3.9, 6.2, 8.1, 9.8]) # outputs (close to y = 2x)
# Model: y_pred = w * x (simple linear model, no bias)
w = 0.0 # initial weight
learning_rate = 0.01
n_samples = len(X)
print(f"\nDataset: {n_samples} samples")
print(f"X = {X}")
print(f"y = {y}")
print(f"\nInitial weight: w = {w}")
print(f"Learning rate: η = {learning_rate}\n")
# Run 5 iterations to show the process
for iteration in range(5):
# 1. Make predictions for ALL samples
predictions = w * X
# 2. Calculate errors for ALL samples
errors = predictions - y
# 3. Calculate gradient (average over all samples)
# For loss = (1/2n) * sum((w*x_i - y_i)^2), gradient = (1/n) * sum(x_i * (w*x_i - y_i))
gradient = (1 / n_samples) * np.sum(X * errors)
# 4. Update weight
w_old = w
w = w - learning_rate * gradient
# 5. Calculate total loss
loss = (1 / (2 * n_samples)) * np.sum(errors**2)
print(f"Iteration {iteration + 1}:")
print(f" Predictions: {predictions}")
print(f" Errors: {errors}")
print(f" Gradient: {gradient:.4f}")
print(f" Weight update: {w_old:.4f} → {w:.4f}")
print(f" Loss: {loss:.4f}\n")
print(f"Final weight after 5 iterations: w = {w:.4f}")
print(f"(True value should be close to 2.0)\n")# ===================================
# STOCHASTIC GRADIENT DESCENT (SGD)
# ===================================
print("=" * 60)
print("STOCHASTIC GRADIENT DESCENT (Uses 1 random sample)")
print("=" * 60)
# Same dataset
X = np.array([1, 2, 3, 4, 5])
y = np.array([2.1, 3.9, 6.2, 8.1, 9.8])
# Reset parameters
w = 0.0
learning_rate = 0.01
np.random.seed(42)
print(f"\nInitial weight: w = {w}")
print(f"Learning rate: η = {learning_rate}\n")
# Run 10 iterations (SGD needs more iterations since it's noisier)
for iteration in range(10):
# 1. Pick ONE random sample
idx = np.random.randint(0, len(X))
x_sample = X[idx]
y_sample = y[idx]
# 2. Make prediction for this ONE sample
prediction = w * x_sample
# 3. Calculate error for this ONE sample
error = prediction - y_sample
# 4. Calculate gradient from this ONE sample (no averaging!)
gradient = x_sample * error
# 5. Update weight
w_old = w
w = w - learning_rate * gradient
print(f"Iteration {iteration + 1}:")
print(f" Selected sample: x={x_sample}, y={y_sample}")
print(f" Prediction: {prediction:.4f}")
print(f" Error: {error:.4f}")
print(f" Gradient: {gradient:.4f}")
print(f" Weight update: {w_old:.4f} → {w:.4f}\n")
print(f"Final weight after 10 SGD iterations: w = {w:.4f}")
print(f"(Notice: more erratic updates, but still converging)\n")# ===================================
# MINI-BATCH GRADIENT DESCENT
# ===================================
print("=" * 60)
print("MINI-BATCH GRADIENT DESCENT (Uses small batch of samples)")
print("=" * 60)
# Same dataset
X = np.array([1, 2, 3, 4, 5])
y = np.array([2.1, 3.9, 6.2, 8.1, 9.8])
# Reset parameters
w = 0.0
learning_rate = 0.01
batch_size = 2 # Use 2 samples per batch
np.random.seed(42)
print(f"\nInitial weight: w = {w}")
print(f"Learning rate: η = {learning_rate}")
print(f"Batch size: m = {batch_size}\n")
# Run 5 iterations
for iteration in range(5):
# 1. Randomly select a mini-batch of samples
indices = np.random.choice(len(X), size=batch_size, replace=False)
X_batch = X[indices]
y_batch = y[indices]
# 2. Make predictions for the batch
predictions = w * X_batch
# 3. Calculate errors for the batch
errors = predictions - y_batch
# 4. Calculate gradient (average over batch)
gradient = (1 / batch_size) * np.sum(X_batch * errors)
# 5. Update weight
w_old = w
w = w - learning_rate * gradient
print(f"Iteration {iteration + 1}:")
print(f" Batch indices: {indices}")
print(f" X_batch: {X_batch}, y_batch: {y_batch}")
print(f" Predictions: {predictions}")
print(f" Errors: {errors}")
print(f" Gradient: {gradient:.4f}")
print(f" Weight update: {w_old:.4f} → {w:.4f}\n")
print(f"Final weight after 5 mini-batch iterations: w = {w:.4f}")
print(f"(Balanced between Batch GD stability and SGD speed)\n")# Visualizing all three variants on f(x) = x^2
def f(x):
return x**2
def gradient_f(x):
return 2 * x
# Setup
x_start = 50.0
learning_rate_batch = 0.01
learning_rate_sgd = 0.01
learning_rate_mini = 0.01
iterations = 50
# ===== BATCH GD =====
x_batch = x_start
history_batch = [x_batch]
for _ in range(iterations):
grad = gradient_f(x_batch) # exact gradient
x_batch = x_batch - learning_rate_batch * grad
history_batch.append(x_batch)
# ===== SGD =====
x_sgd = x_start
history_sgd = [x_sgd]
np.random.seed(42)
for _ in range(iterations):
# Add noise to simulate using single sample
noise = np.random.normal(0, 0.5)
grad_noisy = gradient_f(x_sgd) + noise
x_sgd = x_sgd - learning_rate_sgd * grad_noisy
history_sgd.append(x_sgd)
# ===== MINI-BATCH GD =====
x_mini = x_start
history_mini = [x_mini]
np.random.seed(42)
for _ in range(iterations):
# Add less noise (averaging over mini-batch reduces variance)
noise = np.random.normal(0, 0.2)
grad_mini = gradient_f(x_mini) + noise
x_mini = x_mini - learning_rate_mini * grad_mini
history_mini.append(x_mini)
# Plot comparison
plt.figure(figsize=(14, 5))
# Left plot: trajectories on the function
plt.subplot(1, 2, 1)
x_range = np.linspace(-60, 60, 200)
plt.plot(x_range, f(x_range), "gray", alpha=0.3, linewidth=2, label="f(x) = x²")
plt.plot(
history_batch,
[f(x) for x in history_batch],
"b-o",
markersize=3,
label="Batch GD",
alpha=0.7,
)
plt.plot(
history_sgd,
[f(x) for x in history_sgd],
"r-o",
markersize=3,
label="SGD",
alpha=0.7,
)
plt.plot(
history_mini,
[f(x) for x in history_mini],
"g-o",
markersize=3,
label="Mini-Batch GD",
alpha=0.7,
)
plt.xlabel("x")
plt.ylabel("f(x)")
plt.title("Convergence Paths")
plt.legend()
plt.grid(True, alpha=0.3)
# Right plot: x value over iterations
plt.subplot(1, 2, 2)
plt.plot(history_batch, "b-", label="Batch GD (smooth)", linewidth=2)
plt.plot(history_sgd, "r-", label="SGD (noisy)", linewidth=2, alpha=0.7)
plt.plot(history_mini, "g-", label="Mini-Batch GD (balanced)", linewidth=2, alpha=0.7)
plt.axhline(y=0, color="k", linestyle="--", alpha=0.3, label="Minimum (x=0)")
plt.xlabel("Iteration")
plt.ylabel("x value")
plt.title("x Value Over Time")
plt.legend()
plt.grid(True, alpha=0.3)
plt.tight_layout()
plt.show()
print(f"\nFinal positions:")
print(f" Batch GD: x = {history_batch[-1]:.4f}")
print(f" SGD: x = {history_sgd[-1]:.4f}")
print(f" Mini-Batch GD: x = {history_mini[-1]:.4f}")
print(f" True minimum: x = 0.0000")Visual Comparison of the Three Variants
Let's visualize how each variant behaves on the same simple function .
3. Convexity and The Hessian
What is Convexity?
A function is convex if it is shaped like a bowl (∪) — any line segment connecting two points on the function lies above or on the function itself.
Formal Definition
A function is convex if for any two points and any :
Intuition: If you pick any two points on the curve and draw a straight line between them, that line will never go below the curve.
Why Convexity Matters in Optimization
✅ Convex Functions (Good News!)
- Have exactly one global minimum (no local minima)
- Gradient descent is guaranteed to find the optimal solution
- Examples: Linear regression loss (MSE), logistic regression loss
❌ Non-Convex Functions (Challenges)
- Can have multiple local minima
- Gradient descent might get stuck in a bad local minimum
- Examples: Neural network loss functions, most real-world problems
Testing for Convexity: The Hessian Matrix
For a function , the Hessian is the matrix of second-order partial derivatives:
Physical Meaning: The Hessian describes the curvature of the function in all directions.
Convexity Test
A twice-differentiable function is convex if and only if its Hessian is Positive Semi-Definite (PSD) everywhere:
What does "Positive Semi-Definite" mean?
A matrix is PSD if:
- All eigenvalues , OR
- For all vectors :
Intuition: The function curves upward (or stays flat) in all directions — like a bowl.
Classification by Hessian
| Condition | Meaning | Shape | Example Point |
|---|---|---|---|
| (all eigenvalues > 0) | Strictly convex | Upward in all directions | Local minimum |
| (all eigenvalues ≥ 0) | Convex | Upward or flat | Minimum or flat region |
| (all eigenvalues ≤ 0) | Concave | Downward or flat | Local maximum |
| Mixed signs | Indefinite | Saddle point | Neither min nor max |
Example: Manual Calculation
For :
-
First derivatives (gradient):
-
Second derivatives (Hessian):
-
Eigenvalues: (both positive!)
-
Conclusion: The function is strictly convex → has a unique global minimum at .
# Testing Convexity with Eigenvalues
print("=" * 60)
print("CONVEXITY TESTING: Checking if functions are convex")
print("=" * 60)
# Example 1: f(x, y) = x^2 + 2y^2 (should be convex)
print("\nExample 1: f(x, y) = x² + 2y²")
print("-" * 40)
H1 = np.array(
[[2.0, 0.0], [0.0, 4.0]] # ∂²f/∂x² = 2, ∂²f/∂x∂y = 0 # ∂²f/∂y∂x = 0, ∂²f/∂y² = 4
)
print("Hessian matrix:")
print(H1)
eigvals1 = np.linalg.eigvals(H1)
print(f"\nEigenvalues: {eigvals1}")
if np.all(eigvals1 > 0):
print("✓ All eigenvalues > 0 → STRICTLY CONVEX")
print(" → Has unique global minimum")
print(" → Gradient descent will find it!")
elif np.all(eigvals1 >= 0):
print("✓ All eigenvalues ≥ 0 → CONVEX")
else:
print("✗ Mixed eigenvalues → NON-CONVEX (danger!)")
# Example 2: f(x, y) = x^2 - y^2 (saddle point - not convex)
print("\n" + "=" * 60)
print("Example 2: f(x, y) = x² - y² (saddle point)")
print("-" * 40)
H2 = np.array(
[[2.0, 0.0], [0.0, -2.0]] # ∂²f/∂x² = 2, ∂²f/∂x∂y = 0 # ∂²f/∂y∂x = 0, ∂²f/∂y² = -2
)
print("Hessian matrix:")
print(H2)
eigvals2 = np.linalg.eigvals(H2)
print(f"\nEigenvalues: {eigvals2}")
if np.all(eigvals2 > 0):
print("✓ STRICTLY CONVEX")
elif np.all(eigvals2 >= 0):
print("✓ CONVEX")
elif np.all(eigvals2 < 0):
print("✓ CONCAVE (local maximum)")
else:
print("✗ INDEFINITE (saddle point)")
print(" → Gradient descent can get confused here!")
print(" → This point is neither minimum nor maximum")
# Example 3: A more complex case
print("\n" + "=" * 60)
print("Example 3: Custom matrix")
print("-" * 40)
H3 = np.array([[3.0, 1.0], [1.0, 2.0]])
print("Hessian matrix:")
print(H3)
eigvals3 = np.linalg.eigvals(H3)
print(f"\nEigenvalues: {eigvals3}")
if np.all(eigvals3 > 0):
print("✓ All eigenvalues > 0 → STRICTLY CONVEX")
print(" → Safe for gradient descent!")
elif np.all(eigvals3 >= 0):
print("✓ All eigenvalues ≥ 0 → CONVEX")
else:
print("✗ Mixed signs → NON-CONVEX")
# Practical interpretation
print("\n" + "=" * 60)
print("PRACTICAL INTERPRETATION FOR EXAMS:")
print("=" * 60)
print(
"""
When analyzing a function:
1. Calculate the Hessian matrix (second derivatives)
2. Find eigenvalues
3. Check signs:
- All positive (λ > 0) → Convex, safe, unique minimum
- All negative (λ < 0) → Concave, local maximum
- Mixed signs → Saddle point, careful!
Remember: Convex = Good for optimization!
"""
)4. Constrained Optimization
The Problem
Sometimes, we can't just minimize freely — parameters must satisfy constraints.
Example scenarios:
- Probabilities must be in
- Weights must sum to 1 (portfolio optimization)
- Parameters must be non-negative
- Budget constraints in resource allocation
Formal Setup: where is the constraint set (feasible region).
Projected Gradient Descent
Since regular gradient descent might step outside the constraint set , we use Projected Gradient Descent (PGD):
Algorithm
-
Take a normal gradient descent step:
-
Project the result back into the constraint set:
where finds the closest point in to .
Common Projection Operations
1. Box Constraints:
Clip each coordinate:
Example: Keep weights between -1 and 1
2. Non-negativity:
3. Simplex: (probability distributions)
More complex, involves sorting (see specialized algorithms)
4. L2 Ball: (bounded norm)
Why This Works
Intuition: If gradient descent tries to escape the feasible region, we "snap it back" to the nearest valid point. This ensures:
- Parameters always satisfy constraints
- We still make progress toward the minimum
- Convergence guarantees still hold (for convex problems)
Example: Paper Calculation
Suppose after a gradient step, but we need .
Projection:
Result:
# Projected Gradient Descent Example
print("=" * 60)
print("PROJECTED GRADIENT DESCENT")
print("=" * 60)
# Example 1: Box Constraints [-1, 1]
print("\nExample 1: Box Constraints x ∈ [-1, 1]")
print("-" * 40)
# Suppose gradient descent calculated these new weights
x_unconstrained = np.array([1.5, -2.3, 0.7, 2.8, -0.5])
print(f"After gradient step (unconstrained): {x_unconstrained}")
# Project back to [-1, 1]
x_projected = np.clip(x_unconstrained, -1, 1)
print(f"After projection to [-1, 1]: {x_projected}")
# Show what happened to each element
print("\nElement-by-element:")
for i, (original, projected) in enumerate(zip(x_unconstrained, x_projected)):
if original < -1:
print(f" x[{i}]: {original:.2f} → {projected:.2f} (clipped to lower bound)")
elif original > 1:
print(f" x[{i}]: {original:.2f} → {projected:.2f} (clipped to upper bound)")
else:
print(f" x[{i}]: {original:.2f} → {projected:.2f} (unchanged)")
# Example 2: Non-negativity Constraint
print("\n" + "=" * 60)
print("Example 2: Non-Negativity Constraint x ≥ 0")
print("-" * 40)
x_unconstrained2 = np.array([2.5, -1.3, 0.0, -0.8, 3.2])
print(f"After gradient step (unconstrained): {x_unconstrained2}")
x_projected2 = np.maximum(0, x_unconstrained2) # equivalent to np.clip(x, 0, np.inf)
print(f"After projection to x ≥ 0: {x_projected2}")
print("\nElement-by-element:")
for i, (original, projected) in enumerate(zip(x_unconstrained2, x_projected2)):
if original < 0:
print(f" x[{i}]: {original:.2f} → {projected:.2f} (clipped to 0)")
else:
print(f" x[{i}]: {original:.2f} → {projected:.2f} (unchanged)")
# Example 3: L2 Ball Constraint ||x|| ≤ r
print("\n" + "=" * 60)
print("Example 3: L2 Ball Constraint ||x||₂ ≤ r")
print("-" * 40)
x_unconstrained3 = np.array([3.0, 4.0]) # This has norm = 5
r = 2.0 # Maximum allowed radius
norm = np.linalg.norm(x_unconstrained3)
print(f"Unconstrained point: {x_unconstrained3}")
print(f"Norm: ||x||₂ = {norm:.2f}")
print(f"Constraint: ||x||₂ ≤ {r}")
if norm <= r:
x_projected3 = x_unconstrained3
print(f"Point is inside ball → No projection needed")
else:
# Scale down to boundary of ball
x_projected3 = r * x_unconstrained3 / norm
print(f"Point is outside ball → Scale down")
print(f"Projected point: {x_projected3}")
print(f"New norm: ||x_new||₂ = {np.linalg.norm(x_projected3):.2f}")
# Visualization of projection
print("\n" + "=" * 60)
print("VISUAL INTERPRETATION:")
print("=" * 60)
print(
"""
Projection is like a "safety net":
Before projection: x might be anywhere
↓
[Gradient Descent Step]
↓
After projection: x is forced back into valid region
Think of it as:
- Taking a step (gradient descent)
- Checking if you went out of bounds
- If yes, snap back to nearest valid point
- If no, keep the new position
"""
)5. Summary & Exam Tips
Key Formulas to Remember
Gradient Descent Update
Gradient Variants
- Batch:
- SGD: (one sample)
- Mini-batch:
Convexity Test
- Calculate Hessian matrix (second derivatives)
- Find eigenvalues
- If all → Convex (safe!)
Projected Gradient Descent
Exam Strategy
For Multiple Choice / Interpretation Questions:
- Identify the variant: How many samples? → Batch/SGD/Mini-batch
- Check convexity: Positive eigenvalues? → Unique minimum
- Learning rate: Too large → diverge, too small → slow
- Constraints: Are parameters bounded? → Need projection
For Manual Calculations:
-
Gradient calculation:
- Take partial derivatives
- Evaluate at given point
- Don't forget the negative sign in update!
-
Hessian analysis:
- Compute all second derivatives
- Form the matrix
- Calculate eigenvalues (or check determinant for 2×2)
-
Projection:
- Apply gradient step first
- Then clip/project each coordinate
- Check if result satisfies constraints
Common Pitfalls to Avoid
❌ Mistake: Forgetting the minus sign in
✅ Correct: We go in the opposite direction of the gradient
❌ Mistake: Thinking SGD converges to exact minimum
✅ Correct: SGD oscillates around minimum due to noise
❌ Mistake: Assuming all ML problems are convex
✅ Correct: Neural networks are non-convex (local minima exist)
❌ Mistake: Projecting before the gradient step
✅ Correct: Gradient step THEN projection
Quick Reference Table
| Concept | Key Question | Answer |
|---|---|---|
| Gradient | Which direction to move? | Opposite of |
| Learning rate | How far to move? | (tune carefully!) |
| Batch GD | When to use? | Small datasets, need stability |
| SGD | When to use? | Huge datasets, online learning |
| Mini-batch | When to use? | Default choice |
| Convexity | How to check? | Hessian eigenvalues ≥ 0 |
| Constraints | How to handle? | Projected GD |