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 J(w)J(w). 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 (f′(x)f'(x)): Measures the slope (rate of change) of a function at a point.
  • Interpretation:
    • If f′(x)>0f'(x) > 0 → function is increasing → move left (decrease xx) to minimize
    • If f′(x)<0f'(x) < 0 → function is decreasing → move right (increase xx) to minimize
    • If f′(x)=0f'(x) = 0 → potential minimum (or maximum, or saddle point)

Example: For f(x)=x2f(x) = x^2, the derivative is f′(x)=2xf'(x) = 2x

Multiple Variables: Gradient

  • Gradient (∇f(x)\nabla f(x)): A vector of partial derivatives for functions with multiple variables.

  • Formula: ∇f(x)=[∂f∂x1∂f∂x2⋮∂f∂xd]\nabla f(x) = \begin{bmatrix} \frac{\partial f}{\partial x_1} \\ \frac{\partial f}{\partial x_2} \\ \vdots \\ \frac{\partial f}{\partial x_d} \end{bmatrix}

  • 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:

wnew=wold−η∇J(w)w_{new} = w_{old} - \eta \nabla J(w)

where:

  • η\eta (eta) = Learning Rate (step size, typically 0.001 to 0.1)
  • ∇J(w)\nabla J(w) = gradient of the loss function
  • The minus sign = move downhill
In [ ]
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 (nn samples) to compute the gradient at each iteration.

Gradient Formula

gk=1n∑i=1n∇l(fw(xi),yi)g_k = \frac{1}{n} \sum_{i=1}^{n} \nabla l(f_w(x_i), y_i)

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

gk=∇l(fw(xik),yik)g_k = \nabla l(f_w(x_{i_k}), y_{i_k}) where iki_k is a randomly chosen index at iteration kk.

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 mm samples (typically 16, 32, 64, or 128).

Gradient Formula

gk=1m∑i∈Bk∇l(fw(xi),yi)g_k = \frac{1}{m} \sum_{i \in B_k} \nabla l(f_w(x_i), y_i) where BkB_k is a random batch of size mm at iteration kk.

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 (nn) Slow High None Small datasets
SGD 1 Fast Low High Huge datasets, online
Mini-Batch mm (e.g., 32) Medium Medium Low Most ML problems

Learning Rate (η\eta)

  • 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)
In [ ]
# ===================================
# 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")
In [ ]
# ===================================
# 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")
In [ ]
# ===================================
# 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")
In [ ]
# 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 f(x)=x2f(x) = x^2.

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 ff is convex if for any two points x,yx, y and any λ∈[0,1]\lambda \in [0,1]: f(λx+(1−λ)y)≤λf(x)+(1−λ)f(y)f(\lambda x + (1-\lambda) y) \leq \lambda f(x) + (1-\lambda) f(y)

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 f:Rd→Rf: \mathbb{R}^d \to \mathbb{R}, the Hessian is the matrix of second-order partial derivatives:

Hf(x)=[∂2f∂x12∂2f∂x1∂x2⋯∂2f∂x1∂xd∂2f∂x2∂x1∂2f∂x22⋯∂2f∂x2∂xd⋮⋮⋱⋮∂2f∂xd∂x1∂2f∂xd∂x2⋯∂2f∂xd2]H_f(x) = \begin{bmatrix} \frac{\partial^2 f}{\partial x_1^2} & \frac{\partial^2 f}{\partial x_1 \partial x_2} & \cdots & \frac{\partial^2 f}{\partial x_1 \partial x_d} \\ \frac{\partial^2 f}{\partial x_2 \partial x_1} & \frac{\partial^2 f}{\partial x_2^2} & \cdots & \frac{\partial^2 f}{\partial x_2 \partial x_d} \\ \vdots & \vdots & \ddots & \vdots \\ \frac{\partial^2 f}{\partial x_d \partial x_1} & \frac{\partial^2 f}{\partial x_d \partial x_2} & \cdots & \frac{\partial^2 f}{\partial x_d^2} \end{bmatrix}

Physical Meaning: The Hessian describes the curvature of the function in all directions.


Convexity Test

A twice-differentiable function ff is convex if and only if its Hessian is Positive Semi-Definite (PSD) everywhere:

Hf(x)⪰0∀xH_f(x) \succeq 0 \quad \forall x

What does "Positive Semi-Definite" mean?

A matrix HH is PSD if:

  1. All eigenvalues λi≥0\lambda_i \geq 0, OR
  2. For all vectors vv: vTHv≥0v^T H v \geq 0

Intuition: The function curves upward (or stays flat) in all directions — like a bowl.


Classification by Hessian

Condition Meaning Shape Example Point
H≻0H \succ 0 (all eigenvalues > 0) Strictly convex Upward in all directions Local minimum
H⪰0H \succeq 0 (all eigenvalues ≥ 0) Convex Upward or flat Minimum or flat region
H⪯0H \preceq 0 (all eigenvalues ≤ 0) Concave Downward or flat Local maximum
Mixed signs Indefinite Saddle point Neither min nor max

Example: Manual Calculation

For f(x,y)=x2+2y2f(x, y) = x^2 + 2y^2:

  1. First derivatives (gradient):

    • ∂f∂x=2x\frac{\partial f}{\partial x} = 2x
    • ∂f∂y=4y\frac{\partial f}{\partial y} = 4y
  2. Second derivatives (Hessian):

    H=[∂2f∂x2∂2f∂x∂y∂2f∂y∂x∂2f∂y2]=[2004]H = \begin{bmatrix} \frac{\partial^2 f}{\partial x^2} & \frac{\partial^2 f}{\partial x \partial y} \\ \frac{\partial^2 f}{\partial y \partial x} & \frac{\partial^2 f}{\partial y^2} \end{bmatrix} = \begin{bmatrix} 2 & 0 \\ 0 & 4 \end{bmatrix}
  3. Eigenvalues: λ1=2,λ2=4\lambda_1 = 2, \lambda_2 = 4 (both positive!)

  4. Conclusion: The function is strictly convex → has a unique global minimum at (0,0)(0, 0).

In [ ]
# 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 [0,1][0, 1]
  • Weights must sum to 1 (portfolio optimization)
  • Parameters must be non-negative
  • Budget constraints in resource allocation

Formal Setup: min⁡x∈Cf(x)\min_{x \in C} f(x) where CC is the constraint set (feasible region).


Projected Gradient Descent

Since regular gradient descent might step outside the constraint set CC, we use Projected Gradient Descent (PGD):

Algorithm

  1. Take a normal gradient descent step: xtemp=x−η∇f(x)x_{temp} = x - \eta \nabla f(x)

  2. Project the result back into the constraint set: xnew=projC(xtemp)x_{new} = \text{proj}_C(x_{temp})

where projC(z)\text{proj}_C(z) finds the closest point in CC to zz.


Common Projection Operations

1. Box Constraints: x∈[a,b]x \in [a, b]

Clip each coordinate: proj[a,b](z)=max⁡(a,min⁡(b,z))\text{proj}_{[a,b]}(z) = \max(a, \min(b, z))

Example: Keep weights between -1 and 1

xi={−1if xi<−1xiif −1≤xi≤11if xi>1x_i = \begin{cases} -1 & \text{if } x_i < -1 \\ x_i & \text{if } -1 \leq x_i \leq 1 \\ 1 & \text{if } x_i > 1 \end{cases}

2. Non-negativity: x≥0x \geq 0

projR+(z)=max⁡(0,z)\text{proj}_{\mathbb{R}_+}(z) = \max(0, z)

3. Simplex: ∑xi=1,xi≥0\sum x_i = 1, x_i \geq 0 (probability distributions)

More complex, involves sorting (see specialized algorithms)

4. L2 Ball: ∥x∥2≤r\|x\|_2 \leq r (bounded norm)

proj∥x∥≤r(z)={zif ∥z∥≤rr⋅z∥z∥if ∥z∥>r\text{proj}_{\|x\| \leq r}(z) = \begin{cases} z & \text{if } \|z\| \leq r \\ r \cdot \frac{z}{\|z\|} & \text{if } \|z\| > r \end{cases}

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 x=[2.5,−3.0,0.8]x = [2.5, -3.0, 0.8] after a gradient step, but we need x∈[−1,1]3x \in [-1, 1]^3.

Projection:

  • x1=2.5→clip(2.5,−1,1)=1.0x_1 = 2.5 \to \text{clip}(2.5, -1, 1) = 1.0
  • x2=−3.0→clip(−3.0,−1,1)=−1.0x_2 = -3.0 \to \text{clip}(-3.0, -1, 1) = -1.0
  • x3=0.8→clip(0.8,−1,1)=0.8x_3 = 0.8 \to \text{clip}(0.8, -1, 1) = 0.8

Result: xnew=[1.0,−1.0,0.8]x_{new} = [1.0, -1.0, 0.8]

In [ ]
# 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

wnew=wold−η∇J(w)w_{new} = w_{old} - \eta \nabla J(w)

Gradient Variants

  • Batch: g=1n∑i=1n∇lig = \frac{1}{n} \sum_{i=1}^{n} \nabla l_i
  • SGD: g=∇lig = \nabla l_i (one sample)
  • Mini-batch: g=1m∑i∈batch∇lig = \frac{1}{m} \sum_{i \in \text{batch}} \nabla l_i

Convexity Test

  • Calculate Hessian matrix HH (second derivatives)
  • Find eigenvalues λi\lambda_i
  • If all λi≥0\lambda_i \geq 0 → Convex (safe!)

Projected Gradient Descent

  1. xtemp=x−η∇f(x)x_{temp} = x - \eta \nabla f(x)
  2. xnew=projC(xtemp)x_{new} = \text{proj}_C(x_{temp})

Exam Strategy

For Multiple Choice / Interpretation Questions:

  1. Identify the variant: How many samples? → Batch/SGD/Mini-batch
  2. Check convexity: Positive eigenvalues? → Unique minimum
  3. Learning rate: Too large → diverge, too small → slow
  4. Constraints: Are parameters bounded? → Need projection

For Manual Calculations:

  1. Gradient calculation:

    • Take partial derivatives
    • Evaluate at given point
    • Don't forget the negative sign in update!
  2. Hessian analysis:

    • Compute all second derivatives
    • Form the matrix
    • Calculate eigenvalues (or check determinant for 2×2)
  3. 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 w−η∇Jw - \eta \nabla J
✅ 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 ∇f\nabla f
Learning rate How far to move? η\eta (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