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