45.06.05 · mathematical-statistics / 06-high-dimensional-regularization

Subset Selection and the Curse of Dimensionality

shipped3 tiersLean: none

Anchor (Master): Hastie, Tibshirani & Friedman 2009 The Elements of Statistical Learning 2e (Springer) Ch. 3 §3.3 and Ch. 18 (high-dimensional problems, p ≫ n); Berk, Brown, Buja, Zhang & Zhao 2013 Annals of Statistics 41 (valid post-selection inference); Donoho 2000 AMS Lecture (high-dimensional data analysis: the curses and blessings of dimensionality)

Intuition Beginner

Suppose you have a hundred possible predictors and you suspect only a few of them actually matter. The honest thing to do seems simple: try every possible handful of predictors, fit each one, and keep the combination that predicts best. This is subset selection, and it has two problems. The first is that the number of handfuls explodes. With a hundred predictors there are more than a billion billion billion combinations, far too many to ever check. The second is sneakier: the very act of picking the winner from a huge pile of candidates flatters that winner. Some combination will look great on your data by luck alone, and you will mistake luck for signal.

Because checking everything is impossible, people use greedy shortcuts. Forward selection starts with nothing and adds the single best predictor, then the next best given the first, and so on. Backward selection starts with everything and drops the least useful one at a time. These are fast, but they are jumpy: change a few data points and the chosen set can flip entirely. A predictor is either fully in or fully out, with nothing in between, so small wiggles in the data cause big jumps in the answer.

Compare this to the smooth approach of the previous units, where every predictor's weight is gently dialed up or down. Shrinkage moves continuously; selection moves in hard steps. The steps are what make selection unstable.

There is a second, deeper trouble lurking behind all of this, and it is purely about having many predictors at once. In high dimensions, space behaves in ways that defeat our everyday intuition. Points that you think of as "close" are almost all about the same distance apart, so the idea of a nearby neighbour stops meaning much. To cover the space with examples, you would need an absurd number of them. This is the curse of dimensionality, and it is the real reason that throwing more predictors at a problem so often backfires.

Visual Beginner

Two pictures sit at the heart of this unit. The first contrasts how selection and shrinkage move. The second shows how empty high-dimensional space is.

Method	How a predictor's weight changes as you tune	Behaviour when data wiggles
Best-subset / stepwise selection	jumps between zero and its full value (in or out)	unstable: the chosen set can flip
Shrinkage (ridge)	slides smoothly toward zero, never exactly off	stable: small data changes, small weight changes

The second table shows how much data you need just to keep your examples close together as the number of predictors grows. To capture a small fixed fraction of the space around a point, the side length of the little box you need swells toward covering the whole range.

Number of predictors	Side length needed to enclose 1% of the data volume
1	0.01
2	0.10
5	0.40
10	0.63

The takeaway: selection is a staircase, shrinkage is a ramp, and in many dimensions the staircase has to reach across almost the entire room to find anything to stand on.

Worked example Beginner

Here is the curse made concrete with arithmetic. Imagine your data live in a cube whose sides each run from $0$ to $1$ . You want to find a little sub-cube around a point that contains a fixed fraction $r$ of the data, say $r = 0.01$ , one percent. Assume the data are spread out evenly.

In one dimension the cube is just a line of length $1$ . To capture $1%$ of it you need a piece of length $0.01$ . Short and local, just as intuition says.

In two dimensions the cube is a square of area $1$ . A little sub-square with side $s$ has area $s \times s = s^{2}$ . To make that area equal $0.01$ you need $s^{2} = 0.01$ , so $s = 0.1$ . The side already grew tenfold.

In ten dimensions the cube has volume $1$ , and a little sub-cube with side $s$ has volume $s$ multiplied by itself ten times. To make that equal $0.01$ you need $s$ raised to the tenth power to be $0.01$ . Solving, $s = 0.0 1^{1/10} \approx 0.63$ .

So in ten dimensions, capturing a mere $1%$ of the data forces your "local" box to stretch across $63%$ of the full range in every direction. That is not local at all. What this tells us: in high dimensions there is no such thing as a small neighbourhood that still contains data. Any method that relies on looking at nearby points, such as nearest-neighbours, is forced to look far away, where the points no longer resemble the one you care about.

Check your understanding Beginner

Exercise (easy, multiple choice).

What is the main practical reason best-subset selection cannot be used directly with many predictors?

A. It always overfits the training data. B. The number of subsets to check grows explosively with the number of predictors. C. It can only handle one predictor at a time. D. It requires the predictors to be uncorrelated.

Hint

Count the possible subsets of a set with $p$ elements.

Answer

Option B. A set of $p$ predictors has $2^{p}$ subsets, a count that becomes astronomical well before $p$ reaches a hundred, so exhaustively fitting and comparing every subset is computationally out of reach. Feedback if correct: this combinatorial explosion is exactly why greedy shortcuts like forward and backward stepwise exist. Feedback if wrong: A and D describe other concerns, and C confuses best-subset selection with a single-variable procedure; the binding obstacle is the sheer number of subsets.

Formal definition Intermediate+

Fix a design matrix $X \in R^{n \times p}$ with columns indexed by ${1, \dots, p}$ and response $y \in R^{n}$ . A submodel is a subset $S \subseteq {1, \dots, p}$ ; writing $X_{S}$ for the columns in $S$ , the least-squares fit on $S$ has residual sum of squares $RSS (S) = min_{β_{S}} ∥ y - X_{S} β_{S} ∥^{2}$ . Best-subset selection of size $k$ solves the combinatorial problem

\hat{S}_{k} = ar g ∣ S ∣ = k min RSS (S),

and then a size $k$ is chosen by a complexity-penalized criterion such as $AIC$ , $BIC$ , or cross-validation 45.06.02. There are $(k p)$ candidates of size $k$ and $2^{p}$ submodels in total, so direct enumeration is infeasible for moderate $p$ ; the leaps-and-bounds algorithm prunes the search but is still exponential in the worst case.

Two greedy heuristics replace the search with a path. Forward stepwise selection begins with $\hat{S}^{(0)} = \emptyset$ and at each step adds the index that most reduces the residual sum of squares, $\hat{S}^{(m + 1)} = \hat{S}^{(m)} \cup {ar g min_{j \in / \hat{S}^{(m)}} RSS (\hat{S}^{(m)} \cup {j})}$ . Backward stepwise selection begins with the full model and at each step deletes the index whose removal least increases the residual sum of squares; it requires $n > p$ so the full model is defined. Forward stagewise selection is gentler still: it repeatedly identifies the predictor most correlated with the current residual and moves its coefficient a small step in that direction, leaving all others fixed, so the coefficient paths are built up in tiny increments rather than by full least-squares refits.

The discreteness of selection is its defining structural feature. The selection map $y \mapsto \hat{S}$ is piecewise constant: it takes finitely many values, and the data space partitions into regions on whose boundaries the selected set jumps. A selection estimator is therefore discontinuous in the data, in sharp contrast to ridge regression 45.06.03, whose coefficient path $\hat{β} (λ)$ is a continuous, indeed smooth, function of $y$ . The discontinuity is the source of selection's high variance: a small perturbation of $y$ can flip $\hat{S}$ to an entirely different subset, and averaging over the sampling distribution of $y$ then averages over qualitatively different fitted models.

Two geometric definitions organize the high-dimensional half. For points $x_{1}, \dots, x_{n}$ drawn i.i.d. uniformly on the unit ball $B^{d} \subset R^{d}$ , the median nearest-neighbour distance to the origin is the median of $min_{i} ∥ x_{i} ∥$ ; it is the radius of the smallest ball about the origin expected to contain a data point. Two random vectors $u, v$ are near-orthogonal when their normalized inner product $⟨ u, v ⟩ / (∥ u ∥ ∥ v ∥)$ is close to zero; in high dimensions this holds with high probability for independent isotropic vectors, with fluctuations controlled by the concentration inequalities of 45.05.01 and 40.07.05.

Counterexamples to common slips

Forward stepwise need not find the best subset of its own size. The greedy path is not guaranteed to pass through $\hat{S}_{k}$ ; a predictor that is useless alone but decisive in combination with another can be passed over forever. Greedy optimality is a heuristic, not a theorem.
Selection is not a continuous limit of shrinkage. Ridge never sets a coefficient exactly to zero, so it cannot reproduce a hard selection at any finite penalty; the discontinuity of $y \mapsto \hat{S}$ is a genuine difference, not a tuning artifact. The lasso 45.06.06 is the object that interpolates, by being continuous yet capable of exact zeros.
The curse is not merely "more parameters, more overfitting". Even with the true model known, density and distance estimation degrade with dimension because the geometry itself thins out the data; the curse is about the ambient space, not only about model complexity.
Distance concentration does not say all points coincide. Pairwise distances concentrate around a common value in relative terms; the absolute spread can still grow. What collapses is the contrast between nearest and farthest, which is what nearest-neighbour methods exploit.

Key theorem with proof Intermediate+

Theorem (median nearest-neighbour distance and the emptiness of high-dimensional neighbourhoods). Let $x_{1}, \dots, x_{n}$ be i.i.d. uniform on the unit ball $B^{d} = {x \in R^{d} : ∥ x ∥ \leq 1}$ . The median distance from the origin to its nearest data point is

med (1 \leq i \leq n min ∥ x_{i} ∥) = (1 - 2^{- 1/ n})^{1/ d} .

Consequently, for $n = 500$ and $d = 10$ the median nearest-neighbour distance is about $0.52$ , more than halfway to the boundary: with five hundred points the typical nearest neighbour of the centre lies past the midradius, not nearby.

Proof. A single uniform point $x$ on $B^{d}$ has $Pr (∥ x ∥ \leq t) = vol (t B^{d}) / vol (B^{d}) = t^{d}$ for $t \in [0, 1]$ , because the ball of radius $t$ scales every coordinate by $t$ and volume scales by $t^{d}$ . Hence $Pr (∥ x ∥ > t) = 1 - t^{d}$ . With $n$ independent points, the nearest distance $R = min_{i} ∥ x_{i} ∥$ exceeds $t$ exactly when all $n$ points do, so by independence

Pr (R > t) = (1 - t^{d})^{n} .

The median $m$ of $R$ solves $Pr (R > m) = \frac{1}{2}$ , that is $(1 - m^{d})^{n} = \frac{1}{2}$ . Taking $n$ -th roots gives $1 - m^{d} = 2^{- 1/ n}$ , so $m^{d} = 1 - 2^{- 1/ n}$ and $m = (1 - 2^{- 1/ n})^{1/ d}$ , as claimed. For $n = 500$ , $2^{- 1/500} = e^{- (l n 2) /500} \approx 1 - 0.001386 = 0.998614$ , so $1 - 2^{- 1/500} \approx 0.001386$ ; raising to the power $1/10$ gives $m \approx (0.001386)^{0.1} \approx e^{0.1 l n (0.001386)} = e^{0.1 \times (- 6.582)} = e^{- 0.658} \approx 0.518$ . $□$

Bridge. This computation builds toward the operational failure of every local method in the chapter, because a nearest neighbour that sits past the midradius is not a local datum at all, so $k$ -nearest-neighbour regression and kernel density estimation lose the locality on which their low bias depends. The foundational reason is the volume law $Pr (∥ x ∥ \leq t) = t^{d}$ : high-dimensional volume hugs the boundary, which is exactly the thin-shell phenomenon proved in the advanced section and is dual to the distance-concentration statement that nearest and farthest neighbours become indistinguishable. The same exponent $d$ appears again in 45.06.06, where sparsity assumptions are precisely what let regularized selection beat the curse by acting as though the effective dimension were the small number of relevant predictors rather than the full $p$ . Putting these together, the median-distance identity is the quantitative skeleton on which the case for structure-exploiting regularization, rather than brute-force local fitting, is built; this is exactly the bias-variance trade-off of 45.06.02 read through the geometry of the sample space.

Exercises Intermediate+

Exercise 3 (medium, symbolic).

For two independent vectors $u, v$ uniform on the unit sphere $S^{d - 1} \subset R^{d}$ , show that $E [⟨ u, v ⟩] = 0$ and $E [⟨ u, v ⟩^{2}] = 1/ d$ , and interpret the consequence for near-orthogonality as $d \to \infty$ .

Hint

Condition on $v$ and use rotational symmetry of $u$ ; then use $\sum_{j} u_{j}^{2} = 1$ and exchangeability of the coordinates of $u$ .

Answer

Condition on $v$ . By rotational symmetry rotate so $v = e_{1}$ ; then $⟨ u, v ⟩ = u_{1}$ . The first coordinate of a uniform sphere point has mean zero by the symmetry $u_{1} \mapsto - u_{1}$ , so $E [⟨ u, v ⟩] = 0$ . For the second moment, $E [u_{1}^{2}] = \frac{1}{d} E [\sum_{j = 1}^{d} u_{j}^{2}] = \frac{1}{d} E [1] = \frac{1}{d}$ by exchangeability of the coordinates and $∥ u ∥ = 1$ . Thus $⟨ u, v ⟩$ has mean $0$ and standard deviation $1/ d$ , so the angle between two independent random unit vectors concentrates at $9 0^{\circ}$ with fluctuation shrinking like $1/ d$ : in high dimensions, independent directions are nearly orthogonal.

Exercise 5 (medium, short-answer).

Explain why forward stepwise selection can fail to recover the best two-predictor subset, and give a schematic example.

Hint

Think of two predictors that are each weakly related to the response alone but jointly determine it (an XOR-like or cancellation structure).

Answer

Forward stepwise commits to the single best predictor first and never reconsiders. If predictors $X_{1}$ and $X_{2}$ are each only weakly correlated with $y$ on their own but together explain it almost perfectly — for instance $y \approx X_{1} - X_{2}$ with $X_{1}, X_{2}$ strongly correlated, so each alone tracks $y$ poorly while their difference tracks it well — the first step may instead admit some $X_{3}$ that has a higher marginal correlation. Once $X_{3}$ is in, the path is anchored to it, and the genuinely best pair ${X_{1}, X_{2}}$ may never be selected together. Best-subset selection would find ${X_{1}, X_{2}}$ by evaluating it directly; the greedy path cannot, because its myopic single-step criterion is blind to joint effects. This is the greedy-versus-exhaustive gap that makes stepwise a heuristic.

Exercise 6 (hard, symbolic).

(Selection-induced optimism.) Let $Z_{1}, \dots, Z_{p}$ be i.i.d. $N (0, 1)$ and $M = max_{j} Z_{j}$ . Show $E [M] > 0$ and that $E [M]$ grows without bound as $p \to \infty$ (the bound $E [M] \leq 2 ln p$ may be cited). Explain why this is the mathematical heart of why the selected model's apparent fit is optimistic.

Hint

Each $Z_{j}$ has mean zero, but the maximum of several mean-zero variables is positive in expectation. Relate $Z_{j}$ to per-predictor "signal" statistics computed on noise.

Answer

Since $M = max_{j} Z_{j} \geq Z_{1}$ and the inequality is strict on a positive-probability event, $E [M] \geq E [Z_{1}] = 0$ with strict inequality once $p \geq 2$ . For the growth, the standard sub-Gaussian maximal bound gives $E [M] \leq 2 ln p$ , and a matching lower bound of the same order holds, so $E [M] ≍ 2 ln p \to \infty$ . Now read $Z_{j}$ as the standardized strength-of-association statistic of predictor $j$ when in truth no predictor carries signal: each is mean-zero noise, yet selection keeps the largest, whose expected value is $2 ln p$ , not $0$ . The fitted model therefore reports an association that is pure selection artifact, and naive inference that ignores the maximization step understates the variability and overstates the effect. This is selection-induced optimism, and it is why post-selection confidence intervals computed as if the model were fixed in advance fail to cover at their nominal rate.

Exercise 7 (hard, short-answer).

Contrast the variance behaviour of best-subset selection and ridge regression as functions of the data, using the discontinuity of the selection map, and explain why the lasso is often preferred to both.

Hint

Selection is piecewise constant in $y$ ; ridge is smooth in $y$ . What does a discontinuous estimator do to variance, and what does the lasso combine?

Answer

Best-subset selection is a piecewise-constant function of $y$ : the data space is partitioned into regions, and across a region boundary the chosen subset jumps. An estimator that jumps has high sampling variance, because resampling $y$ frequently lands on the other side of a boundary and returns a qualitatively different model; the fitted coefficients inherit this instability. Ridge, by contrast, is a smooth function of $y$ — the map $y \mapsto \hat{β} (λ)$ is linear — so small perturbations produce small changes and the variance is controlled, at the cost of never producing exact zeros and hence never giving an interpretable sparse model. The lasso 45.06.06 is preferred because it is continuous in $y$ (soft-thresholding has no jumps) yet still produces exact zeros, so it delivers the sparsity of selection with a variance closer to that of shrinkage. It is, in effect, the convex relaxation that turns the discontinuous combinatorial problem into a continuous one without abandoning variable selection.

Advanced results Master

The volume law underlies a sharp concentration statement. For $x$ uniform on $B^{d}$ , $Pr (∥ x ∥ \leq t) = t^{d}$ , so the density of the radius $R$ is $d t^{d - 1}$ on $[0, 1]$ , with mean $d / (d + 1) \to 1$ and standard deviation of order $1/ d$ . The mass therefore collapses onto a thin shell at the boundary: for any fixed $ϵ > 0$ , $Pr (R \leq 1 - ϵ) = (1 - ϵ)^{d} \to 0$ . A $(1 - δ)$ fraction of the ball's volume lies within relative distance $O (d^{- 1} ln (1/ δ))$ of the surface, the thin-shell phenomenon. The Gaussian analogue is cleaner: for $x \sim N (0, I_{d})$ the squared norm $∥ x ∥^{2}$ is $χ_{d}^{2}$ with mean $d$ and standard deviation $2 d$ , so $∥ x ∥$ concentrates at $d$ with $O (1)$ fluctuation, and by the sub-exponential tail bounds of 45.05.01, $Pr (∣∥ x ∥^{2} - d ∣ \geq t) \leq 2 exp (- c min (t^{2} / d, t))$ . High-dimensional Gaussian mass lives on a sphere of radius $d$ , the Gaussian annulus.

Distance concentration is the consequence that breaks nearest-neighbour methods. For i.i.d. data with independent coordinates of bounded variance, the pairwise squared distance $∥ X - Y ∥^{2} = \sum_{j = 1}^{d} (X_{j} - Y_{j})^{2}$ is a sum of $d$ independent bounded-variance terms, so by the law of large numbers it concentrates at $d E [(X_{1} - Y_{1})^{2}]$ with fluctuations of order $d$ controlled by the bounded-differences inequality of 40.07.05. The ratio of the largest to the smallest pairwise distance among $n$ points therefore tends to $1$ : $(dist_{m a x} - dist_{m i n}) / dist_{m i n} \to 0$ in probability as $d \to \infty$ with $n$ fixed. The notion "nearest neighbour" loses contrast, and the relevance of the nearest point over a random point vanishes. This is the precise statement behind the worked example's empty neighbourhoods, and it explains why $k$ -NN regression bias grows with dimension: the $k$ nearest points are at almost the same distance as arbitrary points, so averaging over them is averaging over a region as large as the whole support.

Near-orthogonality has a quantitative concentration form. For independent $u, v$ uniform on $S^{d - 1}$ , the inner product $⟨ u, v ⟩$ has mean $0$ and variance $1/ d$ (Exercise 3), and it is sub-Gaussian with parameter $O (1/ d)$ , so $Pr (∣⟨ u, v ⟩∣ \geq t) \leq 2 e^{- d t^{2} /2}$ . The number of pairwise near-orthogonal vectors one can pack grows exponentially in $d$ : there exist $e^{c d}$ unit vectors with pairwise inner products below any fixed $ϵ$ , the Johnson-Lindenstrauss regime. This is the blessing of dimensionality: random projection into a space of dimension $O (ϵ^{- 2} ln n)$ preserves all pairwise distances among $n$ points to relative error $ϵ$ with high probability, because the projected coordinates concentrate. The same concentration that empties neighbourhoods also makes high-dimensional geometry regular and predictable, so that low-dimensional structure, when present, can be recovered.

Selection-induced optimism is the statistical curse paired to the geometric one. When a model is chosen by minimizing a fit criterion over many candidates, the in-sample error of the winner understates its true error by more than the fixed-model optimism of 45.06.02, because the selection step actively seeks the most favourable noise realization. With $p$ pure-noise candidate statistics, the selected maximum has expectation of order $2 ln p$ rather than $0$ (Exercise 6), so naive post-selection confidence intervals and p-values are invalid: they are computed as though the model were specified in advance, ignoring the data-dependence of $\hat{S}$ . Valid post-selection inference (Berk, Brown, Buja, Zhang and Zhao, 2013) restores coverage by widening intervals to be simultaneously valid over all submodels the procedure could have chosen, at a multiplicative cost in width that itself grows like $2 ln p$ . The discreteness of selection that drives its instability is the same discreteness that makes its inference intractable; both are cured, or at least softened, by passing to the continuous convex surrogate of 45.06.06.

Synthesis. The foundational reason a single circle of ideas governs subset selection, the curse of dimensionality, and post-selection inference is that all three are consequences of measure concentration in high dimensions, and the bias-variance decomposition of 45.06.02 reads each one as a motion along the same trade-off. The volume law $t^{d}$ is the central insight: it forces mass onto a thin shell, which is exactly the distance-concentration statement that nearest and farthest neighbours become indistinguishable, and this is dual to the near-orthogonality of random directions that simultaneously empties neighbourhoods and, through Johnson-Lindenstrauss, makes random projection faithful. Putting these together, the curse and the blessing are one phenomenon viewed from two sides — concentration destroys locality and creates regularity at once — so the right response is not brute-force local fitting but exploiting structure such as sparsity. The discreteness of selection generalises the same lesson on the statistical side: best-subset selection is the combinatorial extreme whose discontinuity in the data produces both high variance and invalid naive inference, and the bridge to a workable method is the convex relaxation of 45.06.06, which keeps exact zeros while restoring continuity. This is exactly the passage from a staircase to a ramp, promoted from the one-coordinate picture of shrinkage in 45.06.03 to the full geometry of the sample space.

Full proof set Master

The median-distance identity is proved in full in the Key theorem section, and the near-orthogonality moments and the selection-optimism growth bound in Exercises 3 and 6. The remaining Master claims are recorded here.

Proposition 1 (Thin-shell concentration for the uniform ball). For $x$ uniform on $B^{d}$ and any $ϵ \in (0, 1)$ , $Pr (∥ x ∥ \leq 1 - ϵ) = (1 - ϵ)^{d}$ , so the fraction of volume outside the shell of relative thickness $ϵ$ decays exponentially in $d$ , and a $(1 - δ)$ fraction of the volume lies within relative distance $ϵ = d^{- 1} ln (1/ δ) + O (d^{- 2})$ of the surface.

Proof. The radius law $Pr (∥ x ∥ \leq t) = t^{d}$ on $[0, 1]$ follows from volume scaling: $vol (t B^{d}) = t^{d} vol (B^{d})$ because dilation by $t$ multiplies the Jacobian determinant by $t^{d}$ . Setting $t = 1 - ϵ$ gives the stated probability $(1 - ϵ)^{d}$ . To locate the $(1 - δ)$ shell, solve $(1 - ϵ)^{d} = δ$ for the inner radius, i.e. the volume inside $1 - ϵ$ equals $δ$ : $d ln (1 - ϵ) = ln δ$ , so $ln (1 - ϵ) = \frac{1}{d} ln δ = - \frac{1}{d} ln (1/ δ)$ . Expanding $ln (1 - ϵ) = - ϵ - ϵ^{2} /2 - \dots$ and inverting gives $ϵ = \frac{1}{d} ln (1/ δ) + O (d^{- 2})$ . Hence the inner ball of radius $1 - ϵ$ holds only a $δ$ fraction of the volume, and the complementary $(1 - δ)$ fraction sits in a shell of relative thickness $O (d^{- 1} ln (1/ δ))$ . $□$

Proposition 2 (Gaussian norm concentration on the annulus). For $x \sim N (0, I_{d})$ , $E ∥ x ∥^{2} = d$ , $Var (∥ x ∥^{2}) = 2 d$ , and for all $t \geq 0$ , $Pr (∥ x ∥^{2} - d \geq t) \leq 2 exp (- c min (t^{2} / d, t))$ for an absolute constant $c > 0$ ; consequently $∥ x ∥ = d (1 + O_{P} (d^{- 1/2}))$ .

Proof. The coordinates $x_{j}$ are i.i.d. $N (0, 1)$ , so $∥ x ∥^{2} = \sum_{j} x_{j}^{2}$ is a sum of $d$ i.i.d. $χ_{1}^{2}$ variables, whence $E ∥ x ∥^{2} = d \cdot 1 = d$ and $Var (∥ x ∥^{2}) = d \cdot Var (x_{1}^{2}) = d \cdot 2 = 2 d$ , using $Var (χ_{1}^{2}) = 2$ . Each $x_{j}^{2} - 1$ is sub-exponential (a centered $χ_{1}^{2}$ ), so the sum obeys the Bernstein-type tail of 45.05.01: $Pr (∣ \sum_{j} (x_{j}^{2} - 1) ∣ \geq t) \leq 2 exp (- c min (t^{2} / d, t))$ , which is the stated bound. Writing $∥ x ∥ = d 1 + (∥ x ∥^{2} - d) / d$ and expanding the square root, the relative fluctuation is $O_{P} (2 d / d) = O_{P} (d^{- 1/2})$ , so the norm concentrates on the sphere of radius $d$ . $□$

Proposition 3 (Distance contrast vanishes). Let $X, Y^{(1)}, \dots, Y^{(n)}$ be i.i.d. in $R^{d}$ with i.i.d. coordinates of mean $μ$ , variance $σ^{2} > 0$ , and finite fourth moment, with $n$ fixed. Then $(max_{k} ∥ X - Y^{(k)} ∥ - min_{k} ∥ X - Y^{(k)} ∥) / min_{k} ∥ X - Y^{(k)} ∥ \to 0$ in probability as $d \to \infty$ .

Proof. For each $k$ , $∥ X - Y^{(k)} ∥^{2} = \sum_{j = 1}^{d} (X_{j} - Y_{j}^{(k)})^{2}$ is a sum of $d$ i.i.d. terms with common mean $ν := E [(X_{1} - Y_{1}^{(k)})^{2}] = 2 σ^{2} > 0$ and finite variance, so by the law of large numbers $\frac{1}{d} ∥ X - Y^{(k)} ∥^{2} \to ν$ in probability, and by the bounded-fourth-moment central-limit scaling the fluctuation of $∥ X - Y^{(k)} ∥^{2}$ about $d ν$ is $O_{P} (d)$ , controlled uniformly over the fixed finite set of $n$ indices by 40.07.05. Thus $∥ X - Y^{(k)} ∥ = d ν (1 + O_{P} (d^{- 1/2}))$ for every $k$ simultaneously. The maximum and minimum over the $n$ distances therefore both equal $d ν (1 + O_{P} (d^{- 1/2}))$ , so their difference is $O_{P} (d ν \cdot d^{- 1/2}) = O_{P} (1)$ while the minimum is of order $d$ ; the ratio is $O_{P} (d^{- 1/2}) \to 0$ . $□$

Proposition 4 (Selection map is discontinuous; ridge is continuous). The best-subset selection map $y \mapsto \hat{S} (y)$ is piecewise constant and discontinuous on a set of positive $(d - 1)$ -dimensional measure, whereas the ridge map $y \mapsto \hat{β} (λ)$ is continuous (indeed linear) for every $λ > 0$ .

Proof. For fixed $X$ and model size $k$ , $\hat{S} (y) = ar g min_{∣ S ∣ = k} ∥(I - H_{S}) y ∥^{2}$ where $H_{S}$ is the projection onto the column span of $X_{S}$ . Each $∥(I - H_{S}) y ∥^{2}$ is a continuous quadratic in $y$ , and $\hat{S} (y)$ selects the index of the smallest among finitely many such quadratics; the selected index is constant on each open region where one quadratic is strictly smallest and jumps across the boundaries ${y : ∥(I - H_{S}) y ∥^{2} = ∥(I - H_{S^{'}}) y ∥^{2}}$ , which are quadric hypersurfaces of positive surface measure. Hence $\hat{S}$ is piecewise constant with genuine jumps, so it is discontinuous. By contrast $\hat{β} (λ) = (X^{⊤} X + λ I)^{- 1} X^{⊤} y$ is a fixed linear map applied to $y$ (the matrix is invertible for $λ > 0$ 45.06.03), and every linear map is continuous; small changes in $y$ give proportionally small changes in $\hat{β} (λ)$ . The discontinuity of selection versus the continuity of shrinkage is therefore structural, not a matter of tuning. $□$

Connections Master

The bias-variance decomposition 45.06.02 is the lens through which both halves of this unit are read: the curse of dimensionality inflates the variance of local methods because their effective neighbourhoods are forced to span the whole support, raising bias as well, while the discreteness of subset selection is a variance phenomenon — a discontinuous estimator has high sampling variance — so the staircase-versus-ramp contrast is a bias-variance contrast in disguise.

Ridge regression and shrinkage 45.06.03 is the continuous counterpoint to selection developed here: ridge's coefficient path is a smooth, always-defined function of the data, which is exactly the stability that the piecewise-constant selection map lacks, and the present unit's Proposition 4 makes the discontinuity-versus-continuity distinction precise so that the case for shrinkage over explicit selection is a theorem rather than a preference.

The lasso and sparse selection 45.06.06 is the resolution this unit motivates: it is the convex relaxation that keeps the exact zeros of subset selection while restoring continuity in the data, so it inherits the interpretability of selection and the stability of shrinkage, and the curse-of-dimensionality geometry here is precisely what its sparsity assumptions are designed to defeat by acting on the small effective dimension rather than the full $p$ .

Bernstein and sub-exponential concentration 45.05.01 supplies the tail bounds behind the Gaussian-annulus and thin-shell statements: the squared norm of a high-dimensional Gaussian is a sum of centered $χ_{1}^{2}$ variables whose sub-exponential tails give the concentration on the sphere of radius $d$ used in Proposition 2 and in the distance-concentration argument.

Azuma and bounded-differences concentration 40.07.05 controls the fluctuation of pairwise distances as sums of $d$ independent coordinate contributions, the engine of the distance-contrast collapse in Proposition 3; the same martingale/bounded-differences machinery is what makes the concentration uniform over the finitely many neighbours.

PAC learning and empirical risk minimization 45.07.01 is where selection-induced optimism reappears as the generalization gap: choosing a hypothesis by minimizing empirical risk over a class is the learning-theoretic analogue of choosing a subset by minimizing residual sum of squares, and the $2 ln p$ maximal-inequality bound of Exercise 6 is the finite-class union-bound penalty $lo g ∣ H ∣/ m$ that quantifies how much the selected model's empirical fit overstates its true performance.

Historical & philosophical context Master

The phrase curse of dimensionality is due to Richard Bellman, who coined it in his 1957 monograph on dynamic programming to describe the exponential growth in the number of grid points needed to discretize a high-dimensional state space; the same exponential scaling reappears in density estimation, where the number of samples required to estimate a smooth density to fixed accuracy grows exponentially in the dimension. Subset selection as a regression methodology was systematized in the 1960s and 1970s alongside the computing power to attempt it, with the Furnival-Wilson leaps-and-bounds algorithm (1974) making best-subset search feasible for moderate $p$ by branch-and-bound pruning; forward and backward stepwise procedures, older and cheaper, were already standard practice and were collected with their pitfalls into the modern account of Hastie, Tibshirani and Friedman ^{[Hastie 2009]}.

The recognition that selection corrupts subsequent inference matured slowly. The danger of computing confidence intervals and tests on a model chosen by the same data was known informally for decades, but a framework giving valid post-selection inference — confidence intervals simultaneously correct over every model the procedure might have selected — was provided by Richard Berk, Lawrence Brown, Andreas Buja, Kai Zhang and Linda Zhao ^{[Berk 2013]}, whose PoSI constants make the $2 ln p$ optimism of the selected maximum into an explicit width correction. David Donoho's millennium lecture ^{[Donoho 2000]} reframed the whole subject by naming the blessing alongside the curse: the very measure-concentration that empties neighbourhoods also enforces an asymptotic geometric regularity — random projections preserve distances, independent directions are nearly orthogonal — that makes high-dimensional inference tractable precisely when low-dimensional structure such as sparsity is present, the principle on which the lasso and compressed sensing rest.

Bibliography Master

@book{bellman1957dynamic,
  author    = {Bellman, Richard E.},
  title     = {Dynamic Programming},
  publisher = {Princeton University Press},
  year      = {1957}
}

@article{furnival1974regressions,
  author  = {Furnival, George M. and Wilson, Robert W.},
  title   = {Regressions by Leaps and Bounds},
  journal = {Technometrics},
  volume  = {16},
  number  = {4},
  pages   = {499--511},
  year    = {1974}
}

@book{hastie2009elements,
  author    = {Hastie, Trevor and Tibshirani, Robert and Friedman, Jerome},
  title     = {The Elements of Statistical Learning: Data Mining, Inference, and Prediction},
  edition   = {2},
  publisher = {Springer},
  year      = {2009},
  note      = {Chapter 3 §3.3 subset selection; Chapter 2 §2.5 curse of dimensionality; Chapter 18 high-dimensional problems}
}

@article{berk2013posi,
  author  = {Berk, Richard and Brown, Lawrence and Buja, Andreas and Zhang, Kai and Zhao, Linda},
  title   = {Valid Post-Selection Inference},
  journal = {The Annals of Statistics},
  volume  = {41},
  number  = {2},
  pages   = {802--837},
  year    = {2013}
}

@incollection{donoho2000highdim,
  author    = {Donoho, David L.},
  title     = {High-Dimensional Data Analysis: The Curses and Blessings of Dimensionality},
  booktitle = {AMS Math Challenges of the 21st Century},
  publisher = {American Mathematical Society},
  year      = {2000}
}

@article{johnson1984extensions,
  author  = {Johnson, William B. and Lindenstrauss, Joram},
  title   = {Extensions of Lipschitz Mappings into a Hilbert Space},
  journal = {Contemporary Mathematics},
  volume  = {26},
  pages   = {189--206},
  year    = {1984}
}

Prerequisites

45.06.02
45.05.01
40.07.05

Tier anchors

beginner: Hastie, Tibshirani & Friedman 2009 The Elements of Statistical Learning 2e (Springer) §3.3 (subset selection, forward/backward stepwise) and §2.5 (the curse of dimensionality, the local-neighbourhood picture); James, Witten, Hastie & Tibshirani 2013 An Introduction to Statistical Learning (Springer) §6.1 (best-subset and stepwise selection, informally)
intermediate: Hastie, Tibshirani & Friedman 2009 The Elements of Statistical Learning 2e (Springer) §3.3-3.4 (best-subset selection as a combinatorial problem, forward/backward/stagewise greedy heuristics, the discreteness/instability of selection versus the continuity of shrinkage) and §2.5 (curse-of-dimensionality calculations: median nearest-neighbour distance, edge fraction of a hypercube)
master: Hastie, Tibshirani & Friedman 2009 The Elements of Statistical Learning 2e (Springer) Ch. 3 §3.3 and Ch. 18 (high-dimensional problems, p ≫ n); Berk, Brown, Buja, Zhang & Zhao 2013 Annals of Statistics 41 (valid post-selection inference); Donoho 2000 AMS Lecture (high-dimensional data analysis: the curses and blessings of dimensionality)

References

Hastie, T., Tibshirani, R. & Friedman, J. — The Elements of Statistical Learning (2nd ed.) · Springer, 2009. Ch. 3 §3.3 (subset selection: best-subset via leaps-and-bounds, forward/backward stepwise, forward stagewise; the discreteness of selection and its high variance) and §3.4 (shrinkage as the continuous alternative); Ch. 2 §2.5 (the curse of dimensionality: median distance to the nearest neighbour 1 - (1/2)^{1/N} in the unit ball, the fraction of a hypercube near its boundary, sampling sparsity); Ch. 18 (high-dimensional problems p ≫ n).
Berk, R., Brown, L., Buja, A., Zhang, K. & Zhao, L. — Valid Post-Selection Inference · Annals of Statistics 41 (2), 802-837 (2013). Selection-induced optimism / post-selection inference: naive confidence intervals and p-values computed on a model chosen by looking at the data are invalid; the PoSI framework gives simultaneous-over-all-submodels constants that restore coverage.
Donoho, D. L. — High-Dimensional Data Analysis: The Curses and Blessings of Dimensionality · AMS Math Challenges of the 21st Century lecture (2000). The curse (volume concentration, distance concentration, sample sparsity, the breakdown of local methods) and the blessing (measure concentration / asymptotic geometric regularity that makes high-dimensional inference tractable when structure such as sparsity is present).

Estimated time

beginner: 25m
intermediate: 55m
master: 90m