Machine Learning Theory

Machine Learning Theory

Machine learning is applied statistics, optimization theory, and linear algebra at scale. Understanding the theoretical foundations prevents the "black box" trap: knowing why models fail, what sample size you need, and which algorithm suits which problem.

The Learning Problem

Formally, supervised learning is: given a training set {(x₁,y₁), ..., (xₙ,yₙ)} drawn from an unknown distribution P(X,Y), find a hypothesis h: X → Y that generalizes well to new samples from P.

Empirical Risk Minimization (ERM): minimize average loss on training data. The risk (true error) is the expected loss over P; we minimize empirical risk as a proxy. But minimizing training loss doesn't guarantee minimizing test error.

Generalization gap: difference between test error and training error. A large gap means overfitting. The generalization gap is bounded by O(√(d/n)) where d is model complexity (VC dimension) and n is training size — more data and simpler models generalize better.

PAC Learning Framework

PAC (Probably Approximately Correct) learning formalizes generalization. A concept class C is PAC-learnable if there exists an algorithm A such that for any ε, δ > 0, any target concept c ∈ C, and any distribution P, given m ≥ O(1/ε · log(1/δ) · VC(C)) samples, A outputs a hypothesis with error ≤ ε with probability ≥ 1−δ.

The VC dimension (Vapnik-Chervonenkis) measures hypothesis class capacity: the size of the largest set that can be "shattered" (any labeling realized). A linear classifier in ℝᵈ has VC dimension d+1. Neural networks' VC dimension grows with parameters.

This theoretical framework tells you: to halve your error, you need ~4x more data (all else equal). To double model capacity, you need proportionally more data to maintain the same generalization.

Bias-Variance Decomposition

The expected test error decomposes as:

E[error] = (Bias)² + Variance + Irreducible Noise

Bias measures systematic error: a linear model fitted to nonlinear data always misses the true function regardless of how much data you have. Variance measures sensitivity to training set: a deep tree can memorize any training set but performs poorly on new data.

The bias-variance tradeoff: reducing bias (more complex model) typically increases variance. The goal is the sweet spot — the model complexity where total error is minimized. In practice: start simple, measure validation error, increase complexity until validation error stops improving.

Ensemble methods reduce variance without increasing bias: random forests average many high-variance, low-bias trees; boosting (AdaBoost, XGBoost) reduces bias by sequentially fitting residuals.

Optimization

Gradient descent moves parameters downhill on the loss surface. The loss surface of deep networks is high-dimensional with many saddle points (not local minima — saddle points have zero gradient but are escapable). Research shows SGD naturally escapes saddle points due to gradient noise.

Stochastic Gradient Descent (SGD): compute gradient on one sample (or mini-batch). Noisy but fast, and the noise actually helps generalization (implicit regularization). Mini-batch SGD (batch size 32-512) balances noise and hardware efficiency.

Learning rate is the most important hyperparameter. Too large: oscillates or diverges. Too small: slow convergence. Learning rate schedules (cosine annealing, warmup) adjust lr during training. Adaptive optimizers (Adam, AdaGrad) maintain per-parameter learning rates based on gradient history, dramatically reducing hyperparameter sensitivity.

Vanishing/exploding gradients in deep networks: backpropagation multiplies Jacobians at each layer; with many layers, gradients either vanish (near zero, no learning) or explode (overflow). Solutions: careful initialization (Xavier/Kaiming), batch normalization, residual connections (skip connections in ResNets add gradients directly, bypassing multiplication).

Neural Networks

A neural network is a composition of linear transformations and nonlinear activations. Each layer: y = σ(Wx + b) where W is a weight matrix, b is a bias vector, and σ is an elementwise nonlinearity.

Universal Approximation Theorem: a feedforward network with one hidden layer and enough neurons can approximate any continuous function on a compact domain to arbitrary precision. But "enough neurons" may be exponential — deep networks approximate efficiently what shallow networks require exponential width for.

Activation functions: sigmoid (historical, now mostly deprecated for hidden layers — vanishing gradients), tanh (better than sigmoid, still used), ReLU (max(0,x) — zero gradient for x<0 ("dying ReLU") but simple and effective), GELU (smooth approximation of ReLU, used in transformers).

Convolutional Neural Networks (CNNs): exploit spatial structure through weight sharing. A convolution applies the same filter at every position — this inductive bias is exactly right for images (translation invariance), making CNNs far more sample-efficient than fully connected networks for vision.

Attention and Transformers: instead of processing sequences recurrently, transformers compute a weighted average of all positions (attention = softmax(QKᵀ/√d)V). The self-attention mechanism allows arbitrary dependencies between positions. Transformers scale extremely well with data and compute — the foundation of GPT, BERT, and all modern LLMs.

Regularization

Regularization reduces overfitting by penalizing complexity. L2 regularization (weight decay) adds λ·‖w‖² to the loss, penalizing large weights — equivalent to Gaussian prior on weights in Bayesian terms. L1 regularization adds λ·‖w‖₁, inducing sparsity (weights become exactly zero) — equivalent to Laplace prior, useful for feature selection.

Dropout randomly zeroes neurons during training with probability p. At test time, all neurons are used but outputs are scaled by (1−p). Interpreted as training an ensemble of 2ⁿ sub-networks and averaging.

Early stopping: monitor validation loss; stop when it starts increasing. Simple and effective — keeps the model at the point of best generalization before overfitting sets in.