Foundations

Compactness and Heine-Borel

Sequential compactness, the Heine-Borel theorem in finite dimensions, the extreme value theorem, and why compactness is the key assumption in optimization.

CoreTier 1Stable~40 min

Prerequisites

Metric Spaces Convergence Completeness

Quiz (4)

Why This Matters

Optimization problems in ML ask: does a minimum exist? Compactness is the standard tool for guaranteeing existence of minimizers. The extreme value theorem says a continuous function on a compact set attains its minimum. Without compactness, minima may not exist (the infimum is not achieved), and many proof strategies in learning theory break down.

Core Definitions

Definition

Open Cover

An open cover of a set $K \subseteq X$ is a collection of open sets $\{U_\alpha\}_{\alpha \in I}$ such that $K \subseteq \bigcup_{\alpha \in I} U_\alpha$ . A subcover is a subcollection that still covers $K$ .

Definition

Compactness

A subset $K$ of a metric space is compact if every open cover of $K$ has a finite subcover. Compactness is a topological property: it does not depend on the particular metric, only on the topology.

Definition

Sequential Compactness

A set $K$ is sequentially compact if every sequence in $K$ has a subsequence that converges to a point in $K$ . In metric spaces, compactness and sequential compactness are equivalent.

Definition

Bounded Set

A subset $S$ of a metric space $(X, d)$ is bounded if there exist $x_0 \in X$ and $M > 0$ such that $d(x, x_0) \leq M$ for all $x \in S$ . In $\mathbb{R}^n$ , this means $S$ is contained in some ball of finite radius.

Main Theorems

Theorem

Heine-Borel Theorem

Statement

A subset $K \subseteq \mathbb{R}^n$ is compact if and only if $K$ is closed and bounded.

Intuition

Bounded means sequences cannot escape to infinity. Closed means limits of convergent subsequences stay in the set. Together, they guarantee every sequence has a convergent subsequence with limit in $K$ .

Proof Sketch

Compact implies closed and bounded: If $K$ is not bounded, the sequence $x_n$ with $\|x_n\| \to \infty$ has no convergent subsequence in $K$ . If $K$ is not closed, there is a limit point $x \notin K$ ; a sequence converging to $x$ has no subsequence converging in $K$ . Closed and bounded implies compact: By Bolzano-Weierstrass, every bounded sequence in $\mathbb{R}^n$ has a convergent subsequence. Since $K$ is closed, the limit is in $K$ .

Why It Matters

Heine-Borel makes compactness easy to check in $\mathbb{R}^n$ : just verify closed and bounded. This is the standard way to establish that a constrained optimization problem has a solution.

Failure Mode

Heine-Borel fails in infinite-dimensional spaces. The closed unit ball in $\ell^2$ is closed and bounded but not compact (the standard basis vectors $e_1, e_2, \ldots$ have no convergent subsequence). In infinite dimensions, compactness is a much stronger condition than closed-and-bounded.

Theorem

Extreme Value Theorem

Statement

A continuous function $f: K \to \mathbb{R}$ on a nonempty compact set $K$ attains its maximum and minimum. There exist $x_{\min}, x_{\max} \in K$ with:

$f(x_{\min}) \leq f(x) \leq f(x_{\max}) \quad \text{for all } x \in K$

Intuition

Compactness prevents the minimizing sequence from escaping (either to infinity or to a boundary point outside $K$ ). Continuity preserves convergence, so the limit of a minimizing sequence is a minimizer.

Proof Sketch

Let $m = \inf_{x \in K} f(x)$ . Take a sequence $(x_n)$ with $f(x_n) \to m$ . By compactness, a subsequence $x_{n_k} \to x^* \in K$ . By continuity, $f(x^*) = \lim f(x_{n_k}) = m$ . So the infimum is attained at $x^*$ . Same argument for the supremum.

Why It Matters

This theorem is invoked implicitly whenever you write $\min_{w \in W} L(w)$ for a continuous loss $L$ over a compact parameter set $W$ . Without compactness, you can only write $\inf$ , and the minimizer may not exist.

Failure Mode

Fails without compactness: $f(x) = e^{-x}$ on $(0, \infty)$ has $\inf f = 0$ but no minimizer. Fails without continuity: $f(x) = \mathbf{1}_{x > 0}$ on $[-1, 1]$ achieves its infimum at any $x \leq 0$ , but pathological discontinuous functions on compact sets can fail to have maxima.

Why Compactness Matters in ML

Existence of minimizers: Regularized loss with bounded parameter space (e.g., $\|w\| \leq R$ ) satisfies EVT assumptions.
Uniform convergence: Covering number arguments require compact hypothesis classes.
Continuity arguments: Compactness lets you upgrade pointwise statements to uniform ones (e.g., Dini's theorem).
Function approximation: The Arzela-Ascoli theorem characterizes compact subsets of $C(K)$ , used in universal approximation results.

Common Confusions

Watch Out

Closed and bounded is not enough in infinite dimensions

A common mistake is applying Heine-Borel in function spaces. The closed unit ball in any infinite-dimensional normed space is never compact. This is why weak compactness and related notions are needed in functional analysis and measure-theoretic probability.

Watch Out

Compact subsets of R^n are always complete

Every compact metric space is complete (Cauchy sequences have convergent subsequences, whose limits are in the compact set). But completeness alone does not give compactness: $\mathbb{R}$ is complete but not compact.

Exercises

ExerciseCore

Problem

Is the set $\{x \in \mathbb{R}^2 : \|x\|_2 \leq 1\}$ compact? What about $\{x \in \mathbb{R}^2 : \|x\|_2 < 1\}$ ?

ExerciseAdvanced

Problem

Give an example of a continuous function on a closed (but unbounded) subset of $\mathbb{R}$ that does not attain its infimum. Explain which hypothesis of the extreme value theorem fails.

References

Canonical:

Rudin, Principles of Mathematical Analysis (1976), Chapter 2 (sections on compactness)
Munkres, Topology (2000), Chapter 3
Apostol, Mathematical Analysis (1974), Chapter 3 (compact subsets of R^n)

For ML context:

Shalev-Shwartz & Ben-David, Understanding Machine Learning (2014), Chapter 27 (covering numbers and compactness)
Folland, Real Analysis (1999), Section 4.4 (compactness in metric spaces and function spaces)
Aliprantis & Border, Infinite Dimensional Analysis (2006), Chapters 2-3 (compactness in topological vector spaces)

Last reviewed: April 2026

Prerequisites

Foundations this topic depends on.

Metric Spaces, Convergence, and CompletenessLayer 0A