Linear Regression is one of the simplest supervised learning algorithms. It models a continuous target value as a linear combination of input features.
At its core, the model assumes that the prediction can be written as: , where X is the input feature matrix,
w is the weight vector, and b is the bias term.Despite its simplicity, Linear Regression is still useful as a baseline model, a debugging tool, and a foundation for understanding optimization. It also introduces the core training pattern used throughout machine learning:
prediction → loss → gradient → parameter updateIn this post, we will implement Linear Regression in two ways:
- Closed-form OLS for Line Fitting
- Gradient Descent for multi-feature Linear Regression
The first version gives us an exact analytical solution. The second version shows the scalable optimization pattern that connects directly to Logistic Regression, neural networks, and modern model training.
Core Concepts
- Prediction (The Forward Pass): Calculated via the linear combination or dot product of features and weights, plus a bias term.
- Given 2D points , Linear Regression fits a line:
- For multiple input features, the model generalizes to:
Example: predicting Uber prices based on three attributes (time of day , ride length , duration ):
- Mean Squared Error (MSE) Loss: The most common objective for Linear Regression is Mean Squared Error:
It measures the average squared difference between estimated predictions and actual ground truth targets, acting as a smooth, differentiable objective function.
Closed Form vs. Gradient Descent
Linear Regression can be solved in two common ways.
- The analytical Closed-Form approach (including Ordinary Least Squares or the Normal Equation, ）provides an exact global minimum and gives an exact answer directly.
- Given 2D points , to fit a line , the slope can be computed using covariance and variance. The 1D closed-form solution is clean and efficient.
- For multi-feature Linear Regression, the general Normal Equation is: . This is elegant, but matrix inversion () becomes expensive when the number of features is large. The matrix inversion step scales roughly as , where
Dis the number of features. So it scales poorly as the number of features grows. There is also a numerical stability issue. If features are highly correlated, can become singular or nearly singular, making the inverse unstable or impossible to compute directly.
This is why large-scale Linear Regression is often trained using Gradient Descent or one of its variants.
- Gradient Descent solves the problem iteratively. Instead of computing the answer in one step, we repeatedly update the weights in the direction that reduces the loss. This is the same optimization pattern used by Logistic Regression and neural networks. It scales linearly, making it the standard engine for large production datasets.
Closed-Form OLS for Line Fitting
Given 2D points , we want to fit a line .
The optimal slope is: . That is,
slope = covariance(x, y) / variance(x)Once the slope
w has been determined, the intercept b can be obtained by requiring the fitted line to pass through the mean point (, ). Therefore, .Multi-Feature Linear Regression with Gradient Descent
For multiple features, each sample is a vector:
The prediction is ， where
w is the weight vector and b is the bias term.To learn the model parameters, we minimize the mean squared error (MSE) loss: , where
N is the number of training samples.The gradients of the loss function with respect to the parameters are:
Using gradient descent, the parameters are updated iteratively as
where is the learning rate.
For the multi-feature version, I use Gradient Descent. Each iteration starts with a forward pass: I compute predictions using
X @ weights + bias. Then I calculate the prediction error. From the MSE objective, the gradient with respect to the weights is X.T @ errors / num_samples, and the gradient with respect to the bias is the average error.After computing the gradients, I update the weights and bias in the opposite direction of the gradient, scaled by the learning rate. This avoids matrix inversion and gives us a scalable training pattern that also generalizes to Logistic Regression and neural networks.
Algorithmic Complexity
Let
n be the number of sample observations, d be the number of input features, and T be the total training iterations.- Time Complexity:
- Analytical OLS (2D Line Fit): — We scan the array of points linearly to compile the arithmetic means, covariances, and variances.
- Gradient Descent Engine: — Every optimization epoch tracks a matrix forward pass costing and a backpropagation pass computing gradients across
dseparate features.
- Space Complexity:
- Storing data dimensions takes space. The parameters (weights and inner gradients) scale compactly at , allowing the model's footprint to scale optimally in data-heavy environments.
FAQs
Q1: What are the fundamental statistical assumptions of Linear Regression? What happens if they are violated?
Classical Ordinary Least Squares relies on four key structural assumptions:
- Linearity: The relationship between features and targets must be a linear combination.
- Independence: Multi-row observations must be independent of one another (no auto-correlation).
- Homoscedasticity: The variance of the error terms (residuals) must remain constant across all levels of independent variables.
- Normality of Errors: Residuals should be normally distributed around a mean of zero.
If Homoscedasticity is violated (a condition known as heteroscedasticity), our model's standard errors become biased, making confidence intervals and p-value hypothesis testing highly unreliable, even if the weight predictions themselves remain unbiased.
Q2: What is Multicollinearity, and why is it dangerous for the closed-form solution?
Multicollinearity occurs when two or more independent features in our dataset are highly linearly correlated with each other. In the closed-form Normal Equation (), this causes the matrix product to approach a singular matrix, meaning it becomes uninvertible or numerically unstable. This inflates the variance of our estimated weights, making our model highly sensitive to tiny changes in the training data and stripping the model of feature interpretability.
We can detect this using the Variance Inflation Factor (VIF) and resolve it by removing redundant columns, using Principal Component Analysis (PCA), or adding L2 Regularization (Ridge Regression) to force stability onto the matrix inversion.
Q3: How do you choose between using the Closed-Form Normal Equation and Gradient Descent in a production pipeline?
The decision comes down to the scale of our feature space and the shape of our data pipeline. The Closed-Form Normal Equation provides an exact analytical minimum without hyperparameter tuning, but it requires calculating a matrix inversion that scales at , where
d is the number of features. If our system handles hundreds of thousands of features, this inversion becomes computationally prohibitive and memory-intensive. Gradient Descent, scaling at , handles massive, high-dimensional datasets far better. It also integrates seamlessly with streaming or online production architectures using Stochastic Gradient Descent (SGD) to ingest new samples incrementally without retraining from scratch.
How This Appears in Modern AI Systems
Linear Regression is rarely the final model in modern large-scale AI systems, but it remains useful in several places:
- Baseline modeling: A simple regression baseline helps evaluate whether a more complex model is actually adding value.
- Feature sanity checks: If a single feature has strong linear predictive power, Linear Regression can reveal it quickly.
- Linear heads: Neural networks often end with linear layers that behave like learned weighted combinations of hidden features.
- Optimization intuition: The same forward-pass, loss, gradient, update loop appears in Logistic Regression, MLPs, Transformers, and language model training.
- Author:Fan Luo
- URL:https://fanluo.me/article/linear-regression-from-scratch
- Copyright:All articles in this blog adopt BY-NC-SA agreement. Please indicate the source!
上一篇
Logistic Regression from Scratch
下一篇
Shrinking the Search Space with Binary Search