Learning

Learning from data is used in situations where we don’t have an analytic solution, but we do have data that we can use to construct an empirical solution.

An example is the Netflix Prize recommendation model which is typically described as a latent factor matrix factorization model trained on observed user–item ratings.

• Viewer Vector ($v$): Represents the user’s preferences.

  • Example Factors: Likes comedy? Likes action? Prefers blockbusters? Likes Tom Cruise?

• Movie Vector ($m$): Represents the movie’s attributes.

  • Example Factors: Comedy content, Action content, Blockbuster status, Is Tom Cruise in it?

  

  $\text{Predicted Rating}={\sum }_{i=1}^n(v_i\cdot m_i)$ The power of learning from data is that this entire process can be automated, without any need for analyzing movie content or viewer taste. To do so, the learning algorithm ‘reverse-engineers’ these factors based solely on previous ratings. It starts with random factors, then tunes these factors to make them more and more aligned with how viewers have rated movies before, until they are ultimately able to predict how viewers rate movies in general. In practice, these factors are not human-interpretable features (like “comedy” or “action”), but latent patterns automatically learned from data, and the model often includes additional bias terms to improve prediction accuracy. Latent factors are patterns that are statistically real but often incomprehensible to humans. We might call Factor #1 “Action,” but to the computer, it is just “Factor 1”.

Neural recommender systems extend matrix factorization by learning user and item embeddings and replacing the dot-product similarity with a nonlinear function (e.g., a neural network).

---

Components of learning A learning problem can be defined using four main components: input space, target function, dataset, and hypothesis set.

• $x$ (Input): The specific data used to make a decision (e.g., an individual customer’s financial information).
• $\mathcal{X}$ (Input Space): The set of all possible inputs.
• $\mathcal{Y}$ (Output Space): The set of all possible outputs (e.g., {Yes, No} for credit approval).
• $f:\mathcal{X}\to \mathcal{Y}$ (Target Function): The unknown, ideal, perfect formula that maps every input to the correct output. This is what we are trying to learn.
• $\mathcal{D}$ (Data Set): A collection of historical input-output examples, denoted as $(x_1,y_1),\dots ,(x_N,y_N)$.
• $\mathcal{H}$ (Hypothesis Set): The set of all candidate formulas the algorithm is allowed to consider (e.g., the set of all possible linear equations).
• $g:\mathcal{X}\to \mathcal{Y}$ (Final Hypothesis): The single, specific formula chosen by the learning algorithm from $\mathcal{H}$. The Learning Algorithm analyzes the Data Set ($\mathcal{D}$) to select the best possible formula $g$ from the Hypothesis Set ($\mathcal{H}$), with the goal that $g\approx f$

There is a target to be learned. It is unknown to us. We have a set of examples generated by the target. The learning algorithm uses these examples to look for a hypothesis that approximates the target.

The hypothesis set and learning algorithm are referred to informally as the learning model.

---

A Simple Learning Model : The Perceptron Model (Linear Hypothesis)

The perceptron models binary decisions by assigning weights to input features, computing a weighted sum plus bias, and classifying the result using a sign function to separate inputs into two classes (binary classification). Mathematical Formulation :

• Input Space ($\mathcal{X}$): A $d$-dimensional vector $x\in {\mathbb{R}}^d$. Each coordinate ($x_1,x_2,\dots ,x_d$) represents a specific data field like salary, years in residence, or outstanding debt.
• Output Space ($\mathcal{Y}$): A binary set $\{+1,-1\}$.
  • $+1$ = Approve Credit
  • $-1$ = Deny Credit
• The Hypothesis ($h$): The specific formula used to make the decision. It is defined as: $h(x)=\text{sign}\left({\sum }_{i=1}^d{w}_i{x}_i+b\right)$ Weights ($w_1,\dots ,w_d$): These determine the importance and direction of each input. Bias ($b$): This represents the threshold. larger bias → stricter approval boundary
  smaller bias → more lenient approval boundary

The perceptron is a linear classification model that learns a hyperplane:
$w^{T}x+b=0$

which separates the input space into:

• $+1$ decision region
• $-1$ decision region

A perceptron can operate in:

• 2D
• 3D
• 100D
• 10,000D For:
• $d=2$ → separating line
• $d=3$ → separating plane
• higher $d$ → hyperplane

Example : Image Classification
Input:
a $28\times 28$ grayscale image
Flattened into $784$ features, $x\in {\mathbb{R}}^{784}$

Output:  
	"cat" vs "not cat"  

Perceptron = hypothesis set $H$
Each $h\in H$ = one specific linear classifier
Learning algorithm = picks the best $h$

To simplify the perceptron notation, the bias term is merged into the weight vector. The perceptron hypothesis is: $h(x)=\text{sign}(w^{T}x+b)$ Define: $w_0=b$ and extend the weight vector: $w=[w_0,w_1,\dots ,w_d{]}^T$ Similarly, extend the input vector by adding a constant feature: $x=[x_0,x_1,\dots ,x_d{]}^T$ with $x_0=1$. This allows the bias term to be absorbed into the dot product: $w_0{x}_0=b\cdot 1=b$ So the bias becomes just another weighted feature.

Now: $w^{T}x={\sum }_{i=0}^d{w}_i{x}_i$ $w^{T}x=b+w_1{x}_1+w_2{x}_2+\cdots +w_d{x}_d$

The perceptron can now be written compactly as:

$h(x)=\text{sign}(w^{T}x)$

By augmenting the input vector with a constant feature $x_0=1$, the bias term becomes part of the weight vector, allowing the perceptron to be written as a single dot product.

The bias term in the perceptron can be absorbed into the weight vector by introducing an additional constant input feature, giving the compact form:

$h(x)=\text{sign}(w^{T}x)$

Perceptron Learning Algorithm (PLA) :

An iterative method used to learn the weight vector $w$ from data.

Assumption: Linearly Separable Data

We assume the dataset is linearly separable, meaning:

There exists a weight vector $w$ such that all training examples are classified correctly.

$h(x_n)=y_n\forall n$

Start with an initial weight vector:

$w(0)=0$ (or any arbitrary initialization)

At each iteration $t$:

• Current weight vector: $w(t)$
• Select a misclassified example $(x(t),y(t))$

A misclassified point satisfies: $y(t)\ne \text{sign}(w(t{)}^{T}x(t))$

The perceptron updates weights using: $w(t+1)=w(t)+y(t)x(t)$

Intuition Behind the Update

• moves $w$ in the direction of the correct classification

• increases alignment with correctly labeled examples

• decreases error on the chosen misclassified point

• If $y(t)=+1$ → move $w$ toward $x(t)$

• If $y(t)=-1$ → move $w$ away from $x(t)$
  At each step:

• only one example is corrected

• other examples may temporarily become misclassified again

• rotates the hyperplane slightly in a direction that fixes the current mistake without needing global optimization However:

The process continues until no misclassified examples remain

Perceptron learning primarily rotates the decision boundary by updating the weight vector $w$, while the bias $b$ controls translation of the hyperplane.

The hyperplane is defined by: $w^{T}x+b=0$ So:

• changing w → rotates the hyperplane
• changing b → shifts it

In the classic perceptron update, the dominant effect is rotation.

---

The multiplication by $y_t$ is used to unify the two misclassification cases into a single condition with the same mathematical form.

We want to check whether a point is misclassified.

The perceptron predicts using: $\text{sign}(w^T{x}_t)$

So:

• If $w^T{x}_t>0\Rightarrow +1$ → positive half-space
• If $w^T{x}_t<0\Rightarrow -1$ → negative half-space

Misclassification happens in two cases: Case A: true label is +1, but prediction is negative $y_t=+1,w^T{x}_t\le 0$ Case B: true label is -1, but prediction is positive $y_t=-1,w^T{x}_t\ge 0$

We must check two separate conditions:

• $y_t=+1\wedge w^T{x}_t\le 0$
• $y_t=-1\wedge w^T{x}_t\ge 0$ This is cumbersome for analysis and algorithm design.

We define a unified expression: $y_t(w^T{x}_t)$

Case A: $y_t=+1$ $y_t(w^T{x}_t)=w^T{x}_t$ Misclassification condition: $w^T{x}_t\le 0$ So : $y_t(w^T{x}_t)\le 0$

Case B: $y_t=-1$ $y_t(w^T{x}_t)=-(w^T{x}_t)$ Misclassification condition: $w^T{x}_t\ge 0$ So again: $y_t(w^T{x}_t)\le 0$

Both cases collapse into a single condition: $y_t(w^T{x}_t)\le 0$

Multiplying by $y_t$:

• flips all negatively labeled points
  • all +1 points remain in place
  • all −1 points are mirrored across the origin

After transformation: Every correctly classified point must lie on the same side of the hyperplane

• correct classification means: $y_t(w^T{x}_t)>0$

So all points are evaluated against the same rule: “positive alignment” (everything should land in the positive half-space)

This is useful for learning as this allows a single update rule instead of case-based logic: $w\leftarrow w+y_t{x}_t$ Effect:

• if $y_t=+1$ → move $w$ toward $x_t$
• if $y_t=-1$ → move $w$ away from $x_t$

---

The weight vector $w$ is not the hyperplane itself.

Instead:

$w$ is the normal vector to the hyperplane.

That means:

• $w$ is perpendicular (orthogonal) to the decision boundary
• $w$ determines which side is classified as positive
• the hyperplane is defined relative to $w$

For any two points $x_a,x_b$ lying on the hyperplane:

$w^T{x}_a+b=0$

$w^T{x}_b+b=0$

Subtracting:

$w^T(x_a-x_b)=0$

Thus:

$w$ is perpendicular to every direction lying within the hyperplane. The weight vector defines the orientation and positive direction of the classifier, while the hyperplane itself is the set of points orthogonal to that vector.

The Weight Vector Lies in the Positive Half-Space The hyperplane $w^{T}x=0$ splits space into two regions: Positive half-space: $w^{T}x>0$ Negative half-space: $w^{T}x<0$ The hyperplane equation at $x=w$

		$w^T w = \|w\|^2$
	
		$w^T w > 0$

So the weight vector (w) lies inside the positive half-space defined by the hyperplane. The vector $w$:

• points toward the positive region
• acts as the normal vector to the hyperplane
• defines the direction of increasing score The sign of $w^{T}x$ measures alignment with the weight vector:
• positive dot product → same general direction as $w$
• negative dot product → opposite direction

---

Each perceptron update increases the signed margin of the misclassified point by a strictly positive amount, guaranteeing steady progress toward correct classification (correct side of the decision boundary)

To classify a point correctly, the prediction must agree with the true label. This is captured by requiring:

$y(t)w^{T}x(t)>0$

A point is misclassified when:

$y(t)w^T(t)x(t)<0$

$y(t)w^T(t+1)x(t)>y(t)w^T(t)x(t)$

Proof:

$w(t+1)=w(t)+y(t)x(t)$

$$$y(t)w^T(t+1)x(t) = y(t) \left[ w(t) + y(t)x(t) \right]^T x(t)y(t) \left[ w^T(t) + y(t)x^T(t) \right] x(t)y(t)w^T(t)x(t) + y(t)y(t)x^T(t)x(t)$$

• Since $y(t)$ is either $+1$ or $-1$, its square is always exactly 1.
• The term $x^T(t)x(t)$ is the dot product of a vector with itself, which is equal to its squared length, $\Vert x(t){\Vert }^2$. Assuming the data point is not the origin (a zero vector), this value is strictly positive ($>0$). $y(t)w^T(t+1)x(t)=y(t)w^T(t)x(t)+\Vert x(t){\Vert }^2$ $y(t)w^T(t+1)x(t)>y(t)w^T(t)x(t)$

The score strictly increases after each update.

---

Geometric View of the Perceptron Problem

Each training example imposes a geometric constraint on the weight vector $w$.

For a labeled example $(x_i,y_i)$, correct classification requires:

$y_i{w}^T{x}_i>0$

This can be rewritten as a linear constraint on $w$ (Fix $x_i$, treat w as variable):

$w^T(y_i{x}_i)>0$

The inequality:

$w^T(y_i{x}_i)>0$

defines a half-space in weight space (a half-space of all valid classifiers)** .

We denote it as:

$H_i=\{w:w^T(y_i{x}_i)>0\}$

So each training example restricts $w$ to lie in a convex region.

For a dataset of $N$ examples, we require:

$w\in {\bigcap }_{i=1}^N{H}_i$

This is:

• The set of all perfect classifiers

• $w$ must satisfy all constraints simultaneously

• it must lie in the intersection of all half-spaces

• Each $H_i$ is convex (a half-space is always convex)

• The intersection of convex sets is also convex

The feasible set of solutions is a convex region in weight space

Training becomes:

find a point $w$ inside the intersection of all half-spaces

The perceptron update:

• starts with some $w$
• moves it whenever a constraint is violated
  • if w violates one constraint
  • push w toward satisfying that constraint

The perceptron learning problem is equivalent to finding a point in the intersection of convex half-spaces defined by the training data.

Each training example defines a convex half-space constraint on $w$, and learning reduces to finding a point in the intersection of all such half-spaces.

Perceptron learning is iterative navigation through intersections of convex half-spaces in parameter space, not data space.

---

Why the Perceptron Update Direction is $x$?

Consider the linear objective:

$f(w)=w^{T}x$

where:

• $x$ is fixed
• $w$ is the variable being optimized

We want to determine:

In which direction should we move $w$ to increase $f(w)$ as quickly as possible?

The answer is given by the gradient.

Taking the gradient with respect to $w$:

${\nabla }_w(w^{T}x)=x$

So:

the direction of steepest increase is exactly the vector $x$

$\Delta w\propto x$

If the update is constrained to unit length:

$\Vert \Delta w\Vert =1$

then the optimal direction becomes:

$\Delta w=\frac{x}{\Vert x\Vert }$

which is the normalized version of $x$.

The objective change after a small step $\Delta w$ is:

$(w+\Delta w{)}^{T}x-w^{T}x=\Delta w^{T}x$

So maximizing improvement means maximizing:

$\Delta w^{T}x$

Cauchy–Schwarz Inequality

We use:

$|\Delta w^{T}x|\le \Vert \Delta w\Vert \Vert x\Vert$

If $\Vert \Delta w\Vert =1$, then:

$\Delta w^{T}x\le \Vert x\Vert$

The maximum possible increase is therefore:

$\Vert x\Vert$

Equality in Cauchy–Schwarz occurs only when the vectors are collinear:

$\Delta w=\lambda x$

Under the unit norm constraint:

$\Delta w=\frac{x}{\Vert x\Vert }$

The perceptron update:

$w\leftarrow w+y_t{x}_t$

uses:

• $x_t$ as the optimal correction direction
• $y_t$ to determine whether to move toward or away from the point

Thus:

• positive examples pull $w$ toward themselves
• negative examples push $w$ away

The perceptron update follows the direction that maximally increases the classification score for the current example.

Lagrange Multipliers: Optimal Update Direction

We want to maximize the directional improvement of the objective:

${\max }_{\Delta w}\Delta w^{T}x\text{s.t. }\Delta w^T\Delta w=1$

• Objective: maximize $\Delta w^{T}x$
• Constraint: unit-length update
  $\Vert \Delta w{\Vert }^2=\Delta w^T\Delta w=1$

$L(\Delta w,\lambda )=\Delta w^{T}x-\lambda (\Delta w^T\Delta w-1)$

The Lagrangian says:

“Maximize the objective, BUT punish solutions that break the constraint.”

Differentiate with respect to $\Delta w$:

${\nabla }_{\Delta w}L=x-2\lambda \Delta w=0$

$x=2\lambda \Delta w$

$\Delta w=\frac{1}{2\lambda }x$

Apply unit norm constraint:

$\Vert \Delta w\Vert =1$

Substitute $\Delta w$:

$\Vert \frac{1}{2\lambda }x\Vert =1$

So:

$\frac{1}{2\lambda }\Vert x\Vert =1$

$\frac{\Vert x\Vert }{2\lambda }=1$

$2\lambda =\Vert x\Vert$

$\lambda =\frac{\Vert x\Vert }{2}$

Substitute back into $\Delta w$:

$\Delta w=\frac{1}{2\lambda }x=\frac{1}{\Vert x\Vert }x$

---

If the data is linearly separable:

• PLA is guaranteed to converge
• It will find a valid $w$ in a finite number of steps This result is known as the Perceptron Convergence Theorem.

Perceptron Convergence Theorem :

We are given a dataset $(x_i,y_i)$ where:

• $x_i\in {\mathbb{R}}^d$
• $y_i\in \{-1,+1\}$

We assume linear separability, meaning:

There exists a vector $w^{\ast }$ such that: $y_i(w^{\ast T}{x}_i)>0\forall i$

Define:

• $R={\max }_i\Vert x_i\Vert$
• $\gamma ={\min }_i{y}_i(w^{\ast T}{x}_i)$ (after normalizing $w^{\ast }$ so $\Vert w^{\ast }\Vert =1$)

So:

• $R$ = maximum data norm (The largest length (magnitude) among all training points)
• $\gamma$ = geometric margin (minimum confidence) = $Marg(T)$ (The Margin) : Represents the size of the gap between the classes. A larger gap makes it easier and faster for the line to find its place

At each mistake on $(x_t,y_t)$:

$w_{t+1}=w_t+y_t{x}_t$

Initialize:

$w_0=0$

We prove two inequalities: (A) Progress toward optimal direction (B) Growth of norm is controlled Combining them gives the mistake bound.

Step 1 - Consider dot product with $w^{\ast }$ (alignment with true solution):

$w_{t+1}^T{w}^{\ast }=(w_t+y_t{x}_t{)}^T{w}^{\ast }$

$w_t^T{w}^{\ast }+y_t{x}_t^T{w}^{\ast }$

So each mistake increases projection by:

$y_t(w^{\ast T}{x}_t)$

By separability:

$y_t(w^{\ast T}{x}_t)\ge \gamma$

So:

$w_{t+1}^T{w}^{\ast }\ge w_t^T{w}^{\ast }+\gamma$

So every mistake pushes $w_t$​ **closer in direction to $w^{\ast }$.

After $M$ mistakes:

$w_M^T{w}^{\ast }\ge M\gamma$

Step 2 - Bound growth of $\Vert w\Vert$

Compute norm growth:

$\Vert w_{t+1}{\Vert }^2=\Vert w_t+y_t{x}_t{\Vert }^2$ = $\Vert w_t{\Vert }^2+2y_t{w}_t^T{x}_t+\Vert x_t{\Vert }^2$

Updates happen only on mistakes, for a mistake:

$y_t{w}_t^T{x}_t\le 0$

So:

$\Vert w_{t+1}{\Vert }^2\le \Vert w_t{\Vert }^2+\Vert x_t{\Vert }^2$

Using $\Vert x_t\Vert \le R$:

$\Vert w_{t+1}{\Vert }^2\le \Vert w_t{\Vert }^2+R^2$

After $M$ mistakes:

$\Vert w_M{\Vert }^2\le M{R}^2$

From Cauchy–Schwarz:

$w_M^T{w}^{\ast }\le \Vert w_M\Vert \Vert w^{\ast }\Vert$

Assume $\Vert w^{\ast }\Vert =1$:

$w_M^T{w}^{\ast }\le \Vert w_M\Vert$

Using bounds:

$M\gamma \le \Vert w_M\Vert \le \sqrt{M}R$

So:

$M\gamma \le \sqrt{M}R$

$\sqrt{M}\gamma \le R$

$M\le \frac{R^2}{{\gamma }^2}$

The number of perceptron mistakes is bounded by: $M\le \frac{R^2}{{\gamma }^2}$

Each update:

• increases alignment with $w^{\ast }$ by at least $\gamma$
• increases weight norm only by at most $R^2$

So:

alignment grows faster than destructive “noise” in magnitude

This forces convergence.

• Larger margin $\gamma$ → faster convergence
• Larger data norm $R$ → slower convergence → Larger data vectors push the weight vector around with massive, dramatic steps during an update
• Well-separated data → very few updates

If the data is linearly separable with margin $\gamma$, the perceptron makes at most $\frac{R^2}{{\gamma }^2}$ mistakes before converging.

Even though the hypothesis space is infinite, PLA finds a correct solution using only simple local updates based on misclassified points. So convergence is guaranteed in finite steps.

The perceptron converges because its updates increase alignment with the true separator linearly while controlling norm growth sublinearly, forcing a finite bound on mistakes.

---

The Mathematical Guarantee : Why $w^{\ast }$ Exists (Maximum Margin Separator)

$Marg(T):={\sup }_{||w||=1}marg(w,T)$

• $T$ (The Dataset): This is your entire collection of training data points.
• $w$ (The Normal Vector / Boundary): This vector defines the orientation of a specific separating hyperplane (the decision line).
• $||w||=1$: This means we restrict our search only to unit vectors (vectors with a length of exactly 1). This acts as a geometric equalizer so we can calculate true, unscaled physical distances from the line to the data points.
• $marg(w,T)$: This is the margin of a single, specific boundary line. It is the distance from that line to the absolute closest data point in the set.
• $\sup$ (Supremum): This is a mathematical term for the “least upper bound,” which practically means the maximum possible value

If your data points are linearly separable, you can draw infinitely many different lines that successfully split the positive data points from the negative ones.

• If you draw a line that sits incredibly close to a cluster of points, its $marg(w,T)$ is going to be very small. This is a risky boundary because a tiny bit of noise in new test data could easily cause a misclassification. If you carefully adjust the angle and position of the line so it sits perfectly in the middle of the two classes, you push it as far away from the data points as possible.
• $Marg(T)$ represents the width of that widest possible street. It evaluates every single valid separating line ($||w||=1$) , measures the gap to its closest point , and picks the configuration that maximizes that gap

Let $T\subset {\mathbb{R}}^n$ be finite, linearly separable. Once we establish that separating lines do exist, we know there are infinitely many of them. This is where the compactness of $T$ and the continuity of the margin function come into play to guarantee the existence of $w^{\ast }$

The Extreme Value Theorem from calculus states that if you have a continuous function mapping onto a compact set (a space that is closed and has strict boundaries), the function must hit an absolute maximum value at some point within that space.

Margin as an objective function : Define the margin of a separator $w$ as a function: $\gamma (w)$ This measures:

how far the closest point is from the decision boundary

So the learning goal becomes:

${\max }_{w\in T}\gamma (w)$

where:

• $T$ = set of all valid separating weight vectors

The set $T$ has two important properties:

• Closed: boundary solutions are included
• Bounded (after normalization constraints)

So $T$ is a compact set in ${\mathbb{R}}^n$

The margin function $\gamma (w)$ is continuous in $w$ because:

• it depends on dot products $w^{T}x$
• dot products are continuous functions

Extreme Value Theorem

If a function is continuous on a compact set, it must attain both:

• a maximum
• a minimum

Since:

• $T$ is compact
• $\gamma (w)$ is continuous

then:

$\exists w^{\ast }\in T\text{such that}\gamma (w^{\ast })={\max }_{w\in T}\gamma (w)$

Without compactness, we could have:

• sequences of separators improving margin
• but no actual “best” solution attained

i.e. only a supremum, not a maximum

Compactness prevents this pathology.

The vector $w^{\ast }$ is:

• a valid separating hyperplane
• that achieves the largest possible margin
• among all infinitely many separators

So it is not just “good” — it is optimal.

Among all separating hyperplanes:

• some barely separate the data
• some separate with large safety gaps
• one achieves the maximum possible gap

---

The Perceptron is Lazy The stopping condition for the perceptron algorithm is it terminates the very instant it finds any weight vector $w^{(t)}$ that puts a positive gap between the boundary and every data point ($w^{(t)}\cdot x>0$)

The mathematical existence of $w^{\ast }$ is a property of the dataset itself, but finding it is not a guarantee of the perceptron algorithm.

The perceptron learning algorithm updates its weights incrementally whenever a training example is misclassified:

$w_{t+1}=w_t+y_t{x}_t$

Because the updates depend on the current state of the weights, the final learned hyperplane depends strongly on:

• the initial weight vector
• the order in which training examples are presented

Different starting values $w_0$ cause:

• different update trajectories
• different sequences of mistakes
• different final separators Even on the same dataset.

The perceptron is an online algorithm:

• it processes one example at a time
• each update changes future behavior

Therefore changing example order changes the path through parameter space which changes the final solution

For linearly separable data:

• there are usually infinitely many separating hyperplanes

The perceptron does not optimize:

• maximum margin
• minimum norm
• global loss function

It only enforces:

$y_i(w^T{x}_i)>0$

So once it finds any valid separator, it stops.

The perceptron converges to:

the first separating hyperplane consistent with the training data and update trajectory

The perceptron is a feasibility algorithm, not an optimization algorithm.

• The basic perceptron stops adjusting the moment it finds any line that separates the data, even if it’s a terrible, close-shave line. This formula forms the mathematical foundation for Support Vector Machines, which are explicitly engineered to search for and calculate the precise $w$ that achieves this optimal $Marg(T)$.

---

Computational Optimization & Learning Theory

When adjusting the weight parameters $w$ to fit empirical observations, learning theory distinguishes between two primary approximation goals:

A. Interpolation (Strict Functional Matching)

The interpolation objective forces the network output function to pass exactly through every observed point within the finite training set:

$\forall i\in \{1,\dots ,T\},f_w(x_i)=y_i$

• Overfitting: Forcing an exact zero-error fit on empirical training data typically causes the network to absorb localized data noise. This destabilizes the underlying decision boundary, leading to poor generalization behavior when evaluated on out-of-sample data.

In the standard Perceptron, we are performing discrete, rule-based updates driven entirely by local misclassifications. Because the feedback is strictly binary (correct vs. incorrect), there is no continuous “landscape” or smooth hill to walk down. The vector simply takes sharp, discrete jumps in direction until all errors vanish.

B. Regression (Global Objective Minimization)

The regression objective prioritizes tracking the global trend line or underlying data-generating distribution rather than forcing local convergence on noisy individual coordinates.

To systematically implement this approach, we define a continuous, differentiable global performance metric known as the Energy Function (loss or cost function):

$E(w):={\sum }_{i=1}^T{\left(f_w(x_i)-y_i\right)}^2$

• $\left(f_w(x_i)-y_i\right)$: Computes the localized directional error (the vertical distance) between the model’s current parametric estimate and the empirical datum. Instead of a binary “yes/no,” this function outputs a continuous scalar value. It tells the system exactly how far off the predictions are. If a prediction is slightly wrong, the error is small; if it is wildly wrong, the error is massive.
• All evaluated error parameters yield strictly non-negative values, preventing opposing localized errors from mathematically canceling each other out. The quadratic scaling heavily penalizes severe misclassifications or extreme data outliers. The quadratic term also creates a continuously differentiable curve, we can take the derivative (gradient) of the error surface
• Consolidates all isolated sample variances into a single, comprehensive global performance scalar across the entire dataset $T$.

The overarching goal of network training is to minimize the total accumulated error across the global weight space:

${\min }_{w\in {\mathbb{R}}^m}E(w)$

When you shift to an energy function approach, you are essentially trying to navigate a massive, multi-dimensional terrain of mathematical data to find the lowest possible point (the global minimum). Instead of taking discrete jumps by adding the raw data vector $x_i$, optimization algorithms use gradient descent to take small, precise steps down the slope of the error landscape

Transitioning from discrete updates to global functional minimization requires addressing several core mathematical challenges:

• Mathematical Topology: Determining the exact algebraic behavior and geometric profile of the optimization surface $E(w)$. When you map out every possible weight configuration ($w$) against its corresponding error score $E(w)$, you create a geometric landscape called an optimization surface or loss landscape.
  • If the landscape is convex (shaped like a perfect, smooth bowl), optimization is mathematically straightforward. Any local minimum you find is guaranteed to be the absolute lowest point (the global minimum), meaning your gradient descent algorithm can easily slide straight down to the perfect solution.
  • For modern neural networks, the landscape is non-convex—it is a highly chaotic terrain filled with random hills, deep valleys, saddle points, and thousands of deceptive local minima. If your algorithm gets stuck in a shallow local valley where the slope becomes flat ($\nabla E(w)=0$), it will freeze, mistakenly thinking it found the best solution when a much better one exists further away.
• Feasibility and Boundary Constraints: Formulating strict local or global constraints on allowable weight parameters $w$ to ensure convergence and structural stability.
  • In a basic setup, you might let the computer choose any real number it wants for the weights ($w\in {\mathbb{R}}^m$). This is called unconstrained optimization. However, in practical engineering, letting weights roam completely free often leads to exploding values, mathematical instability, or severe overfitting.
  • To prevent this, we introduce constraints to restrict the search to a specific, safe region of the landscape known as the feasible set ($M$).
  • You might place a strict mathematical ceiling on the weights, such as enforcing that the length of the weight vector cannot exceed a certain limit ($\Vert w{\Vert }^2\le C$) (Formulating Boundaries)
  • When you introduce these strict boundaries, simple gradient descent is no longer enough because the algorithm might try to step completely out of bounds (Lagrange Multipliers and KKT Conditions are designed precisely to calculate local optima while strictly respecting equality ($h(x)=0$) and inequality ($g(x)\le 0$) boundaries)
  • In discrete computer science, an algorithm might sort a list in exactly $O(N\log N)$ steps. In continuous optimization, you cannot count exact steps because you are dealing with real numbers drifting down infinite fractional curves. Complexity must instead be measured by proving convergence rates (e.g., linear, quadratic) based on the structural properties of the landscape, like whether the surface is strictly convex or non-convex.

---

Learning from Data vs Design from Specifications

While learning is based on data, this other approach does not use data. It is a ‘design’ approach based on specifications, and is often discussed alongside the learning approach in pattern recognition literature.

A classic example illustrating the difference between learning from data and design from specifications is coin recognition in vending machines.

The goal is to classify:

• pennies
• nickels
• dimes
• quarters

using:

• coin size
• coin mass

So each coin is represented as a 2D input vector:

$x=(\text{size},\text{mass})$

In the learning approach:

• we collect example coins from each denomination
• each example becomes a labeled training point
• input → size and mass
• output → coin denomination

Coins of the same type form clusters in feature space.

The learning algorithm:

• observes the training data
• searches for a hypothesis $g$
• learns decision boundaries separating the coin classes

A new coin is classified by:

1. measuring size and mass
2. feeding the measurement into the learned classifier

In feature space:

• each denomination forms a cluster
• the classifier partitions the space into regions

The boundaries are inferred directly from data.

In the design approach:

• we use prior knowledge instead of training data
• obtain official specifications from the U.S. Mint
• model:
  • expected coin size
  • expected mass
  • measurement noise
  • wear-and-tear variations
  • relative frequency of each coin

Using this information, we construct a joint probability distribution over:

• size
• mass
• denomination

Once the probability model is known, we analytically derive the optimal classifier.

For a given measurement $(x)$:

choose the denomination with the highest probability:

$\arg {\max }_{y}P(y\mid x)$

This minimizes classification error probability.

In the design approach:

• the problem is fully specified
• we derive the solution mathematically
• Example : Classifying numbers into primes and non-primes, Determining the time it would take a falling object to hit the ground

In the learning approach:

• the target function is unknown
• data is needed to approximate it empirically
• Example : Detecting potential fraud in credit card charges, Determining the age at which a particular medical test should be performed

The main difference between the learning approach and the design approach is the role that data plays. In the design approach, the problem is well specified and one can analytically derive f without the need to see any data. In the learning approach, the problem is much less specified, and one needs data to pin down what f is.

---

Types of Learning

Learning from data aims to infer an underlying process from observations. Because real-world settings vary widely, different learning paradigms have been developed.

Supervised Learning

In supervised learning, each training example includes both:

• input $x$
• correct output $y$

So the dataset has the form:

$(x_i,y_i)$

The learning algorithm uses these labeled examples to approximate the unknown function:

$f:\mathcal{X}\to \mathcal{Y}$

Example: Handwritten Digit Recognition

Each training sample consists of:

• input: image of a digit
• output: label in $\{0,1,2,3,4,5,6,7,8,9\}$

So the dataset is:

$(\text{image},\text{digit})$

The model learns to map images → digit labels.

Data can be presented to the learning process

• Data sets are typically created and presented to us in their entirety at the outset of the learning process.

• Active Learning In active learning:

  • The algorithm selects inputs $x$
  • a supervisor provides the corresponding output $y$ So instead of passively receiving data, the model chooses what to learn from.

The learner can ask strategic questions:

“Which example would be most informative?”

This is similar to a game of 20 questions.

• reduces number of labeled examples needed

• focuses learning on informative regions of the input space

• Online Learning In online learning:

  • data arrives sequentially
  • the algorithm updates after each example

Instead of seeing a full dataset, the learner processes a stream:

$(x_1,y_1),(x_2,y_2),\dots$

The model must:

• learn continuously
• update in real time

Use Cases

• streaming recommendation systems
• real-time user feedback (e.g., clicks, ratings)
• systems with memory or compute constraints
• no full dataset is required

No Free Lunch (NFL) theorem

Setup :

Consider a Boolean target function

$$f:\mathcal{X}\to \{0,1\},$$

defined over the three-dimensional Boolean input space

$$\mathcal{X}=\{0,1{\}}^3.$$

Since each input has three binary features, the input space contains

$$|\mathcal{X}|=2^3=8$$

possible input vectors:

$$000,001,010,011,100,101,110,111.$$

Suppose we are given the following training dataset $D$ consisting of five labeled examples:

Input ($x_n$)	Output ($y_n=f(x_n)$)
000	0
001	1
010	1
011	0
100	1

The labels for the remaining inputs

$$101,110,111$$

are unknown.

Since each of these three unseen inputs can independently take either value $0$ or $1$, there are

$$2^3=8$$

possible target functions that are consistent with the observed training data.

More generally, because a Boolean function on three Boolean inputs assigns one binary output to each of the eight possible inputs, the total number of Boolean target functions is

$$2^{2^3}=2^8=256.$$

Only 8 of these 256 functions agree with the given training dataset; they differ only in how they label the three unseen inputs. The training dataset $D$ labels only 5 of the 8 possible inputs. The remaining unseen inputs are:

$101,110,111$

Since these three inputs are never observed, a target function can assign either 0 or 1 independently to each of them.

For each learning algorithm, let the learned hypothesis be $g$.

Evaluate the performance of $g$ by determining how many of the eight candidate target functions agree with $g$ on:

• all 3 unseen inputs,
• exactly 2 unseen inputs,
• exactly 1 unseen input,
• none of the unseen inputs.

Consider a few of the following learning scenarios

(a) $\mathcal{H}$ has only two hypotheses, one that always returns '$\bullet$' and one that always returns '$\circ$'. The learning algorithm picks the hypothesis that matches the data set the most.

The hypothesis set is

$$\mathcal{H}=\{\text{Always }0,\text{Always }1\}.$$

The learning algorithm selects the hypothesis that correctly classifies the largest number of training examples.

On $D$, the labels are $0,1,1,0,1$, i.e., three positives and two negatives. The hypothesis that always predicts $1$ correctly classifies $3/5$ training examples, whereas the hypothesis that always predicts $0$ correctly classifies only $2/5$. Therefore, the learning algorithm selects the constant hypothesis $g(101)=1,g(110)=1,g(111)=1.$Comparing the prediction $(1,1,1)$ with all eight candidate target bit-strings: - one target agrees on all three points, - three targets agree on exactly two points, - three targets agree on exactly one point, - one target agrees on none of the points. Hence the distribution is $(1,3,3,1).$To evaluate $g$, compare it against every possible target function and count how many predictions agree.

Target	Matches with $(1,1,1)$
000	0
001	1
010	1
011	2
100	1
101	2
110	2
111	3

This gives the distribution:

Agreement	Number of target functions
3 matches	1
2 matches	3
1 match	3
0 matches	1

or equivalently,

$$(1,3,3,1)=\left(\left(\genfrac{}{}{0ex}{}{3}{3}\right),\left(\genfrac{}{}{0ex}{}{3}{2}\right),\left(\genfrac{}{}{0ex}{}{3}{1}\right),\left(\genfrac{}{}{0ex}{}{3}{0}\right)\right).$$

These are simply the binomial coefficients, corresponding to the number of target functions at each Hamming distance from the hypothesis.

(b) The same $\mathcal{H}$, but the learning algorithm now picks the hypothesis that matches the data set least.

The learning algorithm now deliberately chooses the constant hypothesis that fits the training data least, namely $g(101)=0,g(110)=0,g(111)=0.$Although this prediction differs completely from part (a), the counting argument is identical. Every fixed three-bit prediction has exactly the same Hamming-distance distribution over the eight possible target bit-strings. Thus the distribution is again $(1,3,3,1).$ (c) XOR Hypothesis : $\mathcal{H}=\{\text{XOR}\}$ (only one hypothesis which is always picked), where $\text{XOR}$ is defined by $\text{XOR}(\text{x})=\bullet$ if the number of $1$‘s in $\text{x}$ is odd and $\text{XOR}(\text{x})=\circ$ if the number is even.

The hypothesis set contains only the XOR function:

$$\mathcal{H}=\{\text{XOR}\}.$$ $$\mathrm{XOR}(x)=\{\begin{array}{ll}1,& \text{if the number of 1’s in }x\text{ is odd},\\ 0,& \text{if the number of 1’s is even}.\end{array}$$

Since there is only one hypothesis, it is always selected.

Evaluating XOR on the three unseen inputs:$g(101)=0,g(110)=0,g(111)=1.$ Comparing this fixed prediction with all eight candidate target functions again yields $(1,3,3,1).$ (d) $\mathcal{H}$ contains all possible hypotheses (all Boolean functions on three variables), and the learning algorithm picks the hypothesis that agrees with all training examples, but otherwise disagrees the most with the $\text{XOR}$.

$$|\mathcal{H}|=2^{2^3}=256.$$

The learning algorithm chooses a hypothesis that

1. correctly classifies all training examples, and
2. among all such hypotheses, disagrees with the XOR function as much as possible on the three unseen inputs.

Here $\mathcal{H}$ contains all $256$ Boolean functions. The learning algorithm first requires perfect agreement with the five training examples in $D$. Since the remaining three inputs are unconstrained, it chooses the hypothesis that disagrees with XOR as much as possible on those unseen points by flipping XOR’s outputs: $g(101)=1,g(110)=1,g(111)=0.$Once again, this is simply another fixed three-bit prediction, so its agreement with the eight candidate target functions follows exactly the same combinatorial counting: $(1,3,3,1).$ Key fact: For any fixed prediction $g$ on these 3 points, since the 8 candidate targets range uniformly over all $2^3$ bit-strings, the number of targets agreeing with $g$ in exactly $k$ of the 3 positions is $\left(\genfrac{}{}{0ex}{}{3}{k}\right)$ — independent of what $g$ actually predicts.

Agreement with $g$	# of targets (out of 8)
all 3 points	$\left(\genfrac{}{}{0ex}{}{3}{3}\right)=1$
2 points	$\left(\genfrac{}{}{0ex}{}{3}{2}\right)=3$
1 point	$\left(\genfrac{}{}{0ex}{}{3}{1}\right)=3$
0 points	$\left(\genfrac{}{}{0ex}{}{3}{0}\right)=1$

It holds no matter which $g$ you pick.

Scenario	$g$ on $(101,110,111)$	Agree on 3 / 2 / 1 / 0
(a) best-fit constant	$111$	$1/3/3/1$
(b) worst-fit constant	$000$	$1/3/3/1$
(c) XOR	$001$	$1/3/3/1$
(d) anti-XOR (perfect on $D$)	$110$	$1/3/3/1$

Although the four learning algorithms produce different hypotheses, every fixed prediction on the three unseen inputs has exactly the same agreement distribution over the eight possible target functions. Consequently, averaging over all target functions consistent with the training data, no algorithm performs better than any other.

This illustrates the central idea behind the No Free Lunch principle: without additional assumptions about which target functions are more likely, no learning algorithm has an inherent advantage on unseen data. Any improvement in generalization must come from introducing an appropriate inductive bias, rather than from the learning algorithm alone.

Without making assumptions about the target function, no learning algorithm is inherently better than any other, even random guessing.

Any improvement over random guessing must come from introducing inductive bias (assumptions about which target functions are more likely), rather than from the learning algorithm alone.

Learning is only possible because real-world problems are not arbitrary. The No Free Lunch theorem shows that if every target function were equally likely, no algorithm could outperform any other on average. Successful machine learning therefore depends on incorporating assumptions or biases that reflect the structure of real data.

---

Using a probability distribution

We can indeed infer something outside $\mathcal{D}$ using only $\mathcal{D}$, but in a probabilistic way.

Estimating an Unknown Probability from Sampling : Suppose a bin contains red and green marbles. The proportion of red marbles is such that

• the probability of drawing a red marble is $\mu$,
• the probability of drawing a green marble is $1-\mu$, where $\mu$ is fixed but unknown.

We draw a sample of $N$ marbles with replacement, so each draw is independent. Let $v$ denote the observed fraction of red marbles in the sample.

What does the observed value of $v$ tell us about the unknown probability $\mu$?

⇒ $v$ is an estimate of the unknown parameter $\mu$

For each draw, define the random variable

$$X_i=\{\begin{array}{ll}1,& \text{if the }i\text{th marble is red},\\ 0,& \text{if the }i\text{th marble is green}.\end{array}$$

Since the probability of drawing a red marble is $\mu$,

$$P(X_i=1)=\mu ,P(X_i=0)=1-\mu .$$

Each $X_i$ is therefore a Bernoulli random variable.

We draw $N$ marbles.

If exactly $k$ of them are red, then the observed fraction of red marbles is

$$v=\frac{k}{N}.$$

Since

$$k=X_1+X_2+\cdots +X_N,$$

we can also write

$$v=\frac{X_1+X_2+\cdots +X_N}{N}.$$

The quantity $v$ is called the sample proportion.

$$E[X_i]=1\cdot \mu +0\cdot (1-\mu )=\mu .$$

Using the linearity of expectation,

$$E[v]=E\left[\frac{X_1+\cdots +X_N}{N}\right]=\frac{1}{N}\left(E[X_1]+\cdots +E[X_N]\right).$$

Since every draw has expectation $\mu$,

$$E[v]=\frac{1}{N}(N\mu )=\mu .$$

Therefore,

$$\boxed{E[v]=\mu .}$$

$v$ estimates $\mu$. The sample proportion is an unbiased estimator of the true probability. Individual samples may overestimate or underestimate $\mu$, but over many repeated experiments, their average equals the true value.

Since

$$k=X_1+X_2+\cdots +X_N,$$

its expectation is

$$E[k]=E[X_1+\cdots +X_N]=N\mu .$$

Thus, on average,

$$\boxed{E[k]=N\mu .}$$

Intuitively,

$$k\approx N\mu ,$$

so

$$v=\frac{k}{N}\approx \frac{N\mu }{N}=\mu .$$

This explains why the observed proportion tends to approximate the true probability.

Although $E[v]=\mu$, different samples generally produce different values of $v$.

The variance of the sample proportion is

$$\mathrm{Var}(v)=\frac{\mu (1-\mu )}{N},$$

so the standard deviation is

$$\sqrt{\frac{\mu (1-\mu )}{N}}.$$

As the sample size $N$ increases, this quantity decreases, meaning that the observed values of $v$ become increasingly concentrated around $\mu$.

The Law of Large Numbers states that

$$v⟶\mu$$

with high probability as the sample size grows.

The difference

$$|v-\mu |$$

is called the sampling error.

For sufficiently large sample sizes, concentration results such as Hoeffding’s inequality or the Central Limit Theorem show that this error is likely to be small.

Example : Suppose the true probability is

$$\mu =\mathrm{0.6.}$$

If we repeatedly perform the experiment, we might observe:

Sample size ($N$)	Number of red marbles ($k$)	Observed proportion ($v=k/N$)
10	7	0.70
100	61	0.61
1,000	602	0.602
10,000	5,991	0.5991

The observed proportion fluctuates for small samples but approaches the true probability as the sample size increases.

Similarly, if we repeatedly draw $100$ marbles from the same bin, we might obtain:

Experiment	Observed proportion ($v$)
1	0.66
2	0.73
3	0.71
4	0.69
5	0.75

Some estimates are above the true probability, while others are below it. However, the average of many such experiments approaches $\mu$

---

Hoeffding’s Inequality

To quantify this relationship, we use one of the most important concentration results in probability theory: Hoeffding’s Inequality.

For a sample of size $N$, Hoeffding’s Inequality states that, for any tolerance $ϵ>0$,

$$\boxed{P\left(|v-\mu |>ϵ\right)\le 2e^{-2N{ϵ}^2}.}$$

Hoeffding’s inequality bounds the probability that the sampling error exceeds a chosen tolerance $ϵ$.

The probability that the observed proportion differs from the true probability by more than $ϵ$ decreases exponentially as the sample size $N$ increases.

Only the sample proportion $v$ is random.

The true probability

$$\mu =P(\text{red})$$

is a fixed (but unknown) constant.

The randomness comes entirely from the random sample we draw.

Each new sample produces a different value of

$$v=\frac{k}{N},$$

while $\mu$ remains unchanged.

Therefore, the probability

$$P\left(|v-\mu |>ϵ\right)$$

is taken over all possible random samples of size $N$.

The probability

$$P\left(|v-\mu |>ϵ\right)$$

depends on the unknown value of $\mu$ because

• $\mu$ appears inside the event,
• $\mu$ determines the distribution of the sample.

Hoeffding’s inequality replaces this unknown probability with the universal bound

$$2e^{-2N{ϵ}^2},$$

which does not depend on $\mu$ at all.

Therefore, we obtain a guarantee that holds for every possible value of the unknown probability.

The bound depends only on

• the sample size $N$,
• the tolerance $ϵ$. It does not depend on
• the number of marbles in the bin,
• whether the bin is finite or infinite,
• the actual value of $\mu$.

Consequently, whenever two experiments use the same sample size $N$, Hoeffding’s inequality provides exactly the same probabilistic guarantee, regardless of the size of the underlying population.

The term

$$e^{-2N{ϵ}^2}$$

decreases exponentially with $N$.

This means that doubling the sample size causes the probability of a large estimation error to decrease extremely rapidly.

As $N\to \infty$,

$$2e^{-2N{ϵ}^2}⟶0,$$ $$P\left(|v-\mu |>ϵ\right)⟶0.$$

Example: Applying Hoeffding’s Inequality

Suppose the true probability of drawing a red marble is

$$\mu =0.9,$$

and we draw

$$N=10$$

marbles (with replacement).

We wish to bound the probability that the observed fraction of red marbles satisfies

$$v\le \mathrm{0.1.}$$

Hoeffding’s inequality bounds events of the form

$$|v-\mu |\ge ϵ.$$

Since

$$\mu =0.9,v\le 0.1,$$

the deviation from the true probability is

$$ϵ=|0.1-0.9|=0.8$$

Since

$\{v\le 0.1\}\subseteq \{|v-\mu |\ge 0.8\}$

Therefore,

$$P(v\le 0.1)\le P(|v-0.9|\ge 0.8)$$

Hoeffding’s inequality states

$$P(|v-\mu |\ge ϵ)\le 2e^{-2N{ϵ}^2}.$$ $$P(|v-0.9|\ge 0.8)\le 2e^{-2(10)(0.8{)}^2}.$$ $$P(v\le 0.1)\le 2e^{-12.8}\approx 5.52\times 10^{-6}$$

Using Exact Probability (Binomial Distribution)

Because each draw is independent with probability

$$P(\text{red})=0.9,$$

the number of red marbles follows a Binomial distribution,

$$X\sim \mathrm{Binomial}(10,0.9).$$

The condition

$$v\le 0.1$$

means that at most one red marble is observed:

$$X\le 1.$$

Therefore,

$$P(X\le 1)=P(X=0)+P(X=1).$$

Using the binomial probability formula,

$$P(X=k)=\left(\genfrac{}{}{0ex}{}{10}{k}\right)(0.9{)}^k(0.1{)}^{10-k},$$

Exactly 0 red marbles

$$P(X=0)=\left(\genfrac{}{}{0ex}{}{10}{0}\right)(0.9{)}^0(0.1{)}^{10}=10^{-10}.$$

Exactly 1 red marble

$$P(X=1)=\left(\genfrac{}{}{0ex}{}{10}{1}\right)(0.9{)}^1(0.1{)}^9=10(0.9)(10^{-9})=9\times 10^{-9}.$$

Hence,

$$P(X\le 1)=10^{-10}+9\times 10^{-9}=9.1\times 10^{-9}.$$ $$P(v\le 0.1)=9.1\times 10^{-9}$$

Exact Binomial probability	$9.1\times 10^{-9}$
Hoeffding upper bound	$5.52\times 10^{-6}$

$$9.1\times 10^{-9}<5.52\times 10^{-6},$$

Hoeffding’s inequality is satisfied.

Why Is the Hoeffding Bound So Loose : Hoeffding’s inequality is a universal concentration bound. It does not assume that the observations follow a Binomial distribution, nor does it exploit the fact that $\mu =0$ is very close to the extreme value of $1$. It only assumes that each observation is bounded between $0$ and $1$. Because it must provide a guarantee for every possible bounded distribution, it is necessarily conservative.

For small sample sizes such as

$$N=10,$$

the bound can be much larger than the true probability. In this example,

$$5.52\times 10^{-6}\approx 600\times (9.1\times 10^{-9}),$$

so Hoeffding overestimates the probability by roughly a factor of 600.

Hoeffding’s inequality sacrifices tightness in exchange for universality : it guarantees correctness without requiring any knowledge of the underlying distribution beyond boundedness.

As the sample size $N$ increases, however, the exponential term

$$e^{-2N{ϵ}^2}$$

shrinks rapidly, and Hoeffding’s bound becomes increasingly informative and often much closer to the true probability.

Hoeffding’s inequality provides a distribution-free upper bound on the probability of large deviations between the sample proportion and the true probability.

---