Supervised learning

Formal statement#

Supervised learning assumes a sample drawn independently from a fixed joint distribution.

Given   S = {(x_1, y_1), ..., (x_n, y_n)}  drawn i.i.d. from D over X x Y
Find    h : X -> Y  minimising  R(h) = E_{(x,y) ~ D} [ L(h(x), y) ]

• x_i — feature vector for example i, typically in R^d
• y_i — label; {1..K} for K-class classification, R for regression
• D — the unknown joint distribution over features and labels
• L — a loss function scoring the mismatch between prediction and label
• R(h) — the true risk, the quantity we want small

The i.i.d. assumption is doing enormous work here. It fails under distribution shift, time-series dependence, and any sampling process correlated with the label. Most production failures of supervised learning are failures of this assumption, not of the optimiser.

Loss functions#

The choice of L defines what "correct" means, and different losses induce genuinely different optimal predictors.

0-1 loss           L(y_hat, y) = 1 if y_hat != y else 0
Squared error      L(y_hat, y) = (y_hat - y)^2
Absolute error     L(y_hat, y) = |y_hat - y|
Binary cross-ent.  L(p, y)     = -( y*log(p) + (1-y)*log(1-p) )
Hinge (SVM)        L(f, y)     = max(0, 1 - y*f),   y in {-1, +1}

• y_hat — the model's prediction
• y — the true label
• p — predicted probability of the positive class, in the open interval (0, 1)
• f — the raw real-valued model score before any threshold

The minimiser of expected squared error is the conditional mean E[y | x]. The minimiser of expected absolute error is the conditional median. This is why absolute error is more robust to outliers. It is not a heuristic preference — it is a different estimand.

0-1 loss is discontinuous and non-convex, so it is not directly optimised. Cross-entropy and hinge loss are convex surrogates, meaning tractable stand-ins. Bartlett, Jordan & McAuliffe (2006) established the classification-calibration conditions under which minimising a surrogate also minimises 0-1 risk.

The Bayes optimal predictor#

The best achievable predictor under 0-1 loss is:

h*(x) = argmax_{k} P(y = k | x)

Its risk R(h*) is the Bayes error, the irreducible error arising from genuine overlap between classes. No model, no amount of data, and no architecture can go below it.

This matters when reading benchmark claims. Suppose a paper reports 92 percent accuracy. That is excellent against a Bayes error of 7 percent, and mediocre against 1 percent. The Bayes error is unknown for real datasets. That is precisely why human-level performance is often used as a rough proxy.

Consistency and sample complexity#

An estimator is consistent if R(h_hat_n) -> R(h*) in probability as n -> infinity. Consistency is an asymptotic guarantee, and asymptotic guarantees say nothing about the sample you actually have.

For a finite hypothesis class H in the realisable case (some h in H has zero risk), PAC theory gives:

n  >=  ( log|H| + log(1/delta) ) / epsilon

• n — number of labelled examples required
• |H| — size of the hypothesis class
• epsilon — target excess risk
• delta — allowed failure probability

In the agnostic case the dependence worsens to 1/epsilon^2. Replacing log|H| with the VC dimension extends this to infinite classes.

Label noise#

Real labels are wrong some of the time. Under symmetric label noise with flip rate eta < 0.5, Natarajan et al. (2013) showed that loss correction can recover an unbiased risk estimate. Under asymmetric or instance-dependent noise, guarantees are considerably weaker.

Empirically, deep networks fit clean patterns before they memorise noisy labels (Arpit et al., 2017). That ordering is why early stopping is a surprisingly effective noise defence.

Reducing the label bottleneck#

Labels dominate cost, so several families of methods attack that directly.

Transfer and self-supervised pretraining are the dominant practical answers today. They largely explain why the field moved from training per-task models to fine-tuning foundation models.

Key references#

• Vapnik, V. (1998). Statistical Learning Theory. Wiley.
• Hastie, T., Tibshirani, R. & Friedman, J. (2009). The Elements of Statistical Learning, 2nd ed. Springer. Free PDF from the authors.
• Bartlett, P., Jordan, M. & McAuliffe, J. (2006). Convexity, Classification, and Risk Bounds. JASA 101(473).
• Natarajan, N. et al. (2013). Learning with Noisy Labels. NeurIPS.
• Arpit, D. et al. (2017). A Closer Look at Memorization in Deep Networks. ICML.

What to learn next#

• Model evaluation — estimating R(h) and quantifying the estimate's variance.
• Overfitting and underfitting — decomposing the gap between empirical and true risk.
• Linear regression — the closed-form case where all of this is exactly solvable.