Introduction

This site is the mathematical companion to Rust for Machine Learning. The book builds machine learning systems from first principles and deliberately keeps the mathematics to the minimum needed to keep building. This site is where the rest of that mathematics lives: formal definitions, theorems with full proofs, and complete derivations of every construction the book uses.

Nothing here is required to follow the book. Everything here is for the reader who, at some point in a chapter, asks "but why is that true?" — and wants a real answer.

How this site is organized

Each section covers the mathematics of one machine-learning subject, in the order the book develops them. Sections go live one at a time, as they are written; the full map of the book is below so you can see where each companion section will land.

Book chapter	Companion section
Introduction — Programs that Learn	—
Chapter 1 — The First Neuron	The Perceptron
Chapter 2 — The Search for Structure	Maximum-Margin Separation (planned)
Chapter 3 — A Framework for Learning	The Statistical Learning Framework (planned)
Chapter 4 — Building the Toolkit	The Linear Algebra of Learning Systems (planned)
Chapter 5 — Representations by Hand	Kernels and Feature Spaces (planned)
Chapter 6 — From Hard Decisions to Probabilities	Probabilistic Classification (planned)
Chapter 7 — Optimization	Optimization for Learning (planned)
Chapter 8 — Neural Networks	(planned)
Chapter 9 — Deep Neural Networks	(planned)
Chapter 10 — Convolutional Neural Networks	(planned)
Chapter 11 — Recurrent and Sequential Networks	(planned)
Chapter 12 — Making Rust Fast	(planned)
Chapter 13 — Unsupervised Learning	(planned)
Chapter 14 — Reinforcement Learning	(planned)
Chapter 15 — A Glimpse into Transformers	(planned)
Chapter 16 — Rust for ML in Production	(planned)

Every page opens with an In the book line pointing to the chapter and section it formalizes, and a Builds on line linking the earlier pages (or Background entries) it relies on. Preliminaries — dot-product identities, basic probability, differentiation rules — are collected once in the Background appendix and referenced, so each section stays focused on its subject.

How to read the proofs

Every mathematical claim on this site gets one of three treatments:

A full proof — for named theorems and anything short enough to be self-contained (Novikoff's convergence theorem, convexity of the logistic loss).
A complete derivation — for constructions: where the sigmoid comes from, how the SVM dual is obtained, why Adam's bias correction has the form it has.
An explicit pointer — for results whose proofs are genuinely beyond the scope of a companion site, a reference to a textbook treatment in Further reading. There is no "it can be shown that" here without a link.

Proofs end with ∎. If a proof relies on a fact from the Background appendix, the fact is linked at the point of use.

Notation

Notation follows the book's conventions throughout — bold lowercase for vectors, plain italic for scalars — and is collected in the Notation appendix.

The Perceptron

In the book: Chapter 1 — The First Neuron.

Chapter 1 builds the perceptron: a unit that computes a weighted sum and thresholds it, together with a learning rule that nudges the weights on every mistake. The chapter shows geometrically that it works. This section shows why — culminating in the perceptron convergence theorem, the guarantee the book invokes at the end of the chapter.

Note	The claim it formalizes
The formal model	A perceptron's decision boundary is a hyperplane; predictions are half-space membership.
The learning rule	Each mistake-driven update provably moves the score of the offending example in the right direction.
Linear separability and XOR	AND and OR are linearly separable; XOR provably is not.
The convergence theorem	On separable data, the algorithm converges after finitely many updates — Novikoff's theorem, with proof.
Reading the bound	What the mistake bound $(R / γ)^{2}$ actually says, and what it foreshadows.

The formal model

In the book: Chapter 1, §"Intuition: AND and OR" and §"Why the Perceptron Works". Builds on: Background: the dot product.

Planned. Defines the perceptron as $h (x) = sign (w^{⊤} x + b)$ , makes precise what the book shows in pictures: the set ${x : w^{⊤} x + b = 0}$ is a hyperplane, the two prediction regions are half-spaces, $w$ is normal to the boundary, and $b$ controls its offset from the origin.

The learning rule

In the book: Chapter 1, §"Implementing a Learning Algorithm" and §"Why the Perceptron Works". Builds on: The formal model.

Planned. Formalizes the mistake-driven update $w \leftarrow w + y x, b \leftarrow b + y$ : proves the score-improvement identity the book computes (the functional margin $y (w^{⊤} x + b)$ increases by exactly $x^{⊤} x + 1$ on the triggering example), relates the book's code form $e = y - y$ to the analyzed form, and shows why constant scaling of updates cannot change the boundary found.

Linear separability and XOR

In the book: Chapter 1 (AND/OR plots); Chapter 2, §"The Limitations of the Perceptron". Builds on: The formal model.

Planned. Defines linear separability of a labeled dataset, exhibits separating hyperplanes for AND and OR, and proves that no $(w, b)$ separates XOR — the four-inequality contradiction argument, done honestly.

The convergence theorem

In the book: Chapter 1, §"Why the Perceptron Works" — "the perceptron convergence theorem states that the algorithm finds a separating boundary after a finite number of updates." This page states and proves that theorem. Builds on: The learning rule · Background: dot-product identities · Background: the Cauchy–Schwarz inequality.

The book demonstrates that each update improves the score of the example that triggered it, and warns that an update "may worsen the margin on other examples." So why does this tug-of-war end? The answer is Novikoff's theorem (1962): if the data is linearly separable, the total number of updates the perceptron can ever make is bounded by a constant that depends only on the geometry of the data — not on the number of examples, not on the dimension, and not on the order in which examples are visited.

Setup

We are given a dataset $(x_{1}, y_{1}), \dots, (x_{N}, y_{N})$ with $x_{i} \in R^{d}$ and labels $y_{i} \in {- 1, + 1}$ , and we run the perceptron rule from Chapter 1: predict with $sign (w^{⊤} x + b)$ , and on a misclassified example update

$w \leftarrow w + y x, b \leftarrow b + y .$

Absorbing the bias. The pair $(w, b)$ is awkward to carry through the analysis, and there is a standard trick to make it disappear: append a constant feature $1$ to every input. Define

$x = (x, 1) \in R^{d + 1}, w = (w, b) \in R^{d + 1} .$

Then $w^{⊤} x = w^{⊤} x + b$ , so predictions are unchanged, and the two-part update above becomes the single update $w \leftarrow w + y \tilde{x}$ : the bias update $b \leftarrow b + y$ is exactly the update of the last coordinate. From here on we work in $R^{d + 1}$ and drop the tildes: inputs are $x_{i}$ , the parameter is a single vector $w$ , and the update is $w \leftarrow w + y x$ . We start, as the book's code does, from $w_{0} = 0$ .

The two geometric quantities. The bound is stated in terms of:

the radius of the data, $R = max_{i} ∥ x_{i} ∥$ — how far any example sits from the origin;
the margin $γ$ of the best separator: linear separability means there exists some unit vector $w^{*}$ ( $∥ w^{*} ∥ = 1$ ) and some $γ > 0$ with

$y_{i} ⟨ w^{*}, x_{i} ⟩ \geq γ for every i = 1, \dots, N .$

In words: some hyperplane not only separates the classes but clears every point by at least $γ$ . (Requiring $∥ w^{*} ∥ = 1$ is what makes $γ$ a genuine distance rather than an artifact of scaling — made precise in Margin, formally, in the planned Maximum-Margin Separation section.)

Statement

Theorem (Novikoff, 1962). Run the perceptron algorithm, starting from $w_{0} = 0$ , on any sequence of examples drawn from the dataset (in any order, with any repetitions). If the data is linearly separable with margin $γ > 0$ and radius $R$ , then the algorithm makes at most

$(\frac{R}{γ})^{2}$

updates. In particular, after finitely many mistakes the weight vector separates the data perfectly and never changes again.

Proof

Let $w_{k}$ denote the weight vector after the $k$ -th update. The proof tracks one quantity from two sides: the alignment $⟨ w_{k}, w^{*} ⟩$ between the learned weights and the perfect separator. Each mistake forces this alignment up by a fixed amount, while the length of $w_{k}$ can only grow slowly. Since alignment cannot outrun length (Cauchy–Schwarz), mistakes must stop.

Step 1 — each update gains $γ$ of alignment. Suppose the $k$ -th update is triggered by the example $(x, y)$ , so $w_{k} = w_{k - 1} + y x$ . By linearity of the dot product,

$⟨ w_{k}, w^{*} ⟩ = ⟨ w_{k - 1}, w^{*} ⟩ + y ⟨ x, w^{*} ⟩ \geq ⟨ w_{k - 1}, w^{*} ⟩ + γ,$

where the inequality is exactly the margin condition $y ⟨ w^{*}, x ⟩ \geq γ$ . Starting from $⟨ w_{0}, w^{*} ⟩ = 0$ and applying this $k$ times,

$⟨ w_{k}, w^{*} ⟩ \geq kγ . (1)$

Step 2 — each update grows the length by at most $R^{2}$ . For the same update, expand the squared norm (Background: norms):

$∥ w_{k} ∥^{2} = ∥ w_{k - 1} + y x ∥^{2} = ∥ w_{k - 1} ∥^{2} + 2 y ⟨ w_{k - 1}, x ⟩ + y^{2} ∥ x ∥^{2} .$

Now use the one fact that makes the whole proof work: the update only happens because the example was misclassified, which means $y ⟨ w_{k - 1}, x ⟩ \leq 0$ . The middle term is not just bounded — it helps us. Together with $y^{2} = 1$ and $∥ x ∥ \leq R$ ,

$∥ w_{k} ∥^{2} \leq ∥ w_{k - 1} ∥^{2} + R^{2},$

and therefore, again starting from $w_{0} = 0$ ,

$∥ w_{k} ∥^{2} \leq k R^{2} . (2)$

Step 3 — the two bounds collide. By the Cauchy–Schwarz inequality and $∥ w^{*} ∥ = 1$ ,

$⟨ w_{k}, w^{*} ⟩ \leq ∥ w_{k} ∥ ∥ w^{*} ∥ = ∥ w_{k} ∥ .$

Chaining (1), this, and (2):

$kγ \leq (1) ⟨ w_{k}, w^{*} ⟩ \leq ∥ w_{k} ∥ \leq (2) k R .$

Reading off the ends, $kγ \leq k R$ , and dividing by $k γ$ (positive for any $k \geq 1$ ) gives

$k \leq \frac{R}{γ} ⟺ k \leq (\frac{R}{γ})^{2} .$

So the number of updates can never exceed $(R / γ)^{2}$ . Once the algorithm completes a full pass with no mistake — which must happen, since passes containing a mistake are limited — the weights separate every example and no future pass changes them. ∎

Remarks

Where each hypothesis was used. Separability with margin $γ$ powered Step 1; misclassification-only updates powered Step 2 (it is the reason the cross term is $\leq 0$ ); $w_{0} = 0$ made both accumulations start at zero. Drop any one and the proof — and the theorem — fails.

What the theorem does not say. It does not say the perceptron finds the best boundary, only a separating one; the book's "tug-of-war" ends, but possibly at a line that barely clears some points. It also says nothing when the data is not separable — the XOR case — where the algorithm cycles forever. Both gaps are picked up in Reading the bound and resolved properly in Maximum-Margin Separation (planned).

The bound is dimension-free. Neither $d$ nor $N$ appears. This is worth pausing on: a million points in a million dimensions cost no more updates than four points in the plane, so long as the geometry ( $R / γ$ ) is the same. This is the first appearance of a theme that returns with kernels in Kernels and Feature Spaces (planned).

Going further

A. Novikoff, On convergence proofs for perceptrons, Symposium on the Mathematical Theory of Automata, 1962 — the original.
M. Minsky & S. Papert, Perceptrons, MIT Press, 1969 — the book-length study of what perceptrons can and cannot represent.
Freund & Schapire, Large margin classification using the perceptron algorithm, Machine Learning 37, 1999 — what can still be said when the data is not separable.

Reading the bound

In the book: Chapter 1, §"Why the Perceptron Works" (closing); foreshadows Chapter 2. Builds on: The convergence theorem.

Planned. Interprets the mistake bound $(R / γ)^{2}$ : the number of updates does not depend on the number of examples or the dimension, only on the geometry — how spread out the data is ( $R$ ) versus how wide the best separating corridor is ( $γ$ ). Discusses what happens when the data is not separable, and why the appearance of the margin $γ$ in the bound is the mathematical seed of Chapter 2's search for the sharpest line.

Background

Compact preliminaries the main sections rely on. This is a reference card, not a course: each entry states facts and proves the short ones, so that no section ever has to interrupt its subject to re-teach them. Entries are added when a section first needs them.

The dot product

For $u, v \in R^{d}$ , the dot product (inner product) is

$⟨ u, v ⟩ = u^{⊤} v = j = 1 \sum d u_{j} v_{j},$

and the Euclidean norm is $∥ u ∥ = ⟨ u, u ⟩$ .

Facts (each immediate from the definition):

Symmetry: $⟨ u, v ⟩ = ⟨ v, u ⟩$ .
Linearity in each argument: $⟨ a u + w, v ⟩ = a ⟨ u, v ⟩ + ⟨ w, v ⟩$ for any scalar $a$ .
Positivity: $⟨ u, u ⟩ = ∥ u ∥^{2} \geq 0$ , with equality iff $u = 0$ .
Expansion of a sum (used constantly; it is the law of cosines in disguise):

$∥ u + v ∥^{2} = ∥ u ∥^{2} + 2 ⟨ u, v ⟩ + ∥ v ∥^{2} .$

Proof of 4. Expand $⟨ u + v, u + v ⟩$ using linearity in each argument and symmetry: $⟨ u, u ⟩ + ⟨ u, v ⟩ + ⟨ v, u ⟩ + ⟨ v, v ⟩ = ∥ u ∥^{2} + 2 ⟨ u, v ⟩ + ∥ v ∥^{2}$ . ∎

Geometrically, $⟨ u, v ⟩ = ∥ u ∥ ∥ v ∥ cos θ$ where $θ$ is the angle between the vectors — the dot product measures alignment. This reading is justified by the next entry, which shows the ratio $⟨ u, v ⟩ / (∥ u ∥ ∥ v ∥)$ always lies in $[- 1, 1]$ .

The Cauchy-Schwarz inequality

Theorem. For all $u, v \in R^{d}$ ,

$∣ ⟨ u, v ⟩ ∣ \leq ∥ u ∥ ∥ v ∥,$

with equality iff one vector is a scalar multiple of the other.

Proof. If $v = 0$ both sides are zero. Otherwise, for every $t \in R$ , positivity and the expansion identity give

$0 \leq ∥ u - t v ∥^{2} = ∥ u ∥^{2} - 2 t ⟨ u, v ⟩ + t^{2} ∥ v ∥^{2} .$

The right-hand side is a quadratic in $t$ that is never negative, so its discriminant is at most zero:

$4 ⟨ u, v ⟩^{2} - 4 ∥ u ∥^{2} ∥ v ∥^{2} \leq 0,$

which is the claim after rearranging and taking square roots. Equality of the discriminant means the quadratic has a real root $t_{0}$ , i.e. $∥ u - t_{0} v ∥ = 0$ , i.e. $u = t_{0} v$ . ∎

Used in: the perceptron convergence theorem (Step 3 — alignment cannot exceed length).

Calculus

Planned. Partial derivatives, the gradient, the chain rule, and first-order Taylor approximation — added when The logistic-loss gradient and Gradient descent land.

Probability

Planned. Random variables, expectation and variance, independence, the Bernoulli and Gaussian distributions, and Bayes' rule — added when The data-generating process and Maximum likelihood estimation land.

Convexity and Lagrange duality

Planned. Convex sets and functions, Lagrange multipliers, and the duality facts needed by Duality and the kernel SVM — added before that note is written.

Notation

Notation on this site follows the book's conventions. This page is the single source of truth; any page that deviates from it is a bug.

Symbol	Meaning
$x, y, a, γ$	Scalars — plain italic lowercase.
$x, w$	Vectors — bold lowercase. Components are scalars with subscripts: $x = (x_{1}, \dots, x_{d})$ .
$X, K$	Matrices — bold uppercase.
$w^{⊤} x$ , $⟨ w, x ⟩$	The dot product — both forms appear; they mean the same thing. The book prefers $w^{⊤} x$ ; proofs here sometimes use $⟨ \cdot, \cdot ⟩$ when it reads better.
$∥ x ∥$	Euclidean norm, $x^{⊤} x$ .
$y \in {- 1, + 1}$	Class labels in the perceptron/SVM chapters (1–5).
$y \in {0, 1}$	Class labels in the probabilistic chapters (6 onward), matching the Bernoulli convention.
$y$	A model's prediction; more generally, a hat marks an estimate.
$w, b$	Weights and bias of a linear model; $\tilde{w} = (w, b)$ when the bias is absorbed.
$N$ , $d$	Number of training examples; input dimension.
$D$	The data-generating distribution.
$E [\cdot]$ , $P (\cdot)$	Expectation; probability.
$ℓ$ , $R (h)$ , $R (h)$	Loss function; true risk; empirical risk.
$σ (z)$	The sigmoid $1/ (1 + e^{- z})$ .
$η$	Learning rate (step size).
$φ$ , $k (x, x^{'})$	Feature map; kernel function.
$\nabla f$	Gradient of $f$ .
∎	End of proof.

One deliberate difference from the book's Introduction. The book's front matter writes vectors as bold uppercase ( $X$ ); the chapters themselves, and this site, use bold lowercase ( $x$ ) for vectors and reserve bold uppercase for matrices — the standard convention in the machine-learning literature.

Keyboard shortcuts

The Mathematics of Rust for Machine Learning