Original lecture date: September 3, 2025. Course edition: Fall 2026.
These notes support STAT 709 at the University of Wisconsin–Madison. Use them alongside the cited textbooks; corrections and questions are welcome.
Welcome to STAT 709! Mathematical statistics is built from probability, linear algebra, analysis, and optimization.
Do not be discouraged if some of the results below are unfamiliar. You are not expected to know everything before taking this course. Use this lecture to identify gaps and warm up by working through the exercises.
This begins Part I. The part overview connects these lectures and includes a final self-check.
Learning goals
By the end of this lecture, you should be able to:
use closure, compactness, and continuity to reason about whether an estimator or optimizer exists;
manipulate \(o(\cdot)\) and \(O(\cdot)\) notation without hiding which quantities are held fixed;
perform basic calculations with Gaussian vectors and Gaussian tails;
use Stirling’s approximation to estimate binomial coefficients and optionally recognize the appearance of entropy;
understand basic properties of eigenvalues and singular values, and translate among quadratic forms, matrix norms, and PCA;
apply standard norm inequalities and duality; and
recognize a convex optimization problem and write its first-order optimality condition, with subgradients as an optional extension.
Sets, topology, and compactness
Throughout the course, the ambient space will usually be the Euclidean space \(\R^d\), equipped with the Euclidean norm \[\|x\|_2=\left(\sum_{j=1}^d x_j^2\right)^{1/2}.\] For \(x\in\R^d\) and \(\epsilon>0\), write \[B_\epsilon(x)=\{y\in\R^d:\|y-x\|_2<\epsilon\}\] for the open ball of radius \(\epsilon\) centered at \(x\).
A set \(U\subset\R^d\) is open if, for every \(x\in U\), there exists \(\epsilon>0\) such that \(B_\epsilon(x)\subset U\). A set \(K\subset\R^d\) is closed if its complement \(K^c\) is open.
Arbitrary unions and finite intersections of open sets are open. Dually, arbitrary intersections and finite unions of closed sets are closed. The restriction to finite intersections and unions matters. For example, \[\bigcap_{n=1}^{\infty}(-1/n,1/n)=\{0\},\] which is not open.
For \(S\subset\R^d\): \[\begin{aligned} \overline S &=\{x\in\R^d:B_\epsilon(x)\cap S\neq\emptyset \text{ for every }\epsilon>0\},\\ S^\circ &=\{x\in S:B_\epsilon(x)\subset S \text{ for some }\epsilon>0\},\\ \partial S&=\overline S\setminus S^\circ.\end{aligned}\] These are called the closure, interior, and boundary of \(S\), respectively.
Equivalently, \(\overline S\) is the smallest closed set containing \(S\). A point \(x\) belongs to \(\overline S\) if and only if there is a sequence \((x_n)_{n\geq 1}\) in \(S\) such that \(x_n\to x\). This sequential characterization is particularly convenient in Euclidean spaces.
The rational numbers \(\Q\) are countable and dense in \(\R\): \(\overline{\Q}=\R\). More generally, \(\Q^d\) is countable and dense in \(\R^d\). Thus, countability is a statement about the number of points, whereas density is a statement about how those points are distributed through the space.
A set is countable if it is finite or can be placed in one-to-one correspondence with a subset of the natural numbers \(\N\). A countable union of countable sets is countable, and every finite Cartesian product of countable sets is countable.
A set \(K\subset\R^d\) is compact if every sequence in \(K\) has a subsequence that converges to a point in \(K\).
For \(K\subset\R^d\), the following statements are equivalent:
\(K\) is compact;
\(K\) is closed and bounded.
Moreover, if \(K\) is nonempty and compact and \(f:K\to\R\) is continuous, then \(f\) attains both its minimum and its maximum on \(K\).
An estimator is often defined as an optimizer, \[\widehat\theta\in\argmin_{\theta\in\Theta} L_n(\theta).\] Before discussing uniqueness or computation, we should ask whether the minimum is attained. Compactness of \(\Theta\) and continuity of \(L_n\) give a simple sufficient condition. If \(\Theta\) is open or unbounded, additional arguments such as coercivity may be needed.
The continuous, strictly convex function \(f(x)=e^x\) on \(\R\) has infimum \(0\), but it has no minimizer. Strict convexity guarantees at most one minimizer; it does not guarantee that a minimizer exists.
Limits and asymptotic notation
Asymptotic notation compares deterministic sequences. Stochastic analogues such as \(o_{\PR}(\cdot)\) and \(O_{\PR}(\cdot)\) will be introduced later. Throughout this section, suppose that \(b_n>0\) for all sufficiently large \(n\).
For real sequences \((a_n)\) and \((b_n)\): \[\begin{aligned} a_n=o(b_n) &\quad\Longleftrightarrow\quad \frac{a_n}{b_n}\longrightarrow 0,\\ a_n=O(b_n) &\quad\Longleftrightarrow\quad \text{there exist }C<\infty\text{ and }N \text{ such that }|a_n|\leq Cb_n\text{ for }n\geq N,\\ a_n\sim b_n &\quad\Longleftrightarrow\quad \frac{a_n}{b_n}\longrightarrow 1.\end{aligned}\] We write \(a_n=\Theta(b_n)\) if both \(a_n=O(b_n)\) and \(b_n=O(|a_n|)\).
Thus, \(o(\cdot)\) is a relative statement of negligibility, \(O(\cdot)\) is an eventual upper bound up to a constant, and \(\sim\) is a relative-error approximation. In particular, \[a_n=(1+o(1))b_n \quad\Longleftrightarrow\quad a_n\sim b_n,\] provided \(b_n\neq 0\) eventually.
As \(n\to\infty\), \[\log n=o(n^\alpha)\quad\text{for every fixed }\alpha>0, \qquad \left(1+\frac{x}{n}\right)^n\longrightarrow e^x\] for every fixed \(x\in\R\). Consequently, \[\left(1+\frac{x}{n}\right)^n=e^x(1+o(1)).\] The word “fixed” is important: the conclusion need not remain valid uniformly if \(x=x_n\) is allowed to grow with \(n\).
Useful calculation rules.
If the expressions are well defined and the comparison sequences are eventually positive, then: \[\begin{aligned} a_n=o(b_n),\ c_n=O(d_n) &\quad\Longrightarrow\quad a_nc_n=o(b_nd_n),\\ a_n=O(b_n),\ c_n=O(d_n) &\quad\Longrightarrow\quad a_n+c_n=O(b_n+d_n),\\ a_n=o(1) &\quad\Longrightarrow\quad \frac{1}{1+a_n}=1-a_n+O(a_n^2).\end{aligned}\] The last identity is a first-order Taylor expansion.
Constants and uniformity.
If \(a_n\) also depends on a parameter \(\theta\), the statement \(a_n(\theta)=O(b_n)\) usually means that the constant may depend on \(\theta\). The stronger statement \[\sup_{\theta\in\Theta}|a_n(\theta)|=O(b_n)\] uses one constant uniformly over \(\Theta\). Statistical arguments involving a supremum over a parameter space generally require the uniform form.
The statement \(a_n=O(b_n)\) does not imply that \(a_n/b_n\) converges. For example, \(a_n=(-1)^n\) is \(O(1)\), but it has no limit.
Gaussian calculations
One-dimensional and multivariate Gaussian variables
The Gaussian distribution appears throughout mathematical statistics because it is stable under linear transformations and because normalized sums often approach it.
A random variable \(G\) has the standard normal distribution, written \(G\sim N(0,1)\), if it has density \[\phi(x)=\frac{1}{\sqrt{2\pi}}e^{-x^2/2}, \qquad x\in\R.\] Its upper-tail function is \[\overline\Phi(t)=\PR(G>t)=\int_t^\infty\phi(x)\,dx, \qquad t\in\R.\] The identity \(\int_{-\infty}^{\infty}e^{-x^2/2}\,dx=\sqrt{2\pi}\) ensures that \(\phi\) integrates to one.
A random vector \(X\in\R^d\) is Gaussian if every linear combination \(v^\top X\) is a one-dimensional Gaussian random variable. We write \(X\sim N(\mu,\Sigma)\) when \(\E X=\mu\) and \(\operatorname{Cov}(X)=\Sigma\). The covariance matrix \(\Sigma\) is symmetric and positive semidefinite; it may be singular.
If \(\Sigma\) is positive definite, \(X\) has the multivariate Gaussian density \[f_X(x) =\frac{1}{(2\pi)^{d/2}\det(\Sigma)^{1/2}} \exp\left\{-\frac12 (x-\mu)^\top\Sigma^{-1}(x-\mu)\right\}, \qquad x\in\R^d.\] When \(\Sigma\) is singular, the same Gaussian-vector definition applies, but the distribution is supported on a lower-dimensional affine subspace and does not have a density with respect to \(d\)-dimensional Lebesgue measure.
The defining projection property makes the most useful calculation immediate: for every fixed \(v\in\R^d\), \[v^\top X\sim N(v^\top\mu,v^\top\Sigma v).\] More generally, stacking several linear projections gives the following affine-transformation rule.
If \(X\sim N(\mu,\Sigma)\), \(A\in\R^{m\times d}\), and \(b\in\R^m\), then \[AX+b\sim N(A\mu+b,A\Sigma A^\top).\] In particular, if \(G\sim N(0,I_d)\), then \(AG\sim N(0,AA^\top)\).
Uncorrelated random variables need not be independent in general. For a jointly Gaussian vector, however, zero covariance does imply independence. Thus, if \(X\sim N(\mu,\Sigma)\) and \(\Sigma\) is diagonal, the coordinates of \(X\) are independent.
Predict a projected variance.
Consider the fixed two-dimensional Gaussian model \[\mu=\begin{pmatrix}0.5\\-0.3\end{pmatrix},\qquad \Sigma=\begin{pmatrix}1.6&0.9\\0.9&1.1\end{pmatrix},\qquad u_\theta=\begin{pmatrix}\cos\theta\\\sin\theta\end{pmatrix}.\] Before comparing directions, predict \(\var(u_{45^\circ}^\top X)\). Does the positive covariance make it larger than either coordinate variance? Report a decimal value in squared coordinate units (scientific notation is also acceptable); give three decimal places.
The projection rule gives \[\E[u_\theta^\top X]=0.5\cos\theta-0.3\sin\theta,\qquad \var(u_\theta^\top X) =1.6\cos^2\theta+2(0.9)\sin\theta\cos\theta+1.1\sin^2\theta.\] At \(45^\circ\), both coordinates of \(u_\theta\) equal \(1/\sqrt2\), so the mean is \(0.2/\sqrt2\) and the variance is \[\frac{1.6+2(0.9)+1.1}{2}=2.25.\] The two covariance cross terms contribute \(0.9\): omitting them gives \(1.35\). The standard deviation is \(1.5\), whereas the requested variance is \(2.25\). The explanation is available whether or not you try the check.
Static comparison. These exact parameter calculations give the comparison without a simulation: \[\begin{array}{c|ccc} \theta & 0^\circ & 45^\circ & 90^\circ\\ \hline \E[u_\theta^\top X] & 0.5 & 0.2/\sqrt2 & -0.3\\ \var(u_\theta^\top X) & 1.6 & 2.25 & 1.1 \end{array}\] Rotating the direction changes the projections of the same observations, not the observations themselves. A finite projected sample illustrates the Gaussian law; its histogram need not match the reference density exactly. Positive semidefiniteness: every covariance satisfies \(u^\top\Sigma u=\var(u^\top X)\geq0\). If this variance is zero, the projection equals its mean almost surely: it is a point mass, not a density of positive width. The displayed covariance is positive definite, since \(1.6>0\) and \(\det\Sigma=0.95>0\). For a related variance calculation, see Exercise 6.
Gaussian tails and Mills’ ratio
For every \(t>0\), \[\frac{t}{t^2+1}\phi(t) \leq \overline\Phi(t) \leq \frac{\phi(t)}{t}.\] Consequently, the logarithm of the Gaussian upper tail has leading term \(-t^2/2\) as \(t\to\infty\).
Proof. Since \(\phi'(x)=-x\phi(x)\), \[\overline\Phi(t) =\int_t^\infty\phi(x)\,dx \leq \frac{1}{t}\int_t^\infty x\phi(x)\,dx =\frac{\phi(t)}{t}.\] Integration by parts also gives \[\overline\Phi(t) =\frac{\phi(t)}{t} -\int_t^\infty\frac{\phi(x)}{x^2}\,dx \geq \frac{\phi(t)}{t}-\frac{\overline\Phi(t)}{t^2}.\] Rearranging yields the lower bound. ◻
Used again in Gaussian-type tail bounds and the optional thresholding lecture.
The moment-generating function gives the convenient, slightly looser bound \[\PR(|G|\geq t)\leq 2e^{-t^2/2},\qquad t\geq 0.\]
Let \(G_1,\ldots,G_d\) be standard normal random variables; independence is not needed for this bound. By a union bound, \[\PR\left(\max_{1\leq j\leq d}|G_j|\geq t\right) \leq 2d e^{-t^2/2}.\] Therefore, with probability at least \(1-\delta\), \[\max_{1\leq j\leq d}|G_j| \leq \sqrt{2\log(2d/\delta)}.\] The scale \(\sqrt{\log d}\) is a recurring high-dimensional noise threshold.
Instructor’s NoteA direct Gaussian tail bound
Moment-generating functions are a powerful, general-purpose method that we will study later. Here we can obtain the tail bound by combining Proposition 2 with a direct calculation using the Gaussian density.
Recall Mills’ ratio: its upper bound is \(\overline\Phi(t)\leq\phi(t)/t\) for \(t>0\).
For \(t>1\), the upper bound in Proposition 2 is tighter than the simpler bound \(2e^{-t^2/2}\): by symmetry, \[\PR(|G|\geq t) =2\overline\Phi(t) \leq\frac{2\phi(t)}{t} =\frac{\sqrt{2/\pi}}{t}e^{-t^2/2} <e^{-t^2/2}\leq 2e^{-t^2/2}.\]
For \(0<t<1\), a change of variables gives a simple direct argument. In fact, this argument works for every \(t\geq0\) and improves the constant \(2\) to \(1\). Substitute \(x=t+u\): \[\begin{aligned} \overline\Phi(t) &=\int_0^\infty\phi(t+u)\,du\\ &=e^{-t^2/2}\int_0^\infty e^{-tu}\phi(u)\,du\\ &\leq e^{-t^2/2}\int_0^\infty\phi(u)\,du =\frac12 e^{-t^2/2}. \end{aligned}\] The only inequality is \(e^{-tu}\leq1\), since \(t,u\geq0\); the last equality uses symmetry of the standard normal density. Multiplying by \(2\) gives \[\boxed{\PR(|G|\geq t)\leq e^{-t^2/2}\leq 2e^{-t^2/2}, \qquad t\geq0.}\] This also covers \(t=0\) and \(t=1\), and establishes the bound used in the noise-scale calculation without moment-generating functions.
Combinatorics, Stirling’s formula, and entropy
For integers \(0\leq k\leq n\), \[\binom{n}{k}=\frac{n!}{k!(n-k)!}, \qquad n!=1\cdot 2\cdots n.\] The binomial coefficient counts subsets of size \(k\) selected from \(n\) objects. In probability it also describes the mass function of a binomial random variable.
As \(n\to\infty\), \[n!=\sqrt{2\pi n}\left(\frac{n}{e}\right)^n(1+o(1)).\] Equivalently, \[\log(n!)=n\log n-n+\frac12\log(2\pi n)+o(1).\]
Suppose \(X_1,\ldots,X_n\stackrel{\iid}{\sim}\operatorname{Bernoulli}(1/2)\), \(n\) is even, and \(k=k_n\) is an integer satisfying \(|k|=O(\sqrt n)\). Applying Stirling’s formula to the three factorials gives \[\PR\left(\sum_{i=1}^nX_i=\frac n2+k\right) =2^{-n}\binom{n}{n/2+k} =(1+o(1))\sqrt{\frac{2}{\pi n}} \exp\left(-\frac{2k^2}{n}\right).\] This is a local normal approximation to \(\mathrm{Binomial}(n,1/2)\) near its mean.
Low priority — not examined: Binary entropy
For \(\gamma\in(0,1)\), define the binary entropy function, using natural logarithms, by \[h(\gamma) =-\gamma\log\gamma-(1-\gamma)\log(1-\gamma).\] If \(m=m_n\) and \(m/n\to\gamma\in(0,1)\), then \[\log\binom{n}{m}=n h(m/n)+O(\log n) =(h(\gamma)+o(1))n.\] More precisely, if \(m/n\) remains bounded away from \(0\) and \(1\), then \[\binom{n}{m} =(1+o(1)) \frac{\exp\{n h(m/n)\}} {\sqrt{2\pi n(m/n)(1-m/n)}}.\]
The quantity \(h(\gamma)\) measures the exponential growth rate of the number of subsets with approximately \(\gamma n\) selected elements. With base-\(2\) logarithms, the same count is approximately \(2^{n h_2(\gamma)}\), where \(h_2(\gamma)=h(\gamma)/\log 2\). This combinatorial interpretation connects entropy to coding, likelihoods, and large-deviation probabilities.
Linear algebra for statistics
Trace, covariance, and quadratic forms
For a square matrix \(M\), define \[\tr(M)=\sum_i M_{ii}.\] If the matrix products are dimensionally compatible, the trace is invariant under cyclic permutations: \[\tr(ABC)=\tr(BCA)=\tr(CAB).\] It is not generally invariant under an arbitrary reordering of the factors.
Let \(X\in\R^d\) have mean \(\mu\) and covariance matrix \(\Sigma\), and let \(M\in\R^{d\times d}\). If the relevant second moments are finite, then \[\E[X^\top M X]=\tr(M\Sigma)+\mu^\top M\mu.\] For a centered random vector, this reduces to \(\E[X^\top M X]=\tr(M\Sigma)\).
Proof. Use \(X^\top M X=\tr(MXX^\top)\) and \(\E[XX^\top]=\Sigma+\mu\mu^\top\). ◻
A real symmetric matrix \(A\) is positive semidefinite, written \(A\succeq 0\), if \(x^\top A x\geq 0\) for every \(x\in\R^d\). It is positive definite, written \(A\succ 0\), if the inequality is strict for every nonzero \(x\). Every covariance matrix is positive semidefinite because \[v^\top\Sigma v=\var(v^\top X)\geq 0.\]
Eigenvalues and perturbation
Let \(A\in\R^{d\times d}\) be symmetric. The spectral theorem gives an orthogonal matrix \(Q\) and real eigenvalues \(\lambda_1(A)\geq\cdots\geq\lambda_d(A)\) such that \[A=Q\diag\{\lambda_1(A),\ldots,\lambda_d(A)\}Q^\top.\] The Rayleigh quotient is \[R_A(x)=\frac{x^\top A x}{x^\top x},\qquad x\neq 0.\] It satisfies \[\lambda_{\max}(A) =\max_{\|x\|_2=1}x^\top A x, \qquad \lambda_{\min}(A) =\min_{\|x\|_2=1}x^\top A x.\]
Low priority — not examined: Courant–Fischer min–max characterization
For \(1\leq k\leq d\), \[\begin{aligned} \lambda_k(A) &=\max_{\substack{V\subset\R^d\\ \dim(V)=k}} \ \min_{\substack{x\in V\\ \|x\|_2=1}}x^\top A x\\ &=\min_{\substack{V\subset\R^d\\ \dim(V)=d-k+1}} \ \max_{\substack{x\in V\\ \|x\|_2=1}}x^\top A x.\end{aligned}\]
If \(A,E\in\R^{d\times d}\) are symmetric, then for every \(1\leq k\leq d\), \[|\lambda_k(A+E)-\lambda_k(A)| \leq \|E\|_{\op},\] where \[\|E\|_{\op} =\max_{\|x\|_2=1}\|Ex\|_2 =\max_{1\leq j\leq d}|\lambda_j(E)|.\]
Thus, a small operator-norm perturbation cannot move any eigenvalue very far. This is the basic bridge from concentration of a sample covariance matrix to accuracy of its empirical eigenvalues.
The corresponding complex-valued results hold for Hermitian matrices, which satisfy \(A=A^*\), where \(A^*=\overline A^\top\) is the conjugate transpose.
Used again in random-matrix norms and PCA perturbation.
Singular value decomposition and matrix norms
Let \(A\in\R^{n\times m}\) be nonzero with rank \(\rho\geq 1\). Its thin singular value decomposition (SVD) is \[A=USV^\top,\] where \(U\in\R^{n\times\rho}\) and \(V\in\R^{m\times\rho}\) have orthonormal columns and \[S=\diag\{s_1(A),\ldots,s_\rho(A)\}, \qquad s_1(A)\geq\cdots\geq s_\rho(A)>0.\] The nonzero eigenvalues of \(A^\top A\) and \(AA^\top\) are \(s_1(A)^2,\ldots,s_\rho(A)^2\).
The largest singular value has the variational representations \[s_1(A) =\max_{\|y\|_2=1}\|Ay\|_2 =\max_{\substack{\|x\|_2=1\\\|y\|_2=1}}x^\top Ay.\]
Two matrix norms used throughout the course are \[\|A\|_{\op}=s_1(A), \qquad \|A\|_{\mathrm F} =\left(\sum_{i,j}A_{ij}^2\right)^{1/2} =\left(\sum_{j=1}^{\rho}s_j(A)^2\right)^{1/2}.\] They satisfy \[\|A\|_{\op}\leq\|A\|_{\mathrm F} \leq\sqrt{\rho}\,\|A\|_{\op}.\]
Low priority — not examined: Optimal low-rank approximation
For \(1\leq r<\rho\), define \[A_r=\sum_{j=1}^r s_j(A)u_jv_j^\top.\] Then \(A_r\) is a best rank-\(r\) approximation to \(A\) in both operator and Frobenius norm: \[\begin{aligned} \min_{\rank(B)\leq r}\|A-B\|_{\op} &=s_{r+1}(A),\\ \min_{\rank(B)\leq r}\|A-B\|_{\mathrm F} &=\left(\sum_{j=r+1}^{\rho}s_j(A)^2\right)^{1/2}.\end{aligned}\]
PCA as variance maximization and low-rank approximation
Let \(X\in\R^{n\times d}\) be a nonzero centered data matrix: row \(i\) is the feature vector for observation \(i\), after subtracting the sample mean. No assumption that \(n>d\) or that \(X\) has full rank is needed. Write \[X=USV^\top, \qquad V=[v_1,\ldots,v_\rho].\] Then:
\(v_j\) is the \(j\)th principal direction or loading vector;
\(Xv_j=s_j u_j\) is the vector of \(j\)th principal-component scores;
the empirical covariance matrix \(\widehat\Sigma=X^\top X/n\) has eigenvectors \(v_j\) and eigenvalues \(s_j^2/n\); and
\(X_r=\sum_{j=1}^r s_j u_jv_j^\top\) is the best rank-\(r\) reconstruction of the centered data.
The first principal direction also solves \[v_1\in\argmax_{\|v\|_2=1} \frac{1}{n}\|Xv\|_2^2 =\argmax_{\|v\|_2=1}v^\top\widehat\Sigma v.\] Thus, the eigenvalue view, the variance-maximization view, and the low-rank approximation view describe the same procedure.
Vector norms, inequalities, and duality
A function \(\|\cdot\|:\R^d\to[0,\infty)\) is a norm if, for all \(x,y\in\R^d\) and scalars \(a\):
\(\|x\|=0\) if and only if \(x=0\);
\(\|ax\|=|a|\,\|x\|\);
\(\|x+y\|\leq\|x\|+\|y\|\).
For \(1\leq p<\infty\), \[\|x\|_p=\left(\sum_{j=1}^d|x_j|^p\right)^{1/p}, \qquad \|x\|_\infty=\max_{1\leq j\leq d}|x_j|.\]
The Euclidean inner product is \(\langle x,y\rangle=x^\top y\). For nonzero \(x,y\), the angle between them is defined by \[\cos\theta=\frac{\langle x,y\rangle}{\|x\|_2\|y\|_2}.\]
For \(x,y\in\R^d\), \[|\langle x,y\rangle|\leq\|x\|_2\|y\|_2.\] More generally, if \(1\leq p,q\leq\infty\) and \(1/p+1/q=1\), then \[|\langle x,y\rangle|\leq\|x\|_p\|y\|_q.\]
Cauchy–Schwarz implies the triangle inequality for the Euclidean norm: \[\begin{split} \|x+y\|_2^2 &=\|x\|_2^2+\|y\|_2^2+2\langle x,y\rangle\\ &\leq\|x\|_2^2+\|y\|_2^2+2\|x\|_2\|y\|_2 =(\|x\|_2+\|y\|_2)^2. \end{split}\]
If \(1\leq p\leq q\leq\infty\), then \[\|x\|_q\leq\|x\|_p \leq d^{1/p-1/q}\|x\|_q.\] Important special cases are \[\|x\|_\infty\leq\|x\|_2\leq\|x\|_1, \qquad \|x\|_1\leq\sqrt d\,\|x\|_2, \qquad \|x\|_2\leq\sqrt d\,\|x\|_\infty.\]
The powers of \(d\) are not cosmetic. For the all-ones vector, \(\|\mathbf 1\|_1=d\), \(\|\mathbf 1\|_2=\sqrt d\), and \(\|\mathbf 1\|_\infty=1\), so the dimension-dependent constants are sharp.
If \(1/p+1/q=1\), then \[\|x\|_p =\max_{\|y\|_q\leq 1}\langle x,y\rangle.\] Thus, the dual norm of \(\ell_p\) is \(\ell_q\); in particular, \(\ell_1\) and \(\ell_\infty\) are dual, while \(\ell_2\) is self-dual.
Norms encode different notions of size. The \(\ell_2\) norm is tied to least-squares geometry, \(\ell_1\) regularization encourages sparse solutions, and \(\ell_\infty\) controls the largest coordinatewise error. Duality explains why an \(\ell_1\) estimation error is naturally paired with an \(\ell_\infty\) noise term.
Convexity and optimality
A set \(C\subset\R^d\) is convex if \[tx+(1-t)y\in C \quad\text{for all }x,y\in C,\ t\in[0,1].\] A function \(f:C\to\R\) is convex if \[f(tx+(1-t)y)\leq tf(x)+(1-t)f(y)\] for all \(x,y\in C\) and \(t\in[0,1]\). It is strictly convex if the inequality is strict whenever \(x\neq y\) and \(t\in(0,1)\).
Geometrically, the graph of a convex function lies below every chord joining two points on the graph. Affine subspaces, Euclidean balls, and half-spaces are convex. A union of convex sets need not be convex, but an arbitrary intersection of convex sets is convex.
Predict the chord gap. Fix \(x,y\) and vary \(t\) from \(0\) to \(1\). When does the gap vanish? Here \(t\) weights \(y\), replacing \(t\) by \(1-t\) in the definition above.
At \(z=(1-t)x+ty\), compare A: average then evaluate, \(f(z)\), with B: evaluate then average, \((1-t)f(x)+tf(y)\). Convexity gives \(B-A\geq0\). The figure illustrates this inequality; it does not prove it for every convex function.
For \(f(z)=\tfrac12(z-\tfrac12)^2+0.35\), \(x=-1\), \(y=1.5\) and \(t=0.5\), we have \(z=0.25\), \(A=0.38125\), \(B=1.1625\), and gap \(0.78125\). At \(t=0.8\) the gap is \(0.5\); at either endpoint \(t=0,1\), or when \(x=y\), the gap is zero.
Let \(C\subset\R^d\) be open and convex.
If \(f\) is differentiable on \(C\), then \(f\) is convex if and only if \[f(y)\geq f(x)+\nabla f(x)^\top(y-x) \quad\text{for all }x,y\in C.\]
If \(f\) is twice continuously differentiable on \(C\), then \(f\) is convex if and only if \(\nabla^2 f(x)\succeq 0\) for every \(x\in C\). If \(\nabla^2 f(x)\succ 0\) everywhere, then \(f\) is strictly convex.
Let \(f:\R^d\to\R\) be differentiable and convex. A point \(x^\star\) minimizes \(f\) if and only if \[\nabla f(x^\star)=0.\]
If \(C\) is nonempty and compact and \(f:C\to\R\) is continuous, a minimizer exists. If, in addition, \(C\) is convex and \(f\) is strictly convex, the minimizer is unique.
Convexity also improves the geometry of optimization: every local minimizer of a convex function over a convex set is global. This structural fact does not by itself prescribe a runtime; computational guarantees also depend on how the problem is represented, the desired accuracy, and the available oracle or algorithm.
For \(X\in\R^{n\times d}\) and \(y\in\R^n\), \[L(\beta)=\|y-X\beta\|_2^2\] is convex because \(\nabla^2L(\beta)=2X^\top X\succeq 0\). It is strictly convex if and only if \(X\) has full column rank. For \(\lambda>0\), \[L_{\lambda,q}(\beta) =\|y-X\beta\|_2^2+\lambda\|\beta\|_q^q\] is strictly convex when \(q>1\). When \(q=1\), the objective remains convex but is nonsmooth and need not be strictly convex.
Subgradients and nonsmooth optimality
Low priority — not examined: Subgradients and nonsmooth optimality
For a convex function \(f:\R^d\to\R\), a vector \(g\in\R^d\) is a subgradient of \(f\) at \(x\in\R^d\) if \[f(y)\geq f(x)+g^\top(y-x) \quad\text{for every }y\in\R^d.\] The set of all subgradients is the subdifferential \(\partial f(x)\).
If \(f\) is differentiable at \(x\), then \(\partial f(x)=\{\nabla f(x)\}\). For \(f(x)=|x|\), \[\partial |x|= \begin{cases} \{1\}, & x>0,\\ [-1,1], & x=0,\\ \{-1\}, & x<0. \end{cases}\]
Let \(f:\R^d\to\R\) be convex. A point \(x^\star\) minimizes \(f\) if and only if \[0\in\partial f(x^\star).\]
For the LASSO objective \[L_{\lambda,1}(\beta) =\|y-X\beta\|_2^2+\lambda\|\beta\|_1,\] the optimality condition is \[0\in 2X^\top(X\widehat\beta-y) +\lambda\,\partial\|\widehat\beta\|_1.\] Coordinatewise, the nonsmooth interval at zero creates a range of correlations for which \(\widehat\beta_j=0\) is optimal. This is the basic mechanism behind sparsity.
Extensions and further reading
Low priority — not examined: Function spaces and orthogonal expansions
Finite-dimensional vectors suggest an infinite-dimensional analogue. Let \(I\subset\R\), and let \(h\) be a nonnegative density on \(I\) satisfying \(\int_I h(x)\,dx=1\). For \(1\leq q<\infty\), define \[\|f\|_{L_q(h)} =\left(\int_I|f(x)|^q h(x)\,dx\right)^{1/q}.\] For square-integrable functions, define \[\langle f,g\rangle_{L_2(h)} =\int_I f(x)g(x)h(x)\,dx.\] Strictly speaking, two functions that agree except on a set of measure zero represent the same element of \(L_q(h)\). Lecture 2 will supply the measure-theoretic language behind this statement.
An orthonormal sequence \((\psi_j)_{j\geq 0}\) satisfies \[\langle\psi_j,\psi_k\rangle_{L_2(h)} =\begin{cases}1,&j=k,\\0,&j\neq k.\end{cases}\] It is an orthonormal basis if its finite linear combinations are dense in \(L_2(h)\). Completeness is essential: an arbitrary orthonormal sequence need not span the space.
For an orthonormal basis, every \(f\in L_2(h)\) has the expansion \[f=\sum_{j=0}^{\infty} \langle f,\psi_j\rangle_{L_2(h)}\psi_j\] with convergence in \(L_2(h)\), and Parseval’s identity gives \[\|f\|_{L_2(h)}^2 =\sum_{j=0}^{\infty} \langle f,\psi_j\rangle_{L_2(h)}^2.\] Truncating the expansion is an orthogonal projection and gives the best approximation within the span of the retained basis functions. This is the function-space counterpart of least squares and truncated SVD.
Fourier basis.
On \(I=[-\pi,\pi]\) with \(h(x)=1/(2\pi)\), the functions \[1,\qquad \{\sqrt2\cos(kx)\}_{k\geq 1},\qquad \{\sqrt2\sin(kx)\}_{k\geq 1}\] form an orthonormal basis of \(L_2(h)\).
Hermite basis.
For the standard Gaussian density \(h=\phi\), the normalized probabilists’ Hermite polynomials begin with \[H_0(x)=1,\quad H_1(x)=x,\quad H_2(x)=\frac{x^2-1}{\sqrt2},\quad H_3(x)=\frac{x^3-3x}{\sqrt6}.\] They form an orthonormal basis of \(L_2(\phi)\). If \(G\sim N(0,1)\) and \(f(G)\) is square integrable, then \[f(G)=\sum_{j=0}^{\infty}\E[f(G)H_j(G)]H_j(G)\] in mean square. This decomposes \(f\) into components of increasing polynomial degree and is useful in Gaussian approximation and the analysis of nonlinear statistics.
Low priority — not examined: Proof sketches for selected results
The Gaussian integral.
Let \(I=\int_{-\infty}^{\infty}e^{-x^2/2}\,dx\). By Tonelli’s theorem (introduced later) and polar coordinates, \[\begin{split} I^2 &=\int_{\R^2}e^{-(x^2+y^2)/2}\,dx\,dy\\ &=\int_0^{2\pi}\int_0^\infty e^{-r^2/2}r\,dr\,d\theta =2\pi. \end{split}\] Hence \(I=\sqrt{2\pi}\).
Weyl’s bound from Rayleigh quotients.
For every unit vector \(x\), \[x^\top A x-\|E\|_{\op} \leq x^\top(A+E)x \leq x^\top A x+\|E\|_{\op}.\] Applying the Courant–Fischer characterization to these inequalities yields Theorem 4.
Why truncated SVD is optimal.
Let \(B\) have rank at most \(r\). Its null space has codimension at most \(r\). The span of the first \(r+1\) right singular vectors of \(A\) must therefore contain a unit vector \(x\) with \(Bx=0\). Hence \[\|A-B\|_{\op}\geq\|(A-B)x\|_2 =\|Ax\|_2\geq s_{r+1}(A).\] The truncated SVD attains this lower bound. A related orthogonality argument gives the Frobenius-norm formula.
Further reading: Historical notes, references, and self-study resources
Stirling’s approximation dates to the early eighteenth century, with the form developed by de Moivre and the constant \(\sqrt{2\pi}\) identified by Stirling; see the MacTutor historical account. The normal approximation to the binomial distribution is correspondingly known as the de Moivre–Laplace theorem. Least squares was developed around the turn of the nineteenth century by Legendre and Gauss. The geometric method now called principal component analysis traces to Pearson and was later developed systematically by Hotelling.
For analysis and function spaces, see Rudin [2, 3]. Tao’s text [4] reviews probability and linear algebra in preparation for random matrix theory. Vershynin [5] and Wainwright [6] connect Gaussian tails, matrix norms, and convexity to modern high-dimensional statistics. Boyd and Vandenberghe [1] is a standard reference for convex optimization.
Useful online supplements include:
Boyd and Vandenberghe’s freely available convex-optimization text;
Vershynin’s High-Dimensional Probability, second-edition draft;
Seeing Theory, a visual and interactive introduction to probability and statistics.
Key ideas
Compactness and continuity help establish existence; they do not imply uniqueness.
Gaussian affine transformations and tail bounds are reusable probability tools.
Quadratic forms, eigenvalues and singular values connect linear algebra to statistical variation.
Norm inequalities and convexity organize estimation and optimization arguments.
Looking ahead
Lecture 2 uses sets and countability to define measurable events and probability measures. This gives the Gaussian and empirical examples a common probability language. Continue to Lecture 2.
Exercises and complete solutions9 exercises · complete solutions
Let \(S=(0,1]\cup\{2\}\subset\R\).
Find \(\overline S\), \(S^\circ\), and \(\partial S\).
Give a continuous function on the bounded open set \((0,1)\) whose infimum is not attained.
Give a continuous function on the closed but unbounded set \([0,\infty)\) whose infimum is not attained.
Reveal solution
Every neighborhood of \(0\) intersects \(S\), so \(0\) is added by closure. The point \(2\) is already in \(S\) and is isolated. Thus \[\overline S=[0,1]\cup\{2\},\qquad S^\circ=(0,1),\qquad \partial S=\{0,1,2\}.\]
Take \(f(x)=x\) on \((0,1)\). It is continuous and \(\inf_{x\in(0,1)}f(x)=0\), but no point of the domain has value \(0\).
Take \(f(x)=e^{-x}\) on \([0,\infty)\). It is continuous and has infimum \(0\), approached as \(x\to\infty\), but \(e^{-x}>0\) for every finite \(x\). These examples show why both closedness and boundedness appear in the Heine–Borel theorem.
Suppose all comparison sequences below are eventually positive.
Show that \(\log n=o(n^\alpha)\) for every fixed \(\alpha>0\).
If \(a_n=O(b_n)\) and \(c_n=o(d_n)\), prove that \(a_nc_n=o(b_nd_n)\).
Give an example in which \(a_n=O(b_n)\) but \(a_n/b_n\) does not converge.
For \(a_n(t)=t/n\), explain the difference between \(a_n(t)=O(n^{-1})\) for every fixed \(t\in\R\) and a uniform \(O(n^{-1})\) statement over all \(t\in\R\).
Reveal solution
Treating \(n\) as a continuous variable, repeated use of l’Hôpital’s rule is unnecessary: \[\lim_{x\to\infty}\frac{\log x}{x^\alpha} =\lim_{x\to\infty}\frac{1/x}{\alpha x^{\alpha-1}} =\lim_{x\to\infty}\frac{1}{\alpha x^\alpha}=0.\] Restricting \(x\) to the integers gives the result.
There are \(C<\infty\) and \(N_1\) such that \(|a_n|/b_n\leq C\) for \(n\geq N_1\). Also, \(|c_n|/d_n\to 0\). Therefore, \[\frac{|a_nc_n|}{b_nd_n} =\frac{|a_n|}{b_n}\frac{|c_n|}{d_n} \leq C\frac{|c_n|}{d_n}\longrightarrow 0.\]
Let \(a_n=(-1)^n\) and \(b_n=1\). Then \(|a_n|\leq b_n\), but \(a_n/b_n=(-1)^n\) has no limit.
For each fixed \(t\), \(|a_n(t)|\leq |t|n^{-1}\), so the hidden constant may be \(|t|\). Uniformly over all \(t\in\R\), \[\sup_{t\in\R}|a_n(t)|=\infty,\] so no finite constant works. Uniformity would hold on a bounded set such as \(|t|\leq M\), with constant \(M\).
Let \(G_1,\ldots,G_d\) be standard normal random variables, not necessarily independent.
Use the Gaussian moment-generating function to prove \(\PR(G_1\geq t)\leq e^{-t^2/2}\) for \(t\geq 0\).
Show that, for \(\delta\in(0,1)\), \[\PR\left( \max_{1\leq j\leq d}|G_j| >\sqrt{2\log(2d/\delta)} \right)\leq\delta.\] Identify exactly where independence would have been used, if it were needed.
Reveal solution
Markov’s inequality (Lecture 4) gives \(\PR(Y\geq a)\leq\E Y/a\) for \(Y\geq0\) and \(a>0\). Completing the square in the normal density yields \[\E e^{\lambda G_1} =e^{\lambda^2/2}\int_{\R}\phi(x-\lambda)\,dx =e^{\lambda^2/2}.\]
For any \(\lambda>0\), Markov’s inequality and \(\E e^{\lambda G_1}=e^{\lambda^2/2}\) give \[\PR(G_1\geq t) =\PR(e^{\lambda G_1}\geq e^{\lambda t}) \leq e^{-\lambda t+\lambda^2/2}.\] For \(t>0\), the exponent is minimized at \(\lambda=t>0\), yielding \(e^{-t^2/2}\). At \(t=0\), use the trivial one-sided bound \(\PR(G_1\geq0)\leq1=e^0\) separately. By symmetry, \(\PR(|G_1|\geq t)\leq 2e^{-t^2/2}\).
The union bound gives \[\PR\left(\max_j|G_j|>t\right) \leq\sum_{j=1}^d\PR(|G_j|>t) \leq 2d e^{-t^2/2}.\] Substituting \(t=\sqrt{2\log(2d/\delta)}\) makes the right-hand side equal to \(\delta\). Independence was not used: the union bound is valid for arbitrarily dependent events.
For even \(n\), use Stirling’s formula to show \[\binom{n}{n/2} \sim 2^n\sqrt{\frac{2}{\pi n}}.\]
Reveal solution
Applying Stirling’s formula to \(n!\) and \((n/2)!\) gives \[n!\sim\sqrt{2\pi n}\left(\frac ne\right)^n, \qquad \left\{\left(\frac n2\right)!\right\}^2 \sim \pi n\left(\frac{n}{2e}\right)^n.\] Therefore, \[\binom{n}{n/2} =\frac{n!}{\{(n/2)!\}^2} \sim \frac{\sqrt{2\pi n}}{\pi n}\,2^n =2^n\sqrt{\frac{2}{\pi n}}.\]
Low priority — not examined: Optional practice: entropy approximation
Let \(m=m_n\in\{1,\ldots,n-1\}\) and \(p_n=m/n\). Assume that \(p_n\) remains in a fixed compact subinterval of \((0,1)\).
Use Stirling’s formula to show \[\log\binom{n}{m} =n h(p_n)-\frac12\log\{2\pi n p_n(1-p_n)\}+o(1).\]
Explain the combinatorial meaning of the leading term \(n h(p_n)\).
Reveal solution
Stirling’s logarithmic form gives \[\begin{split} \log\binom{n}{m} &=\log(n!)-\log(m!)-\log((n-m)!)\\ &=n\log n-m\log m-(n-m)\log(n-m)\\ &\quad -\frac12\log\{2\pi n p_n(1-p_n)\}+o(1). \end{split}\] Because \(m=np_n\) and \(n-m=n(1-p_n)\), the first line of leading terms becomes \[-np_n\log p_n-n(1-p_n)\log(1-p_n)=n h(p_n).\] The uniform separation of \(p_n\) from \(0\) and \(1\) ensures that the Stirling remainders for all three factorials are \(o(1)\).
The quantity \(\binom{n}{m}\) counts binary strings with exactly \(m\) ones, or subsets of size \(m\). Thus \(h(p_n)\) is the exponential growth rate per coordinate of this collection.
Let \(X\in\R^d\) have mean \(\mu\) and covariance \(\Sigma\), and let \(M\in\R^{d\times d}\).
Derive \(\E[X^\top M X]=\tr(M\Sigma)+\mu^\top M\mu\).
Suppose \(\mu=0\). For a unit vector \(v\), interpret \(\E[(v^\top X)^2]\) and show that it is maximized by a leading eigenvector of \(\Sigma\).
Reveal solution
Using the cyclic property of trace, \[X^\top M X=\tr(X^\top M X)=\tr(MXX^\top).\] Taking expectations, \[\E[X^\top M X] =\tr\{M\E(XX^\top)\} =\tr\{M(\Sigma+\mu\mu^\top)\} =\tr(M\Sigma)+\mu^\top M\mu.\] If \(\mu=0\), then \[\E[(v^\top X)^2]=\var(v^\top X)=v^\top\Sigma v.\] The Rayleigh-quotient characterization gives \[\max_{\|v\|_2=1}v^\top\Sigma v=\lambda_{\max}(\Sigma),\] and the maximizers are unit vectors in the leading eigenspace. This is population PCA: choose the direction with largest projected variance.
Let \(1<p<\infty\) and let \(q=p/(p-1)\).
Prove \[\|x\|_p=\max_{\|y\|_q\leq 1}\langle x,y\rangle\] and exhibit a maximizing \(y\) when \(x\neq 0\).
State maximizing choices for the endpoint pairs \((p,q)=(1,\infty)\) and \((p,q)=(\infty,1)\).
Use Cauchy–Schwarz to derive \(\|x\|_1\leq\sqrt d\,\|x\|_2\) and \(\|x\|_2\leq\sqrt d\,\|x\|_\infty\).
Reveal solution
Hölder’s inequality gives \(|\langle x,y\rangle|\leq\|x\|_p\|y\|_q\leq\|x\|_p\), so it remains to attain the upper bound. For \(x\neq 0\), define \[y_j=\frac{\sign(x_j)|x_j|^{p-1}}{\|x\|_p^{p-1}}.\] Because \((p-1)q=p\), \[\|y\|_q^q =\frac{\sum_j|x_j|^p}{\|x\|_p^p}=1, \qquad \langle x,y\rangle =\frac{\sum_j|x_j|^p}{\|x\|_p^{p-1}} =\|x\|_p.\] For \(p=1\), take \(y_j=\sign(x_j)\), which has \(\|y\|_\infty\leq 1\). For \(p=\infty\), choose an index \(j^\star\) with \(|x_{j^\star}|=\|x\|_\infty\) and take \(y=\sign(x_{j^\star})e_{j^\star}\).
Finally, \[\|x\|_1=\langle |x|,\mathbf 1\rangle \leq\|x\|_2\|\mathbf 1\|_2 =\sqrt d\,\|x\|_2,\] and \[\|x\|_2^2=\sum_{j=1}^d x_j^2 \leq d\|x\|_\infty^2.\]
Let \(A\) and \(\widehat A=A+E\) be symmetric \(d\times d\) matrices with \(\|E\|_{\op}\leq\epsilon\). Let \(\widehat v_1\) be a unit leading eigenvector of \(\widehat A\).
Bound \(|\lambda_k(\widehat A)-\lambda_k(A)|\) for every \(k\).
Show that \[\widehat v_1^\top A\widehat v_1 \geq\lambda_1(A)-2\epsilon.\] Interpret the result when \(A\) is a population covariance and \(\widehat A\) is a sample covariance.
Reveal solution
Weyl’s bound immediately gives \[|\lambda_k(\widehat A)-\lambda_k(A)|\leq\epsilon \quad\text{for every }k.\] For the second claim, compare the Rayleigh value at the same unit vector under \(A\) and \(\widehat A\), then compare their leading eigenvalues. Identify the reason for each transition; the complete argument follows.
1. Substitute the perturbation. \[\widehat v_1^\top A\widehat v_1 =\widehat v_1^\top\widehat A\widehat v_1 -\widehat v_1^\top E\widehat v_1.\] Use \(A=\widehat A-E\); the vector is held fixed in both terms.
2. Use the eigenvector identity and norm bound. \[\widehat v_1^\top A\widehat v_1 \geq\lambda_1(\widehat A)-\epsilon.\] Since \(\widehat A\widehat v_1=\lambda_1(\widehat A)\widehat v_1\) and \(\|\widehat v_1\|_2=1\), its Rayleigh value is \(\lambda_1(\widehat A)\). Cauchy–Schwarz and the definition of operator norm give \(|\widehat v_1^\top E\widehat v_1| \leq\|\widehat v_1\|_2\|E\widehat v_1\|_2 \leq\|E\|_{\op}\leq\epsilon\).
3. Apply Weyl to the leading eigenvalue. \[\widehat v_1^\top A\widehat v_1 \geq\lambda_1(\widehat A)-\epsilon \geq\lambda_1(A)-2\epsilon.\] Theorem 4 gives \(\lambda_1(\widehat A)\geq\lambda_1(A)-\epsilon\). This uses the mid-priority theorem statement, not its optional Courant–Fischer proof. Thus, operator-norm accuracy of the sample covariance implies eigenvalue accuracy and guarantees that the empirical leading direction captures population variance within \(2\epsilon\) of the optimum. Controlling the angle between the eigenvectors requires an additional eigengap condition and a result such as the Davis–Kahan theorem (an extension, not needed here).
For \(y\in\R\) and \(\lambda>0\), find the unique minimizer of \[f(\beta)=(y-\beta)^2+\lambda|\beta|.\] You may use the subgradient optimality condition, or work separately on \(\beta<0\), \(\beta=0\), and \(\beta>0\). Explain why the solution can be exactly zero.
Reveal solution
One can solve the problem without subgradients. On \(\beta>0\), differentiation gives \(2(\beta-y)+\lambda=0\), so \(\beta=y-\lambda/2\), which is positive exactly when \(y>\lambda/2\). If \(\beta<0\), differentiation gives \(2(\beta-y)-\lambda=0\), so \(\beta=y+\lambda/2\), which is negative exactly when \(y<-\lambda/2\). At \(\beta=0\), the left and right derivatives are \(-2y-\lambda\) and \(-2y+\lambda\), respectively. They straddle zero exactly when \(|y|\leq\lambda/2\). Combining the three cases, \[\widehat\beta =\sign(y)\left(|y|-\frac{\lambda}{2}\right)_+.\]
Optional alternate route (subgradients; not examined). The condition \[0\in 2(\beta-y)+\lambda\,\partial|\beta|\] produces the same three cases; at \(\beta=0\), it becomes \(0\in-2y+\lambda[-1,1]\). This is equivalent to \(|y|\leq\lambda/2\).
This is the soft-thresholding rule. The one-sided derivatives straddle zero for a whole interval of data values, \(|y|\leq\lambda/2\), giving the exact optimizer \(\widehat\beta=0\). The squared term is strictly convex, so the minimizer is unique.
References
What changed
October 19, 2026: Corrected notation, wording and cross-references after the course-wide errata review; refreshed the linked HTML and PDF editions.
October 14, 2026. Added issue-reporting links to the webpage and PDF. The mathematics and priority assignments are unchanged in this update.
Comments
Discuss an idea or ask a public question. Include a section or exercise number when relevant. For errors in the notes or website, Report an issue.
Public comments use Disqus. Enable JavaScript to load them.
Email the instructor for a private question or if comments are unavailable.