Linear regression

Linear regression models a numeric target as y = w0 + w1 x1 + ... + wp xp. Ordinary least squares (OLS) chooses the coefficients that minimise the residual sum of squares ||Xw - y||^2. The method goes back to Legendre (1805) and Gauss (1809). The minimiser has a closed form, the normal equations w = (X^T X)^-1 X^T y, which in practice is solved with a QR or singular value decomposition rather than an explicit inverse; the cost grows roughly with the number of samples times the square of the number of features. For very large data the same squared-error loss can instead be minimised with gradient descent.

Each coefficient is the expected change in the prediction for a one-unit change in that feature with the others held fixed, which is why linear models are prized for interpretability. That reading breaks down under multicollinearity: when features are strongly correlated, X^T X is close to singular and the coefficients become unstable and can flip sign between samples. Under the classical assumptions (linear relationship, independent errors with constant variance) OLS is the best linear unbiased estimator, and with normally distributed errors it is also the maximum likelihood estimate.

Regularised variants add a penalty to the loss. Ridge regression adds an L2 penalty alpha ||w||^2 that shrinks coefficients and copes better with correlated features; lasso adds an L1 penalty that drives some coefficients exactly to zero and so performs feature selection; elastic net combines the two. Non-linear relationships can still be captured by a linear model if the features are transformed first, for example with polynomial terms or splines, since the model only needs to be linear in its weights.

Squared error is sensitive to outliers, because one far-off point can pull the whole line. Robust alternatives such as Huber, RANSAC and Theil-Sen regression reduce that influence, and quantile regression predicts a chosen quantile instead of the mean.