Analysis Prerequisites

This page is a short reference, not a course. It states the analysis facts that later proofs use without comment, so that a reader who wants to check a step has somewhere to look. Where a result is standard and long, it is stated with a citation rather than proved — and marked as such.

Suprema and infima

DefinitionSupremum

For $S \subseteq \R$ non-empty and bounded above, $\sup S$ is the least upper bound: $\sup S \ge s$ for all $s \in S$, and no smaller number has that property. It need not belong to $S$. By convention $\sup \emptyset = -\infty$ and $\sup S = +\infty$ when $S$ is unbounded above.

Two facts are used repeatedly in learning theory, where the object of interest is $\sup_{f \in \Fcal} \big(R(f) - \hat R_n(f)\big)$ over a function class $\Fcal$:

$$\sup_{x}\big(g(x) + h(x)\big) \le \sup_x g(x) + \sup_x h(x), \qquad \Big|\sup_x g(x) - \sup_x h(x)\Big| \le \sup_x |g(x) - h(x)| .$$

The first is subadditivity; the second says the supremum is a $1$-Lipschitz functional in the uniform norm, and it is what makes the bounded-differences argument behind McDiarmid's inequality apply to suprema at all.

Continuity and Lipschitz continuity

DefinitionLipschitz continuity

$f : \Xcal \to \R$ on a metric space $(\Xcal, \rho)$ is $K$-Lipschitz if $|f(x) - f(y)| \le K\rho(x,y)$ for all $x,y$. The smallest such $K$ is $\norm{f}_{\mathrm{Lip}}$.

Lipschitz continuity is the regularity assumption of choice in high-dimensional probability, for a specific reason: it is exactly what is needed for a function of many independent inputs to concentrate, and the resulting bounds do not degrade with dimension. Compare:

• $f(x) = \max_i x_i$ is $1$-Lipschitz in $\norm{\cdot}_2$ on $\R^d$ — uniformly in $d$.
• $f(x) = \sum_i x_i$ is $\sqrt d$-Lipschitz.
• $f(x) = \norm{x}_2$ is $1$-Lipschitz, by the triangle inequality.

For differentiable $f$, $\norm{f}_{\mathrm{Lip}} = \sup_x \norm{\nabla f(x)}_2$, which is the bridge between the analytic condition and the calculus.

Convexity inequalities

TheoremJensen's inequality

Let $\varphi : \R \to \R$ be convex and $X$ an integrable random variable with $\E|\varphi(X)| < \infty$. Then

$$\varphi(\E X) \le \E[\varphi(X)] .$$

If $\varphi$ is strictly convex, equality holds if and only if $X$ is almost surely constant.

ProofReveal

TheoremHölder's inequality

For $p, q \in [1,\infty]$ with $1/p + 1/q = 1$,

$$\E|XY| \le \norm{X}_{L^p}\,\norm{Y}_{L^q}, \qquad \norm{X}_{L^p} = \big(\E|X|^p\big)^{1/p} .$$

The case $p = q = 2$ is Cauchy–Schwarz.

Hölder is quoted, not proved here; see the references. The consequence used most often is the monotonicity of $L^p$ norms, $\norm{X}_{L^p} \le \norm{X}_{L^q}$ for $p \le q$, which is why convergence in $L^2$ implies convergence in $L^1$ but not conversely.

Limits and integrals

TheoremMonotone and dominated convergence

Let $X_n \to X$ pointwise almost surely.

• Monotone convergence. If $0 \le X_1 \le X_2 \le \cdots$ then $\E X_n \to \E X$ (both sides possibly $+\infty$).
• Dominated convergence. If $|X_n| \le Y$ for all $n$ with $\E Y < \infty$, then $\E X_n \to \E X$.
• Fatou. If $X_n \ge 0$ then $\E[\liminf_n X_n] \le \liminf_n \E X_n$.

These are quoted from measure theory. They appear whenever a proof differentiates under an expectation — for instance when showing that a moment generating function is smooth inside its domain, a step used silently in the sub-Gaussian computations.

Compactness and existence of minimisers

TheoremExtreme value theorem

A continuous real-valued function on a compact subset of $\R^d$ attains its supremum and infimum.

In $\R^d$, compact means closed and bounded (Heine–Borel). This theorem is what the proof of the spectral theorem uses to produce the top eigenvector, and it is the reason optimisation theory cares about coercivity: if $f(x) \to \infty$ as $\norm{x} \to \infty$, then the sublevel set $\{f \le f(x_0)\}$ is bounded, closed by continuity, hence compact, so a minimiser exists. Without coercivity a continuous convex function need not have a minimiser at all — $f(x) = e^{x}$ on $\R$ is the one-line counterexample.

Problems

Equality in Jensen's inequalityProof · Beginner · 15 min Lipschitz constants depend on the normNumerical · Beginner · 15 min The supremum is 1-Lipschitz in the uniform normProof · Intermediate · 15 min