A normed space is a vector space equipped with a function called a norm that assigns a non-negative real number to each vector, measuring its "size" or "length." Formally, let $V$ be a vector space over the real or complex numbers. A function $||·||: V → [0, ∞)$ is a norm if, for all $x, y$ in $V$ and all scalars $α$, the following three axioms hold:

1. Positive definiteness: $||x|| = 0$ if and only if $x = 0$;
2. Homogeneity: $$||αx|| = |α| · ||x||||;
3. Triangle inequality: $$||x + y|| ≤ ||x|| + ||y||||.

Some common examples of normed spaces relevant to machine learning include:

• The space of real-valued sequences $l^p$, where the norm is given by $||x||_p = (Σ |x_i|^p)^{1/p}$ for $1 ≤ p < ∞$;
• The space of continuous functions on $[0,1]$, denoted $C([0,1])$, with the supremum norm: $||f||_∞ = sup_{x in [0,1]} |f(x)|$;
• The Euclidean space $R^n$ with the familiar $l^2$ norm: $||x||_2 = (Σ x_i^2)^{1/2}$.

In the context of learning, these spaces often serve as hypothesis spaces, where each element (function or vector) is a potential hypothesis.

The norm on a space induces a rich geometry. The set of all points $x$ such that $||x - x_0|| < r$ forms an open ball of radius $r$ centered at $x_0$. Open balls are basic building blocks for defining open sets, which are crucial for describing neighborhoods and continuity.

This geometric structure is essential for understanding hypothesis complexity: the norm provides a way to measure how "large" or "complex" a hypothesis is. For example, in regularization methods, you often penalize hypotheses with large norms to encourage simplicity and prevent overfitting. The shape of balls and open sets can differ depending on the choice of norm, affecting how you interpret proximity and size in your hypothesis space.

A fundamental result is that every normed space is also a metric space. The metric (distance function) is defined by $d(x, y) = ||x - y||$. This metric satisfies the properties required of a metric: non-negativity, identity of indiscernibles, symmetry, and the triangle inequality (which follows directly from the norm's triangle inequality).

Proof sketch:

• Non-negativity and identity: $d(x, y) = ||x - y|| \geq 0$, and $d(x, y) = 0$ if and only if $x = y$ by positive definiteness of the norm;
• Symmetry: $||x - y|| = ||y - x||$ by properties of vector spaces;
• Triangle inequality: $||x - z|| \leq ||x - y|| + ||y - z||$ for any $x, y, z$.

The implication for learning is that you can discuss convergence of hypotheses: a sequence of hypotheses ${f_n}$ converges to $f$ if $||f_n - f|| \to 0$. This is foundational for analyzing the stability and generalization of learning algorithms.