Completeness

Knowledge Map Atlas
Introduction Complete Metric Spaces Completion of a Metric Space Cantor's Intersection Theorem Banach's Fixed-Point Theorem

Introduction

We briefly introduced completeness on earlier pages as a property ensuring metric spaces have "no holes." Now, equipped with the theory of convergence and Cauchy sequences, we can develop completeness fully and prove one of the most important theorems in analysis: Banach's Fixed-Point Theorem.

This theorem states that in a complete metric space, every strong contraction has a unique fixed point, and iterative application of the mapping converges to that fixed point. Far from an abstract curiosity, the theorem is the theoretical backbone of countless algorithms: Newton's method, value iteration in reinforcement learning, and many optimization schemes.

Understanding why these algorithms converge requires understanding completeness at a deeper level than our initial treatment allowed.

Complete Metric Spaces

Recall the universal criterion for completeness: a metric space \(X\) is complete if and only if \(X\) is closed in every metric superspace of \(X\). Alongside Cauchy sequences, we stated an equivalent intrinsic characterization without proving it. We now establish that equivalence formally.

Theorem: Cauchy Criterion for Completeness A metric space \(X\) is complete if and only if every Cauchy sequence in \(X\) converges in \(X\).
Proof:

(\(\Rightarrow\)) Suppose \(X\) is complete in the universal sense, and let \(\{x_n\}\) be a Cauchy sequence in \(X\). We argue by contradiction. Assume that \(\{x_n\}\) does not converge to any point of \(X\). We manufacture a superspace in which \(X\) fails to be closed, contradicting completeness.

Adjoin a single new point \(\omega \notin X\) and set \(Y = X \cup \{\omega\}\). Define \(e : Y \times Y \to [0, \infty)\) by \[ e(a, b) = d(a, b) \ \ (a, b \in X), \quad e(a, \omega) = e(\omega, a) = \lim_{m \to \infty} d(a, x_m) \ \ (a \in X), \quad e(\omega, \omega) = 0. \] The limit defining \(e(a, \omega)\) exists. The reverse triangle inequality \(|d(a, x_m) - d(a, x_k)| \le d(x_m, x_k)\) shows that \(\{d(a, x_m)\}_m\) is a Cauchy sequence of reals, which converges by completeness of \(\mathbb{R}\).

We verify that \(e\) is a metric on \(Y\). Non-negativity and symmetry are immediate. For the identity of indiscernibles, the only non-trivial case is \(e(a, \omega) = 0\) with \(a \in X\). This would give \(d(a, x_m) \to 0\), that is, \(x_m \to a\) in \(X\), contradicting our assumption that \(\{x_n\}\) has no limit in \(X\). Hence \(e(p, q) = 0\) if and only if \(p = q\).

For the triangle inequality, the cases involving \(\omega\) follow by passing to the limit in the corresponding inequality for \(d\). For \(a, b \in X\), taking \(m \to \infty\) in \(d(a, x_m) \le d(a, b) + d(b, x_m)\) yields \(e(a, \omega) \le e(a, b) + e(b, \omega)\). Taking the limit in \(d(a, b) \le d(a, x_m) + d(x_m, b)\) yields \(e(a, b) \le e(a, \omega) + e(\omega, b)\). Since \(e\) restricts to \(d\) on \(X \times X\), the space \((Y, e)\) is a metric superspace of \((X, d)\).

In \((Y, e)\) we have \(x_n \to \omega\). By the \(\varepsilon\)-\(N\) form of the Cauchy condition, each \(\varepsilon \gt 0\) admits an \(N\) with \(d(x_n, x_m) \lt \varepsilon\) for all \(n, m \ge N\). Fixing \(n \ge N\) and letting \(m \to \infty\) gives \(e(x_n, \omega) = \lim_m d(x_n, x_m) \le \varepsilon\). Consequently \(\operatorname{dist}(\omega, X) = \inf_{a \in X} e(\omega, a) = 0\). At the same time \(X^c = Y \setminus X = \{\omega\}\), so \(\operatorname{dist}(\omega, X^c) = e(\omega, \omega) = 0\).

By definition \(\omega\) is thus a boundary point of \(X\) in \(Y\). Since \(\omega \notin X\), the boundary \(\partial X\) is not contained in \(X\), so \(X\) is not closed in \(Y\). This contradicts the completeness of \(X\). Hence \(\{x_n\}\) converges in \(X\).

(\(\Leftarrow\)) Suppose every Cauchy sequence in \(X\) converges in \(X\), and let \((Y, e)\) be any metric superspace of \(X\). To show \(X\) is closed in \(Y\), take any \(z \in \overline{X}^{\,Y}\). If \(z \in X\) there is nothing to prove, so assume \(z \in Y \setminus X\). Then \(z\) is a boundary point, and every ball about \(z\) meets \(X\). Choose \(x_n \in X\) with \(e(x_n, z) \lt 1/n\), so that \(x_n \to z\) in \(Y\).

A convergent sequence is Cauchy in \(Y\). By the \(\varepsilon\)-\(N\) form of the Cauchy condition, each \(\varepsilon \gt 0\) admits an \(N\) with \(e(x_n, x_m) \lt \varepsilon\) for all \(n, m \ge N\). Since \(e\) agrees with \(d\) on \(X\), the same \(N\) works for \(d\), so the sequence \(\{x_n\}\) is Cauchy in \((X, d)\) as well. By hypothesis it converges to some \(x \in X\). Then \(x_n \to x\) in \(Y\) too, and by uniqueness of limits in \(Y\) we conclude \(z = x \in X\). Hence \(\overline{X}^{\,Y} \subseteq X\), so \(\partial X \subseteq X\) and \(X\) is closed in \(Y\). As \(Y\) was arbitrary, \(X\) is complete.

Insight: Why Completeness Matters in Machine Learning

Parameter spaces for neural networks live in \(\mathbb{R}^n\), which is complete. Thus, gradient-based optimizations have a valid "target" to converge to (provided contraction conditions hold).

However, function spaces require careful treatment:

  • \(C([0,1])\) with the uniform metric \(d_\infty\) is complete, since uniform limits of continuous functions are continuous.
  • \(C([0,1])\) with the integral metric \(d_1(f,g) = \int_0^1 |f(x) - g(x)| \, dx\) is not complete. Its completion is the Lebesgue space \(L^1([0,1])\).
  • In Reinforcement Learning over a state space \(\mathcal{S}\), value functions live in \(\ell^\infty(\mathcal{S})\), the space of bounded functions under the supremum norm \(\|V\|_\infty = \sup_{s \in \mathcal{S}} |V(s)|\), which is complete. Pointwise values matter here, so the norm in play is the supremum norm rather than an almost-everywhere essential supremum. Completeness guarantees that the Bellman operator, a strong contraction in this norm, has a fixed point (the optimal value function) within the space.

Completion of a Metric Space

What if our space is not complete? Can we "fill the holes"? In fact, every metric space has a minimal complete superspace.

Definition: Completion of a Metric Space Suppose \((X, d)\) is a metric space. A metric space \((Y, e)\) is called a completion of \((X, d)\) if and only if \((Y, e)\) is complete and \((X, d)\) is isometric to a dense subspace of \((Y, e)\).

From a mathematical perspective, the existence of a completion is only half the story. If we could "complete" a space in multiple ways that result in fundamentally different structures, the concept would lose its power. The Uniqueness Theorem ensures that the completion of a metric space is unique "up to isometry": any two completions are essentially identical in their distance-preserving structure.

In Computer Science, this is about the canonicity of representation. Consider the challenge of representing real numbers using different underlying logic or data structures.

The Uniqueness Theorem supplies the formal guarantee. If we design a system to handle "incomplete" data (like rational numbers) and extend it to handle all limit points, the resulting system's behavioral properties are invariant regardless of the underlying encoding (for example, Cauchy sequences versus Dedekind cuts). This ensures that algorithms relying on the "structure" of the space remain robust across different implementations.

Theorem: Uniqueness of Completion

Suppose that \((X, d)\) is a metric space and \((X', m)\) and \((X'', s)\) are completions of \(X\), where \(\psi: X \to X'\) and \(\phi: X \to X''\) are isometries onto dense subspaces of \(X'\) and \(X''\), respectively. Then there exists an isometry from \(X'\) to \(X''\) that maps \(\psi(X)\) onto \(\phi(X)\).

The proof relies on a general principle about extending functions from a dense subset. If \(f: S \to Y\) is uniformly continuous on a dense subset \(S \subseteq X\) and \(Y\) is complete, then \(f\) admits a unique continuous extension to all of \(X\).

The idea is natural. For any \(x \in X\), density provides a sequence \(s_n \in S\) with \(s_n \to x\). Uniform continuity transfers the Cauchy property of \(\{s_n\}\) to \(\{f(s_n)\}\) in \(Y\), and completeness of \(Y\) produces a limit, which serves as the extended value \(\tilde f(x)\). Well-definedness (independence of the approximating sequence) again comes from uniform continuity. Furthermore, if \(f\) happens to be an isometry, the extension is an isometry too, since distance preservation passes through the limit by continuity.

We formalize the notion of extension before proceeding.

Definition: Extension and Restriction Suppose \(f\) and \(g\) are functions. We say that \(f\) is a restriction of \(g\) and that \(g\) is an extension of \(f\) if and only if \(\operatorname{dom}(f) \subseteq \operatorname{dom}(g) \) and \(f(x) = g(x)\) for all \(x \in \operatorname{dom}(f)\). In this case, if \(A = \operatorname{dom}(f)\), we say that \(f\) is the restriction of \(g\) to \(A\) and write \(f = g \mid_A\).

With this extension principle in hand, we can outline the proof of the Uniqueness of Completion.

Proof Sketch:

The map \(f := \phi \circ \psi^{-1}\) is an isometry from the dense subspace \(\psi(X)\) of \(X'\) onto the dense subspace \(\phi(X)\) of \(X''\).

Since \(X''\) is complete, \(f\) has a unique continuous extension \(\tilde f\) to \(X'\) (by the extension principle above), and this extension is isometric because the isometry equation passes through limits.

Because \(\tilde f\) is an isometry and \(X'\) is complete, the range \(\tilde f(X')\) inherits completeness (Cauchy sequences transfer across isometries), and by the complete subset theorem applied in \(X''\), \(\tilde f(X')\) is closed in \(X''\). Since \(\tilde f(X') \supseteq \phi(X)\), it contains the closure \(\overline{\phi(X)} = X''\). Thus, \(\tilde f\) is an isometry from \(X'\) onto \(X''\).

Example: \(\mathbb{Q}\) Completes to \(\mathbb{R}\)

The completion of the rational numbers \((\mathbb{Q}, |\cdot|)\) is the real numbers \((\mathbb{R}, |\cdot|)\). While we typically construct \(\mathbb{R}\) as equivalence classes of Cauchy sequences, there are other historically significant methods, such as Dedekind cuts.

  • Cauchy Sequences:
    Constructing \(\mathbb{R}\) via the limits of sequences that "should" converge (for example, \((1, 1.4, 1.41, \dots) \to \sqrt{2}\)).
  • Dedekind Cuts:
    Constructing \(\mathbb{R}\) by partitioning \(\mathbb{Q}\) into two sets (those less than \(\sqrt{2}\) and those greater).

The Uniqueness Theorem provides the vital bridge. It proves that these two entirely different mathematical "implementations" result in the same structural reality. Without this theorem, we could not confidently speak of "The Real Numbers". We would be stuck with "the real numbers according to Cauchy" or "the real numbers according to Dedekind." Uniqueness allows us to treat \(\mathbb{R}\) as a single, canonical abstract data type.

Cantor's Intersection Theorem

Cantor's Intersection Theorem provides an alternative characterization of completeness through nested closed sets. This perspective is particularly useful in existence proofs, where we construct a solution by progressively narrowing the search region.

Definition: Nest A non-empty collection \(\mathcal{N}\) of sets is called a nest if and only if for each \(A, B \in \mathcal{N}\), either \(A \subseteq B\) or \(B \subseteq A\).

The nest formulation repackages the Cauchy criterion in the language of shrinking closed sets. A sequence with diminishing tails is exactly a Cauchy sequence. Taking closures of those tails produces a nested family of closed sets whose diameters tend to zero, and a point common to all of them is precisely a limit of the sequence. This yields the following criteria for completeness, which recast it as the guarantee that shrinking closed containers always trap a point.

Theorem: Cantor's Intersection Theorem (Nest & Nested Sequence Criteria for Completeness) A metric space \(X\) is complete if and only if every nest \(\mathcal{F}\) of non-empty closed subsets of \(X\) for which \[ \inf \{\operatorname{diam}(A) \mid A \in \mathcal{F}\} = 0 \] has a singleton intersection.

The following statement is equivalent:

A metric space \(X\) is complete if and only if every sequence \(\{F_n\}\) of non-empty closed subsets of \(X\) for which \(F_{n+1} \subseteq F_n\) for each \(n \in \mathbb{N}\) and \(\operatorname{diam}(F_n) \to 0\) has singleton (hence non-empty) intersection.

Proof Sketch. (\(\Rightarrow\)) Pick \(x_n \in F_n\). Since \(\operatorname{diam}(F_n) \to 0\), \(\{x_n\}\) is Cauchy, and by completeness converges to some \(z \in X\). Each \(F_n\) is closed and eventually contains the tail of \(\{x_n\}\), so \(z \in F_n\) for every \(n\). Hence \(z \in \bigcap F_n\), and the singleton property follows from \(\operatorname{diam}(F_n) \to 0\).

(\(\Leftarrow\)) We argue by contrapositive. If \(X\) is not complete, the Cauchy Criterion yields a non-convergent Cauchy sequence \(\{x_n\}\). Let \(F_n\) be the closure of the tail \(\{x_k : k \geq n\}\) in \(X\). Each \(F_n\) is non-empty and closed, the sequence is nested since later tails are subsets, and \(\operatorname{diam}(F_n) \to 0\) because the tail diameters vanish by the Cauchy property while closure preserves diameter. If some \(z \in \bigcap F_n\), then \(x_n, z \in F_n\) gives \(d(x_n, z) \leq \operatorname{diam}(F_n) \to 0\), which forces \(x_n \to z\) and contradicts non-convergence. Hence \(\bigcap F_n = \emptyset\), so the sequence \(\{F_n\}\) meets every hypothesis of the criterion yet has empty intersection, and the contrapositive is established.

Proof: Equivalence of the Two Criteria

The sketch above settles the nested-sequence form, so it is enough to show that the two criteria impose the same condition on \(X\).

(Nest \(\Rightarrow\) sequence.) A sequence \(\{F_n\}\) of non-empty closed sets with \(F_{n+1} \subseteq F_n\) is a nest, and \(\operatorname{diam}(F_n) \to 0\) gives \(\inf \{\operatorname{diam}(F_n) \mid n \in \mathbb{N}\} = 0\). The nest criterion therefore applies and returns a singleton intersection, which is what the sequence criterion asks for.

(Sequence \(\Rightarrow\) nest.) Let \(\mathcal{F}\) be a nest of non-empty closed subsets of \(X\) with \(\inf \{\operatorname{diam}(A) \mid A \in \mathcal{F}\} = 0\). For each \(n \in \mathbb{N}\) choose \(A_n \in \mathcal{F}\) with \(\operatorname{diam}(A_n) \lt 1/n\), and let \(B_n\) be the smallest of \(A_1, \dots, A_n\). This least element exists because any two members of a nest are comparable, so every finite subfamily is a chain under inclusion. Since \(B_n\) is one of \(A_1, \dots, A_n\), it lies in \(\mathcal{F}\) and is therefore non-empty and closed, and \(B_{n+1} \subseteq B_n\). From \(B_n \subseteq A_n\) and the fact that the diameter is a supremum over a smaller set, we obtain \(\operatorname{diam}(B_n) \lt 1/n\). The nested-sequence criterion therefore gives \(\bigcap B_n = \{z\}\) for some \(z \in X\).

Now fix \(C \in \mathcal{F}\). Since \(\mathcal{F}\) is a nest, for each \(n\) either \(B_n \subseteq C\) or \(C \subseteq B_n\). If the first alternative holds for some \(n\), then \(z \in B_n \subseteq C\). Otherwise \(C \subseteq B_n\) for every \(n\), so \(C \subseteq \bigcap B_n = \{z\}\), and \(C\) is non-empty, forcing \(C = \{z\}\). Either way \(z \in C\), so \(z \in \bigcap \mathcal{F}\). Conversely every \(B_n\) lies in \(\mathcal{F}\), so \(\bigcap \mathcal{F} \subseteq \bigcap B_n = \{z\}\). Hence \(\bigcap \mathcal{F} = \{z\}\).

We ask next which subsets of a complete space are themselves complete.

Theorem: Complete Subset Suppose \(X\) is a complete metric space and \(S \subseteq X\). Then \(S\) is complete if and only if \(S\) is closed in \(X\).
Proof:

(\(\Rightarrow\)) \(S\) complete \(\Rightarrow\) \(S\) closed. Suppose, for contradiction, that \(S\) is not closed in \(X\). Then there exists \(x \in \partial S\) with \(x \notin S\). By the definition of a boundary point, \(\operatorname{dist}(x, S) = 0\), so for each \(n \in \mathbb{N}\) we can pick \(s_n \in S\) with \(d(s_n, x) \lt 1/n\). Then \(s_n \to x\) in \(X\) (ball form of convergence), hence \(\{s_n\}\) is Cauchy in \(X\).

To transfer this to \(S\), take \(r \gt 0\). Some ball \(\mathcal{B}^X[c; r/2)\) of \(X\) includes a tail \(\{s_n : n \geq N\}\). Re-centering at \(s_N \in S\) and applying the triangle inequality, we obtain \(d(s_n, s_N) \leq d(s_n, c) + d(c, s_N) \lt r/2 + r/2 = r\) for all \(n \geq N\), so the tail lies in \(\mathcal{B}^S[s_N; r)\). Thus \(\{s_n\}\) is also Cauchy in \(S\).

By completeness of \(S\), \(s_n \to s\) for some \(s \in S\). Since every ball of \(S\) is included in the corresponding ball of \(X\), convergence in \(S\) implies convergence in \(X\) to the same point, so \(s_n \to s\) in \(X\) as well. Uniqueness of limits in \(X\) then forces \(s = x\), so \(x \in S\), contradicting \(x \notin S\). Hence \(S\) is closed.

(\(\Leftarrow\)) \(S\) closed \(\Rightarrow\) \(S\) complete. Let \(\{s_n\}\) be Cauchy in \(S\). Since any ball of \(S\) is included in the corresponding ball of \(X\), \(\{s_n\}\) is also Cauchy in \(X\). By completeness of \(X\) and the Cauchy Criterion, \(s_n \to x\) for some \(x \in X\).

We claim \(x \in S\). Any open ball \(\mathcal{B}^X[x; r)\) includes a tail of \(\{s_n\} \subseteq S\), so \(\mathcal{B}^X[x; r) \cap S \neq \emptyset\) for every \(r \gt 0\). Hence \(\operatorname{dist}(x, S) = 0\). If \(x \notin S\), then \(x \in S^c\) gives \(\operatorname{dist}(x, S^c) = 0\) as well, so \(x \in \partial S\). But \(S\) is closed, forcing \(x \in S\), a contradiction. Thus \(x \in S\), and by the subspace convergence theorem, \(\{s_n\}\) converges to \(x\) in \(S\). Hence \(S\) is complete.

CS Insight: The Bridge Between Ideal Convergence and Algorithmic Reality

While computer algorithms are inherently finite, Cantor's Intersection Theorem provides the theoretical upper bound and the logical justification for their convergence.

  • Bisection Method (Termination Logic):
    Numerical solvers rely on Cantor's theorem to guarantee that a "true" root exists within the shrinking interval. When we stop at a tolerance \(\epsilon\), the theorem ensures that our result is a valid approximation of a unique point in \(\mathbb{R}\), rather than an empty search in a space with "holes."
  • Spatial Indexing (Numerical Stability):
    Data structures like Kd-trees partition space into nested regions. The theorem justifies the stability of point-location queries. As the diameter of the partition shrinks, the identity of the trapped point becomes mathematically certain.
  • Floating-Point as a Limit-Logic:
    Floating-point numbers are discrete and finite, but they are designed to shadow the complete structure of \(\mathbb{R}\). Cantor's theorem is the blueprint for this design. It lets us treat increasing precision as a process of converging toward a canonical mathematical object.

Banach's Fixed-Point Theorem

We now formally explain why many optimization methods converge.

Definition: Fixed Point Suppose \(X\) is a non-empty set and \(f: X \to X\). A point \(x \in X\) is called a fixed point for \(f\) if and only if \(f(x) = x\).
Theorem: Banach's Fixed-Point Theorem Suppose \((X, d)\) is a non-empty complete metric space and \(f: X \to X\) is a (strong) contraction on \(X\) with contraction factor \(k \in [0, 1)\). Then \(f\) has a unique fixed point in \(X\) and, for each \(w \in X\), the sequence \(\{f^n(w)\}\) converges to this point.

Note that for \(n \in \mathbb{N}\), \(f^n\) is the composition of \(n\) copies of \(f\). We shall use the following theorem in the proof.

Theorem: Iterates of a Strong Contraction Form a Cauchy Sequence Suppose \((X, d)\) is a metric space and \(f\) is a (strong) contraction on \(X\) with contraction factor \(k \in [0, 1)\). Then,
  1. for each \(a, b \in X\), the real sequence \(\{d(f^n(a), f^n(b))\}\) converges to \(0\).
  2. for each \(x \in X\), the sequence \(\{f^n(x)\}\) is a Cauchy sequence in \(X\).
Proof:

(1) By iterating the contraction inequality, \[ d(f^n(a), f^n(b)) \leq k \cdot d(f^{n-1}(a), f^{n-1}(b)) \leq \cdots \leq k^n \cdot d(a, b). \] Since \(k \in [0, 1)\), we have \(k^n \to 0\), so \(d(f^n(a), f^n(b)) \to 0\).

(2) Fix \(x \in X\) and set \(c := d(x, f(x))\). By (1) applied with \(a = x, b = f(x)\), we obtain \(d(f^n(x), f^{n+1}(x)) \leq k^n c\). For \(m \gt n\), the triangle inequality and the geometric series yield \[ d(f^n(x), f^m(x)) \leq \sum_{i=n}^{m-1} d(f^i(x), f^{i+1}(x)) \leq \sum_{i=n}^{m-1} k^i c \leq \frac{k^n}{1 - k} \cdot c. \] Since \(k^n \to 0\), the right-hand side can be made arbitrarily small by choosing \(n\) large, which establishes the Cauchy property.

Proof: Suppose that \(w \in X\). By the preceding theorem, \(\{f^n(w)\}\) is Cauchy in \(X\), and since \(X\) is complete, this sequence converges in \(X\).
Let \(z = \lim f^n(w)\). Since \(f\) is a contraction, it is uniformly continuous (Lipschitz with constant \(k\)), hence continuous, so \(f(x_n) \to f(z)\) whenever \(x_n \to z\). In particular, \[ f(z) = \lim_{n \to \infty} f(f^n(w)) = \lim_{n \to \infty} f^{n+1}(w). \] Since \(\{f^{n+1}(w)\}\) is a subsequence of \(\{f^n(w)\}\), it has the same limit: \[ \lim_{n \to \infty} f^{n+1}(w) = \lim_{n \to \infty} f^n(w) = z, \] so that \(f(z) = z\) as required.
The map \(f\) has no other fixed point. If \(a \in X\) were also fixed, then \[ d(a, z) = d(f(a), f(z)) \leq k \, d(a, z), \] which forces \(d(a, z) = 0\) and thus \(a = z\) because \(k \lt 1\).
Corollary: Convergence Rate

Under the hypotheses of Banach's theorem, let \(z\) be the unique fixed point. For any starting point \(w \in X\): \[ d(f^n(w), z) \leq \frac{k^n}{1-k} \cdot d(w, f(w)). \] In particular, convergence is geometric (linear in the logarithmic scale) with rate \(k\).

Proof:

For \(m \gt n\), iterating the contraction inequality gives \(d(f^i(w), f^{i+1}(w)) \leq k^i \, d(w, f(w))\), so the triangle inequality and the geometric series give: \[ d(f^n(w), f^m(w)) \leq \sum_{i=n}^{m-1} d(f^i(w), f^{i+1}(w)) \leq \sum_{i=n}^{m-1} k^i \cdot d(w, f(w)) \leq \frac{k^n}{1-k} \cdot d(w, f(w)). \] Taking \(m \to \infty\) yields the result.

Insight: Fixed-Point Iterations in Optimization and Learning

Banach's theorem transforms existence and convergence questions into verification of two conditions: (1) the space is complete, and (2) the iteration mapping is a strong contraction.

Newton's Method
For solving \(g(x) = 0\), Newton's iteration is \[ f(x) = x - \frac{g(x)}{g'(x)}. \] Under sufficient smoothness and starting close enough to a simple root \(x^*\), one can show \(f\) is a strong contraction on a neighborhood of \(x^*\) (in fact, convergence is quadratic, not merely linear).

Gradient Descent (Convex Case)
For minimizing \(h: \mathbb{R}^n \to \mathbb{R}\) with \(L\)-Lipschitz gradient and strong convexity parameter \(\mu \gt 0\): \[ f(x) = x - \alpha \nabla h(x) \] is a contraction with \(k = \max(|1 - \alpha L|, |1 - \alpha \mu|)\). Choosing \(\alpha = \frac{2}{L + \mu}\) minimizes \(k\) to \(\frac{L - \mu}{L + \mu} \lt 1\).
Note: In Deep Learning, loss functions are rarely convex, so global contraction is not guaranteed, but local behavior around minima often approximates this dynamics.

Value Iteration (Reinforcement Learning)
The Bellman backup: \[ V_{k+1}(s) = \max_a \left[ R(s, a) + \gamma \sum_{s'} p_T(s' \mid s, a) V_k (s') \right]. \] is a \(\gamma\)-contraction with the supremum norm \(\|\cdot\|_\infty\), where \(\gamma \in (0,1)\) is the discount factor. The space of bounded value functions is complete under \(\|\cdot\|_\infty\), so value iteration converges to the unique optimal value function \(V_*\) as \(k \to \infty\).

Neumann Series and Iterative Methods
In Policy Evaluation, we solve the linear system \(\mathbf{v} = \mathbf{r} + \gamma \mathbf{T}\mathbf{v}\), which formally yields \(\mathbf{v} = (\mathbf{I} - \gamma \mathbf{T})^{-1} \mathbf{r}\). Calculating this inverse directly is computationally expensive (\(O(|\mathcal{S}|^3)\)).

However, because the operator \(T_{\gamma}(\mathbf{v}) = \mathbf{r} + \gamma \mathbf{T}\mathbf{v}\) is a strong contraction, we can apply the Neumann Series expansion: \[ (\mathbf{I} - \gamma \mathbf{T})^{-1} = \sum_{j=0}^{\infty} (\gamma \mathbf{T})^j = \mathbf{I} + \gamma \mathbf{T} + \gamma^2 \mathbf{T}^2 + \dots \] This power series converges because the spectral radius \(\rho(\gamma \mathbf{T}) \lt 1\). This provides the mathematical guarantee that the iterative updates in Reinforcement Learning (CS approach) will converge to the analytical solution of the Bellman equation (Math approach).