CS229 Lecture 3: Weighted Least Squares (Spring 2026)

Probabilistic Interpretation of Least Squares

The least squares solution can be derived as the maximum likelihood estimate under a Gaussian noise model. Assume each label y_i equals theta transpose x_i plus an error epsilon_i, where epsilon_i are independent and identically distributed normal random variables with mean zero and variance sigma squared. The likelihood of the observed data given theta is the product of Gaussian densities for each epsilon_i. Taking the log turns the product into a sum, and dropping constants that do not depend on theta yields the negative log‑likelihood proportional to the sum of squared residuals. Therefore maximizing the likelihood is equivalent to minimizing the least squares loss.

Maximum Likelihood Principle

The maximum likelihood framework consists of three steps: define a probabilistic model for how labels are generated from inputs and parameters, write the likelihood of the observed dataset as a function of the parameters, and choose the parameter setting that maximizes this likelihood (or equivalently minimizes the negative log‑likelihood). This principle is general; it does not depend on the specific distributional assumption and can be reused for other models such as logistic regression.

From Regression to Classification: Logistic Regression

For binary classification where labels y_i are zero or one, applying least squares directly leads to poor decision boundaries because the method tries to fit continuous values to discrete outcomes. Instead model the probability that y_i equals one as a function of the linear score theta transpose x_i passed through a sigmoid link function G(z) = 1/(1+exp(-z)). The likelihood of a single observation under this Bernoulli model is h_theta(x_i)^{y_i} (1‑h_theta(x_i))^{1‑y_i}. The log‑likelihood over the dataset is a sum of terms y_i log h_theta(x_i) + (1‑y_i) log(1‑h_theta(x_i)). Maximizing this log‑likelihood (or minimizing its negative) gives the logistic regression objective. The resulting optimization problem is convex and can be solved with first‑order methods such as gradient descent or stochastic gradient descent.

Optimization: Gradient Descent vs Newton's Method

Gradient descent (including its stochastic variant) updates theta by moving a small step in the direction opposite the gradient of the objective; each iteration costs O(ND) where N is the number of data points and D is the number of features. Newton's method uses second‑order information, updating theta by solving a linear system involving the Hessian matrix of second derivatives. When it converges, Newton's method can make much faster progress per iteration, often gaining many digits of precision in a single step. However each Newton step requires forming and inverting the Hessian, costing O(ND^2 + D^3) operations, which becomes prohibitive for large N and D. Consequently, in large‑scale machine learning settings stochastic gradient descent is preferred despite its slower per‑iteration convergence, while Newton's method remains useful in classical statistics problems with modest feature dimensions.