7a:Tc7e,import numpy as np from typing import Callable, Tuple, List def batch_gradient_descent( X: np.ndarray, # Training features (N x d) y: np.ndarray, # Training targets (N,) theta_init: np.ndarray, # Initial parameters (d,) loss_fn: Callable, # Loss function L(predictions, targets) grad_fn: Callable, # Gradient function ∇L w.r.t. theta learning_rate: float = 0.01, max_iterations: int = 1000, tolerance: float = 1e-6, verbose: bool = True ) -> Tuple[np.ndarray, List[float]]: """ Full-batch gradient descent optimizer. Returns: theta: Optimized parameters loss_history: Loss value at each iteration """ theta = theta_init.copy() N = X.shape[0] loss_history = [] for t in range(max_iterations): # Step 1: Compute predictions for ALL examples predictions = X @ theta # Assuming linear model for simplicity # Step 2: Compute loss over ENTIRE dataset current_loss = np.mean(loss_fn(predictions, y)) loss_history.append(current_loss) # Step 3: Compute gradient over ENTIRE dataset # The gradient is averaged over all N examples gradient = grad_fn(X, y, theta, predictions) # Shape: (d,) # Step 4: Check stopping criterion gradient_norm = np.linalg.norm(gradient) if gradient_norm < tolerance: if verbose: print(f"Converged at iteration {t} (gradient norm: {gradient_norm:.2e})") break # Step 5: Update parameters theta = theta - learning_rate * gradient if verbose and t % 100 == 0: print(f"Iteration {t}: Loss = {current_loss:.6f}, ||∇J|| = {gradient_norm:.6f}") return theta, loss_history # Example: Linear regression with MSE loss def mse_loss(predictions: np.ndarray, targets: np.ndarray) -> np.ndarray: """Mean squared error loss (per example).""" return 0.5 * (predictions - targets) ** 2 def mse_gradient(X: np.ndarray, y: np.ndarray, theta: np.ndarray, predictions: np.ndarray) -> np.ndarray: """Gradient of MSE loss w.r.t. theta, averaged over all examples.""" N = X.shape[0] residuals = predictions - y # (N,) # ∇J = (1/N) * X^T * (X*theta - y) gradient = (1/N) * X.T @ residuals return gradient # Usage example if __name__ == "__main__": # Generate synthetic data np.random.seed(42) N, d = 1000, 5 X_true = np.random.randn(N, d) theta_true = np.array([1.0, -2.0, 0.5, 3.0, -1.5]) y_true = X_true @ theta_true + 0.1 * np.random.randn(N) # Initialize parameters randomly theta_init = np.random.randn(d) # Run batch gradient descent theta_opt, history = batch_gradient_descent( X_true, y_true, theta_init, loss_fn=mse_loss, grad_fn=mse_gradient, learning_rate=0.1, max_iterations=500 ) print(f" True theta: {theta_true}") print(f"Learned theta: {theta_opt}") print(f"Parameter error: {np.linalg.norm(theta_opt - theta_true):.6f}")7b:T4b8,Understanding when and how fast gradient descent converges is crucial for both theoretical guarantees and practical hyperparameter tuning. The convergence properties depend critically on the **properties of the objective function**. **Key Definitions** Before stating convergence results, we need several important definitions: **Lipschitz Continuity of the Gradient**: The gradient $ abla J$ is $L$-Lipschitz if: $$\| abla J(\boldsymbol{\theta}) - abla J(\boldsymbol{\phi})\| \leq L \|\boldsymbol{\theta} - \boldsymbol{\phi}\|$$ for all $\boldsymbol{\theta}, \boldsymbol{\phi}$. The constant $L$ is called the **smoothness parameter**. **Strong Convexity**: The function $J$ is $\mu$-strongly convex if: $$J(\boldsymbol{\phi}) \geq J(\boldsymbol{\theta}) + abla J(\boldsymbol{\theta})^\top(\boldsymbol{\phi} - \boldsymbol{\theta}) + \frac{\mu}{2}\|\boldsymbol{\phi} - \boldsymbol{\theta}\|^2$$ Strong convexity ensures a unique global minimum and prevents 'flat' regions. **Condition Number**: For a strongly convex function with $L$-Lipschitz gradient, the condition number is: $$\kappa = \frac{L}{\mu}$$ This ratio fundamentally governs convergence speed—higher $\kappa$ means slower convergence.7c:T46d,While batch gradient descent has strong theoretical properties, it suffers from several practical limitations that severely restrict its usefulness in modern machine learning. **Limitation 1: Computational Expense** As analyzed above, the $O(N \cdot d)$ cost per iteration becomes prohibitive for large datasets. But it's worse than just slow—the cost is *unavoidable* for each update. Even if the first 100 examples would give you a 'good enough' gradient direction, you still must process all $N$ examples before making any progress. **Limitation 2: Memory Requirements** Batch gradient descent requires either: - Loading entire dataset into memory (often impossible for large datasets) - Making $N$ disk reads per iteration (extremely slow) Modern datasets can be terabytes in size. Holding them in RAM is simply not feasible. **Limitation 3: No Implicit Regularization** Stochastic methods benefit from noise in the gradient estimates, which acts as a form of regularization. Batch gradient descent, with its exact gradients, lacks this beneficial noise. This often leads to finding sharper minima that generalize worse.7d:T44f,Despite its limitations, batch gradient descent remains the right choice in certain scenarios. Understanding these use cases helps you make informed optimizer choices. **Appropriate Use Cases** 1. **Very small datasets** ($N < 1000$): When the entire dataset fits easily in memory and gradient computation is fast, the simplicity and stability of batch GD is advantageous. 2. **Convex optimization problems**: For convex losses (logistic regression, linear regression, SVMs), batch GD provides reliable convergence with well-understood behavior. 3. **When exact gradients are required**: Some scenarios require precise gradients, such as second-order optimization methods that depend on accurate Hessian-vector products. 4. **Debugging and prototyping**: When developing new models, batch GD's deterministic behavior makes debugging easier. You can reproduce exact training trajectories. 5. **Fine-tuning with stability requirements**: When stability matters more than speed (e.g., fine-tuning a nearly-converged model), exact gradients prevent the noise-induced oscillation of stochastic methods.72:{"json":{"id":"seed_d8584590bd1547ec7c4274184c31dea7","slug":"gradient-descent-variants","category":"Machine Learning","topic":"Backpropagation & Optimization","title":"Gradient Descent Variants","description":"Master the full spectrum of gradient descent algorithms from classical batch methods to modern stochastic approaches. Understand the mathematical foundations, convergence guarantees, and practical tradeoffs that determine which optimizer to use in different scenarios.","difficulty":"INTERMEDIATE","estimatedMinutes":90,"pages":[{"id":"seed_31f04c4f020d5d11bfbd167825753708","title":"Batch Gradient Descent","order":0,"content":[{"id":"opening-hook","title":"The Foundational Algorithm","content":[{"data":{"content":"At the heart of virtually every machine learning algorithm lies a deceptively simple idea: **find the parameters that minimize a loss function by iteratively moving in the direction of steepest descent**. This is gradient descent—the workhorse algorithm that powers everything from logistic regression to transformers with billions of parameters.\n\nBatch gradient descent, also known as **full-batch gradient descent** or simply **vanilla gradient descent**, represents the purest form of this optimization paradigm. Before we can appreciate the sophistication of modern optimizers like Adam or understand why stochastic methods work, we must first master this foundational algorithm in its complete, unmodified form.\n\nThis page provides an exhaustive treatment of batch gradient descent: its mathematical foundations, geometric intuitions, convergence guarantees, implementation considerations, and the fundamental limitations that motivated all subsequent innovations in optimization."},"type":"text"},{"data":{"icon":"Target","title":"What You Will Learn","content":"By the end of this page, you will understand the precise mathematical formulation of batch gradient descent, visualize its behavior in different loss landscapes, derive its convergence conditions, implement it correctly from first principles, and identify when it is (and isn't) the right choice for optimization.","variant":"info"},"type":"callout"}]},{"id":"mathematical-formulation","title":"Mathematical Formulation","content":[{"data":{"content":"To understand batch gradient descent rigorously, we must first establish the precise mathematical setting. Consider a supervised learning problem where we have a dataset of **N** training examples:\n\n$$\\mathcal{D} = \\{(\\mathbf{x}^{(1)}, y^{(1)}), (\\mathbf{x}^{(2)}, y^{(2)}), \\ldots, (\\mathbf{x}^{(N)}, y^{(N)})\\}$$\n\nOur goal is to find parameters $\\boldsymbol{\\theta} \\in \\mathbb{R}^d$ that minimize the **empirical risk**—the average loss over all training examples:\n\n$$J(\\boldsymbol{\\theta}) = \\frac{1}{N} \\sum_{i=1}^{N} \\mathcal{L}(f_{\\boldsymbol{\\theta}}(\\mathbf{x}^{(i)}), y^{(i)})$$\n\nHere, $f_{\\boldsymbol{\\theta}}$ is our model parameterized by $\\boldsymbol{\\theta}$, and $\\mathcal{L}$ is a loss function measuring the discrepancy between predictions and targets."},"type":"text"},{"data":{"icon":"Info","title":"Notation Convention","content":"We use $J(\\boldsymbol{\\theta})$ to denote the objective function (total cost across all examples) and $\\mathcal{L}$ for the per-example loss. The gradient $\nabla_{\\boldsymbol{\\theta}} J$ is a vector in $\\mathbb{R}^d$ pointing in the direction of steepest increase of $J$.","variant":"note"},"type":"callout"},{"data":{"content":"**The Gradient Descent Update Rule**\n\nBatch gradient descent updates parameters by moving in the opposite direction of the gradient:\n\n$$\\boldsymbol{\\theta}^{(t+1)} = \\boldsymbol{\\theta}^{(t)} - \\eta \nabla_{\\boldsymbol{\\theta}} J(\\boldsymbol{\\theta}^{(t)})$$\n\nwhere:\n- $\\boldsymbol{\\theta}^{(t)}$ denotes the parameters at iteration $t$\n- $\\eta > 0$ is the **learning rate** (also called step size)\n- $\nabla_{\\boldsymbol{\\theta}} J(\\boldsymbol{\\theta}^{(t)})$ is the gradient computed over **the entire dataset**\n\nExpanding the gradient explicitly:\n\n$$\nabla_{\\boldsymbol{\\theta}} J(\\boldsymbol{\\theta}) = \\frac{1}{N} \\sum_{i=1}^{N} \nabla_{\\boldsymbol{\\theta}} \\mathcal{L}(f_{\\boldsymbol{\\theta}}(\\mathbf{x}^{(i)}), y^{(i)})$$\n\nThis is the **defining characteristic** of batch gradient descent: at each iteration, we compute gradients with respect to every single training example and average them before making a parameter update."},"type":"text"},{"data":{"rows":[["$$\\boldsymbol{\\theta}$","Parameters","The values we're optimizing","Depends on model architecture"],["$$\\eta$","Learning rate","Controls step size","$$10^{-5}$ to $10^{-1}$"],["$$\nabla J$","Gradient","Direction of steepest ascent","Computed, not chosen"],["$$t$","Iteration","Current optimization step","$$0, 1, 2, \\ldots$"]],"caption":"Key Components of the Gradient Descent Update","headers":["Symbol","Name","Role","Typical Range"]},"type":"table"}],"titleType":"number","titleNumber":1},{"id":"geometric-interpretation","title":"Geometric Interpretation","content":[{"data":{"content":"Understanding gradient descent geometrically provides crucial intuition for debugging optimization problems and selecting hyperparameters. Let's build this understanding from first principles.\n\n**The Loss Surface**\n\nThe objective function $J(\\boldsymbol{\\theta})$ defines a **loss surface** (or loss landscape) over the parameter space. For a model with $d$ parameters, this is a surface in $(d+1)$-dimensional space—$d$ dimensions for parameters and one for the loss value.\n\n- **Valleys** represent regions of low loss (good parameters)\n- **Peaks and ridges** represent regions of high loss (bad parameters)\n- **Saddle points** are flat regions that are neither minima nor maxima\n\nThe gradient $\nabla J(\\boldsymbol{\\theta})$ at any point is a vector that:\n1. **Points in the direction of steepest ascent** on the loss surface\n2. Has **magnitude equal to the rate of steepest ascent**\n\nBy moving in the negative gradient direction, we descend the loss surface toward lower values."},"type":"text"},{"data":{"icon":"Lightbulb","title":"The Mountain Analogy","content":"Imagine standing on a foggy mountain and trying to reach the lowest valley. The gradient tells you the direction of steepest uphill slope. By always walking opposite to this direction (downhill), you'll eventually reach a valley floor. The learning rate determines how large each step is—too large and you might overshoot the valley; too small and the journey takes forever.","variant":"tip"},"type":"callout"},{"data":{"content":"**Why Negative Gradient Works**\n\nConsider the first-order Taylor expansion of $J$ around the current point $\\boldsymbol{\\theta}^{(t)}$:\n\n$$J(\\boldsymbol{\\theta}^{(t)} + \\boldsymbol{\\delta}) \\approx J(\\boldsymbol{\\theta}^{(t)}) + \nabla J(\\boldsymbol{\\theta}^{(t)})^\\top \\boldsymbol{\\delta}$$\n\nTo minimize $J$, we want to choose $\\boldsymbol{\\delta}$ such that $J(\\boldsymbol{\\theta}^{(t)} + \\boldsymbol{\\delta}) < J(\\boldsymbol{\\theta}^{(t)})$. This requires:\n\n$$\nabla J(\\boldsymbol{\\theta}^{(t)})^\\top \\boldsymbol{\\delta} < 0$$\n\nThe most negative this inner product can be (for a fixed $\\|\\boldsymbol{\\delta}\\|$) is achieved when $\\boldsymbol{\\delta}$ points exactly opposite to the gradient:\n\n$$\\boldsymbol{\\delta} = -\\eta \nabla J(\\boldsymbol{\\theta}^{(t)})$$\n\nThis is precisely the gradient descent update! The negative gradient is the direction of **steepest local descent**."},"type":"text"},{"data":{"content":"**Visualizing Different Landscapes**\n\nThe behavior of gradient descent varies dramatically depending on the loss landscape:\n\n1. **Convex quadratic**: The ideal case. Contours are ellipsoids, and gradient descent moves directly toward the minimum (if the Hessian is isotropic) or follows a zig-zag path if contours are elongated.\n\n2. **Convex non-quadratic**: Guaranteed to converge to the global minimum, but the path may be more complex.\n\n3. **Non-convex**: The typical case in deep learning. Multiple local minima, saddle points, and flat regions make optimization challenging.\n\n4. **Ravines and narrow valleys**: Causes oscillation across the valley walls while slow progress along the valley floor—a major motivation for momentum methods.\n\n5. **Plateau regions**: Gradient nearly vanishes, causing extremely slow progress despite being far from any minimum."},"type":"text"}],"titleType":"number","titleNumber":2},{"id":"algorithm-implementation","title":"Algorithm and Implementation","content":[{"data":{"content":"Let's formalize the batch gradient descent algorithm and examine a rigorous implementation. Understanding the precise algorithmic steps is essential before we can appreciate the modifications introduced by more sophisticated optimizers.\n\n**Algorithm: Batch Gradient Descent**\n\n```\nInput: Initial parameters θ₀, learning rate η, dataset D, max iterations T, tolerance ε\nOutput: Optimized parameters θ*\n\n1. t ← 0\n2. while t < T and ||∇J(θᵗ)|| > ε:\n a. Compute gradient: g ← (1/N) Σᵢ ∇L(f_θᵗ(xⁱ), yⁱ) // Over ALL N examples\n b. Update parameters: θᵗ⁺¹ ← θᵗ - η·g\n c. t ← t + 1\n3. return θᵗ\n```\n\nNotice that step 2a requires a **full pass through the entire dataset** for each parameter update. This is the computational signature of batch gradient descent."},"type":"text"},{"data":{"fileName":"batch_gradient_descent.py","languages":[{"code":"$7a","label":"Python","value":"python"}],"showLineNumbers":true},"type":"code"},{"data":{"icon":"AlertCircle","title":"Critical Implementation Detail","content":"The gradient MUST be computed over the entire dataset before making a single parameter update. A common mistake is to update parameters after each example—that's stochastic gradient descent, not batch gradient descent. In batch GD, one 'epoch' equals one parameter update.","variant":"warning"},"type":"callout"}],"titleType":"number","titleNumber":3},{"id":"convergence-analysis","title":"Convergence Analysis","content":[{"data":{"content":"$7b"},"type":"text"},{"data":{"icon":"Info","title":"The Condition Number Intuition","content":"The condition number κ measures how 'elongated' the contours of the loss function are. For a quadratic loss, κ = λ_max/λ_min where λ are eigenvalues of the Hessian. High κ means the loss decreases rapidly in some directions but slowly in others, causing oscillation and slow progress.","variant":"note"},"type":"callout"},{"data":{"content":"**Convergence Theorems**\n\n**Theorem 1 (Convergence for Smooth Functions)**\n\nIf $J$ has $L$-Lipschitz continuous gradient and $\\eta \\leq \\frac{1}{L}$, then batch gradient descent satisfies:\n\n$$J(\\boldsymbol{\\theta}^{(T)}) - J(\\boldsymbol{\\theta}^*) \\leq \\frac{\\|\\boldsymbol{\\theta}^{(0)} - \\boldsymbol{\\theta}^*\\|^2}{2\\eta T}$$\n\nThis is a **sublinear convergence rate** of $O(1/T)$—to reduce the error by a factor of 10, we need 10× more iterations.\n\n**Theorem 2 (Convergence for Strongly Convex Functions)**\n\nIf $J$ is $\\mu$-strongly convex with $L$-Lipschitz gradient and $\\eta = \\frac{1}{L}$, then:\n\n$$\\|\\boldsymbol{\\theta}^{(T)} - \\boldsymbol{\\theta}^*\\|^2 \\leq \\left(1 - \\frac{\\mu}{L}\\right)^T \\|\\boldsymbol{\\theta}^{(0)} - \\boldsymbol{\\theta}^*\\|^2$$\n\nThis is **linear convergence** (also called geometric or exponential convergence). The error decreases by a constant factor $(1 - 1/\\kappa)$ at each step."},"type":"text"},{"data":{"rows":[["Convex, smooth","$$O(1/T)$","$$O(1/\\epsilon)$","$$\\eta \\leq 1/L$"],["Strongly convex, smooth","$$O((1-\\mu/L)^T)$","$$O(\\kappa \\log(1/\\epsilon))$","$$\\eta = 1/L$"],["Non-convex, smooth","To stationary point","$$O(1/\\epsilon^2)$","$$\\eta \\leq 1/L$"]],"caption":"Convergence Rates for Batch Gradient Descent","headers":["Function Class","Rate","Iterations for ε-accuracy","Learning Rate"]},"type":"table"},{"data":{"content":"**Practical Implications**\n\n1. **Learning rate bounds**: The convergence theorems provide concrete guidance: $\\eta \\leq 1/L$ ensures convergence. If you see divergence (loss exploding), your learning rate likely violates this bound.\n\n2. **Condition number determines difficulty**: Problems with $\\kappa \\approx 1$ (isotropic) converge quickly. Problems with $\\kappa >> 1$ (ill-conditioned) converge slowly and may require preconditioning or adaptive methods.\n\n3. **Non-convex reality**: Deep learning loss surfaces are non-convex. We can't guarantee finding global minima, but gradient descent still finds stationary points (where $\nabla J \\approx 0$)."},"type":"text"}],"titleType":"number","titleNumber":4},{"id":"learning-rate-analysis","title":"Learning Rate Analysis","content":[{"data":{"content":"The learning rate $\\eta$ is the single most critical hyperparameter in gradient descent. Its value determines whether optimization succeeds, fails spectacularly, or crawls painfully slowly. Let's develop a deep understanding of learning rate dynamics.\n\n**The Stability Analysis**\n\nConsider optimizing a simple quadratic: $J(\\theta) = \\frac{1}{2}a\\theta^2$ where $a > 0$. The gradient is $\nabla J = a\\theta$, so the update becomes:\n\n$$\\theta^{(t+1)} = \\theta^{(t)} - \\eta \\cdot a \\cdot \\theta^{(t)} = (1 - \\eta a)\\theta^{(t)}$$\n\nFor convergence to $\\theta^* = 0$, we need $|1 - \\eta a| < 1$, which requires:\n\n$$0 < \\eta < \\frac{2}{a}$$\n\nThis is the **stability condition**. When $\\eta > 2/a$, the updates overshoot and oscillate with increasing magnitude—the optimization diverges."},"type":"text"},{"data":{"icon":"AlertCircle","title":"Divergence Warning","content":"If your loss suddenly jumps to NaN or infinity during training, the most likely cause is a learning rate that's too large. This violates the stability condition. The fix is simple: reduce the learning rate.","variant":"error"},"type":"callout"},{"data":{"content":"**The Three Regimes of Learning Rate**\n\n**1. Too Large ($\\eta > 2/L$)**: Divergence\n- Updates overshoot the minimum\n- Loss increases instead of decreasing\n- Parameters may become NaN\n- *Symptom*: Loss explodes or oscillates wildly\n\n**2. Too Small ($\\eta << 1/L$)**: Slow Convergence\n- Each update makes minimal progress\n- May take millions of iterations to converge\n- Gets stuck in noisy regions for a long time\n- *Symptom*: Loss decreases but painfully slowly\n\n**3. Just Right ($\\eta \\approx 1/L$)**: Optimal Convergence\n- Near-optimal convergence rate\n- Stable and efficient\n- Makes meaningful progress each iteration\n- *Symptom*: Loss decreases steadily and reasonably quickly"},"type":"text"},{"data":{"left":[{"data":{"items":["Loss increases instead of decreasing","Loss oscillates wildly between values","Loss becomes NaN or infinity","Loss decreases extremely slowly","Training takes unreasonably long","Loss plateaus far from expected value"],"title":{"icon":"XCircle","text":"Signs of Bad Learning Rate","type":"icon","color":"destructive","variant":"outline-circle"},"variant":"accent"},"type":"list"}],"right":[{"data":{"items":["Loss decreases consistently","Some small fluctuation is acceptable","Convergence within reasonable iterations","Final loss close to expected value","Gradient norms decrease over time","Training completes in expected time"],"title":{"icon":"CheckCircle","text":"Signs of Good Learning Rate","type":"icon","color":"primary","variant":"outline-circle"},"variant":"accent"},"type":"list"}]},"type":"two-column"},{"data":{"content":"**Finding the Right Learning Rate**\n\nIn practice, since we don't know $L$ exactly, we use empirical strategies:\n\n1. **Grid search**: Try values $\\{10^{-5}, 10^{-4}, 10^{-3}, 10^{-2}, 10^{-1}\\}$ and pick the largest that converges\n\n2. **Learning rate finder**: Exponentially increase $\\eta$ during a short training run and plot loss vs. learning rate. Choose $\\eta$ just before loss starts increasing.\n\n3. **Backtracking line search**: Start with large $\\eta$ and halve it until $J(\\theta - \\eta \nabla J) < J(\\theta)$ (Armijo condition).\n\n4. **Adaptive methods**: Use algorithms like Adam that automatically adjust per-parameter learning rates (covered later in this module)."},"type":"text"}],"titleType":"number","titleNumber":5},{"id":"computational-complexity","title":"Computational Complexity","content":[{"data":{"content":"Understanding the computational cost of batch gradient descent is essential for determining its applicability to different problem scales. Let's analyze the time and space complexity rigorously.\n\n**Time Complexity per Iteration**\n\nFor a dataset with $N$ examples and a model with $d$ parameters:\n\n- **Forward pass**: Computing $f_\\theta(\\mathbf{x}^{(i)})$ for all $N$ examples: $O(N \\cdot C_f)$ where $C_f$ is the cost of one forward pass\n\n- **Gradient computation**: Computing $\nabla_\\theta \\mathcal{L}$ for all $N$ examples via backpropagation: $O(N \\cdot C_b)$ where $C_b \\approx C_f$ (backward pass is similar cost)\n\n- **Gradient averaging**: Summing $N$ gradients: $O(N \\cdot d)$\n\n- **Parameter update**: One vector subtraction: $O(d)$\n\nFor neural networks, $C_f$ and $C_b$ are proportional to the number of parameters $d$, giving:\n\n$$\\text{Time per iteration} = O(N \\cdot d)$$"},"type":"text"},{"data":{"rows":[["Single forward pass","$$O(d)$","$$O(d)$","Very deep networks"],["Full-batch forward","$$O(N \\cdot d)$","$$O(N \\cdot d)$","Large datasets"],["Single backprop","$$O(d)$","$$O(d)$","Memory for activations"],["Full-batch gradient","$$O(N \\cdot d)$","$$O(d)$","Time on large $N$"],["Parameter update","$$O(d)$","$$O(d)$","Rarely the bottleneck"]],"caption":"Computational Cost Analysis","headers":["Operation","Time Complexity","Space Complexity","Bottleneck For"]},"type":"table"},{"data":{"content":"**The Scalability Problem**\n\nLet's make this concrete with real numbers:"},"type":"text"},{"data":{"rows":[["10,000","1 million","10 billion","100 seconds"],["1 million","1 million","1 trillion","~3 hours"],["10 million","1 million","10 trillion","~28 hours"],["100 million","1 million","100 trillion","~12 days"]],"headers":["Dataset Size ($N$)","Parameters ($d$)","Ops per Iteration","At 100 GFLOPS"]},"type":"table"},{"data":{"content":"For a modern dataset with millions of examples, **a single iteration of batch gradient descent can take hours or days**. Since training typically requires thousands of iterations, batch gradient descent becomes completely impractical.\n\nThis is the fundamental problem that stochastic gradient descent solves: instead of using all $N$ examples per update, use a small subset. We trade gradient accuracy for computational speed—and as we'll see, this trade-off is extremely favorable."},"type":"text"},{"data":{"icon":"AlertCircle","title":"The Curse of Scale","content":"Batch gradient descent computes the most accurate gradient possible but pays a price: O(N) computation per update. Modern datasets have N in the millions or billions. This makes batch GD impractical for most real-world deep learning—motivating the shift to stochastic methods.","variant":"warning"},"type":"callout"}],"titleType":"number","titleNumber":6},{"id":"limitations-failure-modes","title":"Limitations and Failure Modes","content":[{"data":{"content":"$7c"},"type":"text"},{"data":{"items":["**Saddle points**: In high dimensions, saddle points are far more common than local minima. Batch GD can get stuck at saddle points because the gradient vanishes despite the point not being a minimum.","**Ill-conditioned Hessian**: When eigenvalues of the Hessian vary widely, gradient descent oscillates across narrow valleys. Progress in the 'slow' directions is extremely slow.","**Plateau regions**: Regions where the loss is nearly flat cause vanishingly small gradients, stalling progress entirely.","**Ravine landscape**: Common in neural networks. Causes oscillation perpendicular to the optimal direction, requiring tiny learning rates that slow overall convergence.","**Poor initialization**: Starting in a bad region (far from any good minimum) can lead to extremely long convergence times or convergence to poor local optima."],"title":{"icon":"XCircle","text":"Failure Modes of Batch Gradient Descent","type":"icon","color":"destructive","variant":"outline-circle"},"variant":"glass"},"type":"list"},{"data":{"content":"**Limitation 4: Sensitivity to Curvature**\n\nA single learning rate must work for all parameters. But different parameters may need different step sizes:\n- Some parameters have high curvature (steep loss) → need small steps\n- Other parameters have low curvature (flat loss) → need large steps\n\nUsing one fixed $\\eta$ for all parameters is fundamentally suboptimal. This motivates adaptive learning rate methods like AdaGrad, RMSprop, and Adam, which we'll cover later.\n\n**Limitation 5: Deterministic Path**\n\nBatch gradient descent follows a completely deterministic path given the initial parameters. This means:\n- No chance to 'jump out' of poor local regions via gradient noise\n- No implicit exploration of the loss landscape\n- The minimum found depends entirely on initialization"},"type":"text"}],"titleType":"number","titleNumber":7},{"id":"when-to-use","title":"When to Use Batch Gradient Descent","content":[{"data":{"content":"$7d"},"type":"text"},{"data":{"rows":[["Dataset has < 1,000 examples","Dataset has > 10,000 examples"],["Problem is convex","Problem is highly non-convex"],["Memory allows full dataset","Dataset doesn't fit in memory"],["Need deterministic training","Training speed is critical"],["Debugging model issues","Production training at scale"]],"caption":"Batch GD Decision Guide","headers":["Consider Batch GD When","Avoid Batch GD When"]},"type":"table"},{"data":{"icon":"Lightbulb","title":"The Modern Reality","content":"In contemporary deep learning practice, batch gradient descent is rarely used directly. Mini-batch SGD or adaptive methods dominate. However, understanding batch GD is essential—it's the baseline from which all other methods are derived, and many theoretical results assume this setting.","variant":"tip"},"type":"callout"},{"data":{"content":"**Historical and Pedagogical Importance**\n\nEven if you never use pure batch gradient descent in practice, understanding it deeply is valuable:\n\n- **Foundation for theory**: Convergence theorems, learning rate analysis, and stability conditions extend (with modifications) to all gradient-based methods.\n\n- **Baseline for comparison**: When evaluating new optimizers, batch GD provides a clear baseline. Any new method should outperform it on relevant metrics.\n\n- **Building intuition**: The geometric and mathematical understanding developed here applies directly to understanding more sophisticated methods.\n\nIn the next pages, we'll see how stochastic gradient descent addresses the major limitations of batch GD while preserving the core gradient descent paradigm."},"type":"text"}],"titleType":"number","titleNumber":8},{"id":"summary","title":"Summary: Batch Gradient Descent","content":[{"data":{"content":"We've completed a thorough examination of batch gradient descent—the foundational optimization algorithm. Let's consolidate the key insights:"},"type":"text"},{"data":{"type":"ordered","items":["**Full-batch computation**: Each parameter update uses the gradient averaged over ALL training examples, giving the most accurate gradient estimate possible.","**Negative gradient direction**: Moving opposite to ∇J is the locally optimal direction for decreasing the loss, justified by first-order Taylor expansion.","**Learning rate bounds**: Stability requires η ≤ 2/L where L is the smoothness constant. Practical choice is η ≈ 1/L.","**Convergence guarantees**: Linear convergence for strongly convex functions, O(1/T) for convex functions, convergence to stationary points for non-convex.","**Computational cost**: O(N·d) per iteration makes batch GD prohibitively expensive for large datasets.","**Deterministic behavior**: Same initialization leads to same trajectory—useful for debugging, problematic for exploration.","**Limited practical use**: Modern deep learning rarely uses pure batch GD due to computational constraints and lack of implicit regularization."],"title":{"icon":"CheckCircle","text":"Key Takeaways","type":"icon","color":"primary","variant":"outline-circle"},"variant":"accent"},"type":"list"},{"data":{"content":"**What's Next**\n\nThe next page introduces **Stochastic Gradient Descent (SGD)**—the revolutionary modification that makes gradient-based optimization practical for large-scale machine learning. We'll see how using a single example (or small batch) instead of the full dataset dramatically changes the optimization dynamics while still converging to good solutions."},"type":"text"},{"data":{"icon":"CheckCircle","title":"Foundation Established","content":"You now have a rigorous understanding of batch gradient descent—its mathematics, geometry, convergence properties, implementation, and limitations. This foundation is essential for understanding why stochastic methods work and when to apply different optimization strategies.","variant":"success"},"type":"callout"}],"titleType":"number","titleNumber":9}],"isLocked":false},{"id":"seed_71eb870ab243ce2db5396ccfd0ec9321","title":"Stochastic Gradient Descent","order":1,"content":null,"isLocked":true},{"id":"seed_898b936ec29fe46dfd80f877f1d81783","title":"Mini-batch SGD","order":2,"content":null,"isLocked":true},{"id":"seed_4e2a774e5f6bc6a8d37d51f134b3e0d1","title":"Learning Rate Selection","order":3,"content":null,"isLocked":true},{"id":"seed_4d15965c24fcbe0048b6818491f8a714","title":"Convergence Analysis","order":4,"content":null,"isLocked":true}]}}