The Modern Mathematics of Deep Learning

Decomposing excess risk

Penguin learning project

The project uses 342 complete Palmer penguin records: 240 training-pool and 102 held-out rows. The selected training rows determine feature scaling and model parameters. Source CSV

This project trains weights with softmax, unlike the homepage lab, which uses nearest species averages. Same penguin measurements; different classification methods. Predictions can differ.

Generalization and risk bounds · Relate sample behavior to population risk under stated assumptions.

The project supplies finite observations and fitted parameters. A held-out sample does not establish population bounds or prove a theorem.

Consider this concept alongside the project; its source assumptions may differ. These observations do not prove a theorem.

Input: 12 × 2; Held-out evaluation: 102 · #58 · 40.6 mm, 193 mm. Known answer: Adélie; Prediction: Adélie · [≈0.7383, ≈0.2444, ≈0.01737].

Used in these source sections: 1.2 Learning from examples · 1.2.1 Finding better settings · 1.2.2 Can the network express the answer? · More source sections

The source splits excess risk into optimization error, generalization error, and approximation error. The generalization term appears twice in the bound.

The toy distribution has equally likely targets 0 and 1. The hypothesis class contains constant predictors 0 and 1; the chosen predictor is 0.

The decomposition identifies different reasons a learned rule can have excess risk.

Source formula example

\begin{split}{\mathcal{R}}(f_{S})-{\mathcal{R}}^{*}&={\mathcal{R}}(f_{S})-\widehat{\mathcal{R}}_{S}(f_{S})+\widehat{\mathcal{R}}_{S}(f_{S})-\widehat{\mathcal{R}}_{S}(f^{*}_{\mathcal{F}})+\widehat{\mathcal{R}}_{S}(f^{*}_{\mathcal{F}})-{\mathcal{R}}(f^{*}_{\mathcal{F}})+{\mathcal{R}}(f^{*}_{\mathcal{F}})-{\mathcal{R}}^{*}\\ &\leq{\varepsilon}^{\mathrm{opt}}+2{\varepsilon}^{\mathrm{gen}}+{\varepsilon}^{\mathrm{approx}}\end{split}

illustration · This computes the decomposition and bound for one finite toy class and a known distribution. It does not prove the inequality for general classes.

Symbols

$ε^{opt}$: Difference between the chosen rule’s sample risk and the best sample risk in the class.
$ε^{gen}$: Largest absolute population-to-sample risk gap in the class.
$ε^{approx}$: Difference between best class population risk and optimal population risk.

Source formula example

This source example uses its own inputs and assumptions. Editing it does not change the project.

Edit a value or the code, then run the example. This is a finite demonstration, not a proof of the paper’s theorem.

First sample target

This example’s data flow

You choose

input.first = 0

Initial values in code

populationClassRisk = 0.5
optimalRisk = 0.25

Calculated here

Result expression: { empiricalZero, empiricalOne, classPopulationRisks: [populationClassRisk, populationClassRisk], oneSidedGap: Math.max( populationClassRisk - empiricalZero, populationClassRisk - empiricalOne, ), bestClassPrediction: ...

sample = [input.first, 0] Uses: input.first
empiricalZero = empirical(0) Uses: empirical
empiricalOne = empirical(1) Uses: empirical
optimization = empiricalZero - Math.min(empiricalZero, empiricalOne) Uses: empiricalZero, empiricalOne
generalization = Math.max( Math.abs(populationClassRisk - empiricalZero), Math.abs(populationClassRisk - empiricalOne), ) Uses: populationClassRisk, empiricalZero, empiricalOne
approximation = populationClassRisk - optimalRisk Uses: populationClassRisk, optimalRisk
excessRisk = populationClassRisk - optimalRisk Uses: populationClassRisk, optimalRisk
pieces = [ populationClassRisk - empiricalZero, empiricalZero - empiricalZero, empiricalZero - populationClassRisk, approximation, ] Uses: populationClassRisk, empiricalZero, approximation

Returns

Example result

empiricalZero: 0
empiricalOne: 1
classPopulationRisks: array (2 items): [0.5, 0.5]
oneSidedGap: 0.5
bestClassPrediction: 0
pieces: array (4 items): [0.5, 0, -0.5, 0.25]
excessRisk: 0.25
optimization: 0

… (11 items)

JavaScript

const sample = [input.first, 0];
if (!sample.every((y) => y === 0 || y === 1))
  throw new Error("Targets must be 0 or 1.");
const empirical = (prediction) =>
  sample.reduce((sum, y) => sum + (prediction - y) ** 2, 0) / sample.length;
const empiricalZero = empirical(0);
const empiricalOne = empirical(1);
const populationClassRisk = 0.5;
const optimalRisk = 0.25;
const optimization = empiricalZero - Math.min(empiricalZero, empiricalOne);
const generalization = Math.max(
  Math.abs(populationClassRisk - empiricalZero),
  Math.abs(populationClassRisk - empiricalOne),
);
const approximation = populationClassRisk - optimalRisk;
const excessRisk = populationClassRisk - optimalRisk;
const pieces = [
  populationClassRisk - empiricalZero,
  empiricalZero - empiricalZero,
  empiricalZero - populationClassRisk,
  approximation,
];
return {
  empiricalZero,
  empiricalOne,
  classPopulationRisks: [populationClassRisk, populationClassRisk],
  oneSidedGap: Math.max(
    populationClassRisk - empiricalZero,
    populationClassRisk - empiricalOne,
  ),
  bestClassPrediction: 0,
  pieces,
  excessRisk,
  optimization,
  generalization,
  approximation,
  bound: optimization + 2 * generalization + approximation,
};

Read numbers from input and return the result. JavaScript basics.

Result

Enable JavaScript to run this example.

Technical statement

The source assumes a population-risk minimizer in the hypothesis class for the displayed decomposition. The toy class has two equally good population minimizers; the code chooses predictor 0 as f*₍F₎. The unrestricted squared-loss optimum is predictor 1/2 with risk 1/4.

Source: Source expression