Gradient Descent Implementation vs Closed-Form Solution: A Complete Python Comparison

The gradient descent implementation in rohitg00/ai-engineering-from-scratch uses iterative updates to minimize MSE loss through analytical gradients, while scikit-learn leverages optimized LAPACK routines for an instant closed-form solution, with both approaches demonstrating comparable accuracy but vastly different computational characteristics.

The rohitg00/ai-engineering-from-scratch repository provides a pedagogical deep dive into machine learning fundamentals, specifically showcasing how linear regression works under the hood. In phases/02-ml-fundamentals/02-linear-regression/code/linear_regression.py, the curriculum implements both a gradient descent optimizer and a normal equation solver, allowing direct comparison with production-grade scikit-learn implementations.

The Gradient Descent Implementation

The from-scratch gradient descent approach lives in lines 18–50 of linear_regression.py within the LinearRegression class. This implementation demonstrates the fundamental optimization loop that powers modern deep learning.

Algorithm and Key Methods

The class exposes three critical methods that implement the iterative learning process:

• compute_cost: Calculates the Mean Squared Error (MSE) loss between predictions and targets
• compute_gradients: Derives analytical gradients (dw, db) of the loss with respect to weights and bias
• fit: Executes the training loop for a specified number of epochs, updating parameters using the learning rate

Each epoch costs O(n) where n equals the number of samples. The update rule follows the standard gradient descent formula: w = w - learning_rate * dw.

Hyperparameters and Convergence

Unlike closed-form solutions, this implementation requires tuning:

• learning_rate: Controls step size; too large causes divergence, too small slows convergence
• epochs: Determines the number of iterative passes over the dataset
• print_every: Optional logging frequency for monitoring cost reduction

The convergence speed depends heavily on data conditioning and feature scaling. The repository demonstrates this sensitivity through the comparison block in lines 303–426.

The Closed-Form Normal Equation

Lines 68–81 implement the LinearRegressionNormal class, which solves the normal equation directly without iteration.

Mathematical Foundation

This approach computes the exact solution using:

• Weight calculation: w = Σ((x-x̄)(y-ȳ)) / Σ((x-x̄)²)
• Bias calculation: b = ȳ - w·x̄

The algorithm performs a single pass over the data (O(n)) plus arithmetic operations, delivering an exact solution (subject to floating-point precision) without hyperparameter tuning.

When to Use the Analytical Approach

The normal equation excels in educational contexts and small-to-medium datasets where deterministic answers are preferred. However, it relies on floating-point subtraction of means, which can suffer from catastrophic cancellation on poorly-scaled data.

Scikit-Learn's Optimized Solution

The comparison block (lines 303–426) imports sklearn.linear_model.LinearRegression, which represents the production-standard approach. Under the hood, scikit-learn calls LAPACK-backed ordinary least squares (OLS) routines using QR or SVD decomposition.

Computational Complexity

While the from-scratch implementations operate in O(n) time, scikit-learn solves a linear system with typical complexity O(n·d²) where d represents the number of features. Despite the higher theoretical complexity, the compiled BLAS/LAPACK implementations outperform pure Python loops through optimized matrix operations.

Numerical Stability

Scikit-learn automatically handles ill-conditioned matrices through numerically stable decompositions. This robustness contrasts with the from-scratch implementations, where the gradient descent variant requires careful learning rate selection and the normal equation can accumulate floating-point errors.

Side-by-Side Code Comparison

The repository includes a demonstration harness that fits identical synthetic data across all three implementations:

# 1️⃣ Gradient Descent from scratch

from phases/02-ml-fundamentals/02-linear-regression/code/linear_regression import LinearRegression

model_gd = LinearRegression(learning_rate=0.005)
model_gd.fit(X, y, epochs=1000, print_every=200)
print(f"GD result: y = {model_gd.w:.4f}x + {model_gd.b:.4f}")

# 2️⃣ Closed-form (Normal Equation) from scratch

from phases/02-ml-fundamentals/02-linear-regression/code/linear_regression import LinearRegressionNormal

model_eq = LinearRegressionNormal()
model_eq.fit(X, y)
print(f"Normal-eq result: y = {model_eq.w:.4f}x + {model_eq.b:.4f}")

# 3️⃣ scikit-learn's OLS implementation

from sklearn.linear_model import LinearRegression as SklearnLR
import numpy as np

X_np = np.array(X).reshape(-1, 1)          # scikit-learn expects 2-D input

y_np = np.array(y)

sk_model = SklearnLR()
sk_model.fit(X_np, y_np)
print(f"sklearn result: y = {sk_model.coef_[0]:.4f}x + {sk_model.intercept_:.4f}")

Performance and Complexity Analysis

Time Complexity Comparison

Implementation	Time Complexity	Key Characteristics
Gradient Descent	O(n) per epoch	Iterative; requires multiple passes until convergence
Normal Equation	O(n) total	Single-pass computation of means and covariance
Scikit-Learn	O(n·d²)	Optimized linear algebra; fastest wall-clock time for typical datasets

Numerical Stability Trade-offs

Gradient descent remains sensitive to feature scaling and learning rate selection, potentially diverging or converging to sub-optimal points. The normal equation relies on mean subtraction, risking catastrophic cancellation on poorly-scaled data. Scikit-learn mitigates both issues through automatic preprocessing and stable matrix factorizations.

Educational vs Production Use

The LinearRegression class (gradient descent) serves as a didactic tool for understanding optimization fundamentals including learning rate scheduling and loss landscapes. The LinearRegressionNormal class demonstrates that linear regression admits closed-form solutions. Scikit-learn provides the robust, battle-tested implementation suitable for production pipelines where numerical stability and speed matter.

Summary

• Gradient descent (lines 18–50) implements iterative optimization with O(n) per-epoch complexity, requiring hyperparameter tuning but demonstrating how neural networks learn
• Normal equation (lines 68–81) provides an exact O(n) solution without iterations but lacks scalability to high-dimensional features
• Scikit-learn leverages decades of linear algebra research via LAPACK for numerically stable, instant solutions
• The comparison block (lines 303–426) validates that all three approaches converge to equivalent coefficients given sufficient iterations and proper scaling

Frequently Asked Questions

Why use gradient descent when a closed-form solution exists?

Gradient descent becomes essential for models where closed-form solutions do not exist, such as neural networks, logistic regression, and regularized linear regression with complex penalty terms. The iterative approach also scales better to massive datasets where computing the full covariance matrix becomes prohibitive.

How does the learning rate affect the from-scratch implementation?

The learning_rate parameter in LinearRegression.fit() controls the step size during each parameter update. A rate too high causes divergence (increasing loss), while a rate too low requires excessive epochs to converge. The print_every parameter helps monitor this balance by logging cost values at specified intervals.

Is scikit-learn always faster than the from-scratch implementations?

For small datasets, the overhead of scikit-learn's type checking and input validation may make the pure Python normal equation appear competitive. However, for datasets with many features or samples, scikit-learn's compiled LAPACK routines significantly outperform interpreted Python loops, especially in the gradient descent case which requires thousands of iterations.

When should I use the normal equation over gradient descent?

Choose the normal equation when working with small-to-medium datasets (fewer than tens of thousands of samples) where you need a deterministic answer without hyperparameter tuning. Use gradient descent when handling large datasets that don't fit in memory for matrix inversion, or when extending the code to support stochastic mini-batches or complex loss functions.

{
  "mcpServers": {
    "instagit": {
      "command": "npx",
      "args": ["-y", "instagit@latest"]
    }
  }
}