The Blessing of Dimensions: When Does the Nearest Neighbor Lie?

You have $n$ training points drawn i.i.d. uniformly from the $d$ -dimensional unit hypercube $[0,1]^d$ , and you want to predict at the origin $\mathbf{0}$ .

The 1-nearest neighbor classifier uses the single closest training point to make its prediction.

To "capture" a fraction $r$ of the data (i.e., so that the expected number of training points within a ball of radius $\ell$ around the origin is $rn$ ), the required edge length $\ell$ of a sub-cube satisfies:

$\ell = r^{1/d}.$

The puzzle: Suppose you want to use the nearest $r = 1\%$ of the data to make a local estimate. Compute $\ell$ for $d = 1, 2, 10$ and explain what this reveals about nearest-neighbor methods in high dimensions. What is the conceptual implication for the bias of 1-NN?

Note: Use $r = 0.01$ throughout.

Ridge Regression as Augmented OLS: The Data-Augmentation Trick

Recall that the ridge regression estimator for

y = X\beta + \varepsilon

minimizes

\text{RSS}_\lambda(\beta) = \|y - X\beta\|^2 + \lambda\|\beta\|^2.

Problem: Show that this is exactly equivalent to performing ordinary least squares (no penalty at all) on an augmented dataset

(\tilde{X}, \tilde{y})

, where

\tilde{X} = \begin{pmatrix} X \\ \sqrt{\lambda}\, I_p \end{pmatrix}, \qquad \tilde{y} = \begin{pmatrix} y \\ 0 \end{pmatrix}.

That is, show that

\hat{\beta}_{\text{ridge}} = (\tilde{X}^T \tilde{X})^{-1}\tilde{X}^T \tilde{y}

Bonus reflection: What does this say conceptually about what ridge regression is doing to the data?

Sunday, July 5, 2026

The Blessing of Dimensions: When Does the Nearest Neighbor Lie?

Ridge Regression as Augmented OLS: The Data-Augmentation Trick