Linear Models & Optimization

Linearity in the parameters, independent errors, constant variance, roughly normal residuals. Heteroscedasticity or correlated errors leave coefficients unbiased but break the standard-error formula, so p-values need robust errors.

A coefficient is the expected change in the target per one-unit rise in that feature with others held fixed. Correlated features make that clause unobservable and destabilize signs; unequal scales make magnitudes incomparable, so standardize.

A linear fit is unbounded, so it predicts probabilities below zero or above one and is skewed by far-off points. Logistic regression squashes the score through a sigmoid into a log-odds model and trains on convex log-loss.

Common variants: SGD with momentum (accumulates past gradients), AdaGrad (per-parameter adaptive step), RMSProp (AdaGrad with a decaying average against step collapse), Adam (momentum + RMSProp) and Adan. They differ in how they adapt the step size and smooth the gradient direction.

With gradient-based optimization, not the closed-form matrix formula. The staples are full-batch gradient descent (GD), which uses all samples per step, and stochastic gradient descent (SGD), which uses one sample or a mini-batch. SGD scales to large data and is the usual default.

It assumes features are conditionally independent given the class, which words are not. It survives because classification needs only the right argmax, not calibrated probabilities — correlated words lift every class score alike.

Regularization fights overfitting by adding a weight-norm penalty to the optimization objective. For linear models: L1 (sum of absolute weights), L2 (sum of squared weights), and Elastic Net (a mix of L1 and L2). The penalty discourages overly large weights.

Plot residuals against fitted values — healthy is a shapeless band around zero. A widening funnel means error variance grows with the prediction, so transform the target or use robust errors. A curve means the form is misspecified.

A generative model learns the joint distribution — class prior plus per-class feature distribution — and derives the posterior. A discriminative one fits the boundary directly. Naive Bayes hits its higher asymptotic error sooner and wins on tiny data.

Minimizing the squared error gives w = (XᵀX)⁻¹Xᵀy. It is avoided because inverting XᵀX is costly on many features, and XᵀX may be singular or ill-conditioned, so the inverse is impossible or numerically unstable. Adding λI fixes the conditioning; gradient methods are preferred.

A symptom of overfitting is very large weights. With huge weights, two near-identical inputs differing by epsilon can yield wildly different predictions — the function is unstable. Penalizing the norm shrinks weights toward zero, giving a smoother, lower-variance function that generalizes better.

Momentum keeps an exponentially-weighted sum of recent gradients and steps along it, damping oscillations. It helps most on elongated (ill-conditioned) level curves: the gradient points across the valley, so plain SGD zig-zags, while momentum averages the swing out and moves along the valley.

Geometrically L1's constraint is a diamond with corners on the axes; the loss level-set usually touches a corner, where a weight is 0. L2's is a circle with no corners. By gradient, L1's |∂R/∂w| is constant so descent reaches 0, while L2's shrinks as w→0 and weights stop short.

The margin is the band between the hyperplane and the nearest points, and training maximizes its width. Support vectors are the points on or violating it — only they define the solution. Large C narrows the margin, small C widens it.

The L1 part zeroes weights for selection, the L2 part shrinks smoothly and keeps the problem well-posed. On correlated features pure Lasso keeps one arbitrarily and drops the rest; the L2 term spreads weight across the whole group instead.

Under perfect separation the maximum-likelihood optimum does not exist — scaling the weights up pushes log-loss toward zero without reaching it, so they diverge and the solver stops only on its iteration cap. A penalty pins a finite solution.

No. The intercept only shifts the hyperplane to where the data sits; it is not a weight on a feature. Penalizing it pulls the offset toward zero and stops the model from positioning the hyperplane well, so quality gets worse. By convention the bias is excluded from the penalty.

The standard algorithm (Gauss–Jordan / LU) is cubic, O(n³). Strassen-style multiplication gives about O(n^2.81), and asymptotically faster ones exist but carry huge constants and practical constraints, so they are rare. This cubic cost is why closed-form OLS is avoided.