# high-dimensional regime

*Entry of the [Dictionary of Applied Machine Learning](https://dictionaryofml.org) (course edition), by Alexander Jung, Aalto University. CC BY 4.0. Updated 2026-11-19. [HTML](https://dictionaryofml.org/terms/highdimregime.html) · [typeset PDF](https://dictionaryofml.org/terms/highdimregime.pdf) · [LaTeX](https://dictionaryofml.org/terms/highdimregime.tex) · [Python demo](https://dictionaryofml.org/terms/highdimregime.py) · [notebook](https://dictionaryofml.org/terms/highdimregime.ipynb)*

Math is LaTeX with the book's macros expanded, so no notation package is needed to read it.

## Abstract

A machine learning method operates in the high-dimensional regime when the effective dimension of its hypothesis space exceeds the sample size $m$ of the training set. For a linear model, the regime begins where the number $d$ of features passes the number $m$ of data points. The feature matrix then has rank at most $m$, so the least squares solution is not unique and every solution interpolates the training set. A training error of zero therefore carries no information about the risk, so the regime removes the usual evidence about generalization. Regularization and dimensionality reduction restore a usable method, the first by adding a penalty term to the training error and the second by shrinking the hypothesis space. High-dimensional statistics develops theory and methods for this regime, and its guarantees need a structural assumption such as sparsity.

## Definition

Consider a weather service at Krems an der Donau (Austria) that predicts the maximum daytime temperature of a day from the maxima of the previous $d$ days. Each day is a data point with feature vector ${\mathbf x} \in
\mathbb{R}^{d}$ and label $y \in \mathbb{R}$, and a linear model $h({\mathbf x}) =
{\mathbf w}^{\top} {\mathbf x}$ is learned by least squares on a training set $\mathcal{D}^{(\rm train)}$ of $m = 30$ days of $2023$. For $d = 1$, the training error is $12.4$ and the validation error on the validation set $\mathcal{D}^{(\rm val)}$ of the $366$ days of $2024$ is $10.1$ squared degrees. For $d = 29$, the two numbers are $1.7$ and $100.4$, and for $d = 30$ they are $0$ and $13444$. Once the number of features reaches the number of data points in $\mathcal{D}^{(\rm train)}$, the training error carries no information about the loss on days outside $\mathcal{D}^{(\rm train)}$. Fig. 1 draws both errors for every $d$ from $1$ to $60$.

![Figure 1 of the entry highdimregime](https://dictionaryofml.org/terms/fig/highdimregime-fig1.svg)

*Figure 1: The training error (solid curve) and the validation error (dashed curve) of a linear model that predicts the maximum daytime temperature of a day at Krems from the maxima of the previous $d$ days, learned by least squares on $m = 30$ days of $2023$ and evaluated on the $366$ days of $2024$. The training error is drawn at the axis floor $10^{-3}$ wherever it is zero. The dotted line marks the feature count $d = m = 30$ at which the high-dimensional regime begins. Data generated by pythondemos/highdimregime.py*

A machine learning method operates in the high-dimensional regime when the effective dimension of its hypothesis space $\mathcal{H}$ exceeds the sample size $m$ of the training set,

\begin{equation}
\tag{1}
d_{\rm eff} \left( \mathcal{H} \right) > m \text{.}
\end{equation}

For the linear model above, the condition Eq. (1) reads $d >
m$. Empirical risk minimization with the squared error loss delivers a solution of the least squares problem

\begin{equation}
\tag{2}
\min_{{\mathbf w} \in \mathbb{R}^{d}}
\frac{1}{m} \sum_{r=1}^{m}
\big( y^{(r)} - {\mathbf w}^{\top}
{\mathbf x}^{(r)} \big)^{2} \text{.}
\end{equation}

Here, the feature matrix ${\mathbf X} \in
\mathbb{R}^{m \times d}$ stacks the feature vectors of $\mathcal{D}^{(\rm train)}$ as its rows and the vector ${\mathbf y} \in \mathbb{R}^{m}$ stacks their labels.

The rank of ${\mathbf X}$ is at most $m$, so for $d > m$ the nullspace of ${\mathbf X}$ holds a nonzero vector and the solution of the least squares problem Eq. (2) is not unique: its minimizers form an affine set of dimension at least $d - m$. The pseudoinverse picks the one of smallest Euclidean norm, $\widehat{{\mathbf w}} =
{{\mathbf X}}^{+} {\mathbf y}$. Every minimizer drives the training error to zero, which is interpolation of $\mathcal{D}^{(\rm train)}$. The curse of dimensionality is a separate consequence of a large $d$: the data points spread thin over the feature space $\mathbb{R}^{d}$ however many of them there are, while the high-dimensional regime compares two counts.

Generalization is the performance of a learned hypothesis on data points outside $\mathcal{D}^{(\rm train)}$, and the regime removes the evidence that a small training error usually provides about it. A hypothesis that interpolates $\mathcal{D}^{(\rm train)}$ has a training error of zero whichever labels the data points of $\mathcal{D}^{(\rm train)}$ carry, so a zero training error leaves the risk undetermined and overfitting cannot be diagnosed from $\mathcal{D}^{(\rm train)}$ alone. A large artificial neural network is trained in the same regime, with far more trainable model parameters than data points (Zhang et al., 2017, Sect. 1). A deep network reaches a training error of zero even on a training set whose labels have been replaced by random ones (Zhang et al., 2017, Sect. 2). Learning theory measures the size of $\mathcal{H}$ by its Vapnik–Chervonenkis dimension and by its Rademacher complexity. The sample size that a generalization guarantee needs grows in proportion to the Vapnik–Chervonenkis dimension (Shalev-Shwartz and Ben-David, 2014, Thm. 6.8).

Two routes restore a usable method on the same features, and both are forms of regularization. Adding the penalty term $\alpha \left\lVert {\mathbf w} \right\rVert_{2}^{2}$ to the training error gives ridge regression. With $\alpha
= 100$, the validation error of the weather example stays between $10.2$ and $22.9$ squared degrees for every $d$ from $1$ to $60$. Dimensionality reduction shrinks $\mathcal{H}$ instead: least squares on the first $d' = 5$ principal directions of the feature vectors of $\mathcal{D}^{(\rm train)}$, which is principal component analysis, keeps the validation error between $9.8$ and $22.1$. At $d = m$ neither learned hypothesis interpolates $\mathcal{D}^{(\rm train)}$: the training error is $4.2$ with the penalty term and $11.2$ after the reduction. Fig. 2 draws the validation error of both against the validation error of least squares on all $d$ features.

![Figure 2 of the entry highdimregime](https://dictionaryofml.org/terms/fig/highdimregime-fig2.svg)

*Figure 2: The validation error of the same linear model at Krems against the number $d$ of features, for least squares (dashed curve), for least squares with the penalty term at $\alpha = 100$ (solid curve), and for least squares on the first $d' = 5$ principal directions (dotted curve). Data generated by pythondemos/highdimregime.py*

High-dimensional statistics is the branch of mathematical statistics that develops theory and methods for this regime (Bühlmann and Geer, 2011; Wainwright, 2019, Sect. 1.1). Without a structural assumption on the model parameters, no method estimates them consistently once $d$ exceeds $m$ (Wainwright, 2019, Sect. 7.1.1). One such assumption is sparsity, which says that few model parameters are nonzero. The least absolute shrinkage and selection operator exploits it with a penalty term built from the $\ell_{1}$-norm (Tibshirani, 1996). The regime is common wherever features are cheap and data points are not: a gene-expression dataset with $2308$ features and $63$ data points needs regularization before any classifier can be learned on it (Hastie et al., 2009, Sect. 18.2).

**See also:** [effective dimension](https://dictionaryofml.org/terms/effdim.html), curse of dimensionality, interpolation, [overfitting](https://dictionaryofml.org/terms/overfitting.html), [generalization](https://dictionaryofml.org/terms/generalization.html), [regularization](https://dictionaryofml.org/terms/regularization.html), [dimensionality reduction](https://dictionaryofml.org/terms/dimred.html), [ridge regression](https://dictionaryofml.org/terms/ridgeregression.html), least absolute shrinkage and selection operator, Vapnik–Chervonenkis dimension.

## References

- Zhang et al. (2017). Understanding deep learning requires rethinking generalization. *Int. Conf. Learn. Represent. (ICLR)*.
- Shalev-Shwartz and Ben-David (2014). Understanding Machine Learning: From Theory to Algorithms. *Cambridge Univ. Press*. <https://doi.org/10.1017/cbo9781107298019>
- Bühlmann and Geer (2011). Statistics for High-Dimensional Data: Methods, Theory and Applications. *Springer-Verlag*.
- Wainwright (2019). High-Dimensional Statistics: A Non-Asymptotic Viewpoint. *Cambridge Univ. Press*.
- Tibshirani (1996). Regression Shrinkage and Selection via the Lasso. *J. Roy. Statist. Soc.: Ser. B (Methodological)*. <https://doi.org/10.1111/j.2517-6161.1996.tb02080.x>
- Hastie et al. (2009). The Elements of Statistical Learning: Data Mining, Inference, and Prediction. *Springer Science+Business Media*. <https://doi.org/10.1007/978-0-387-84858-7>

## Cite this entry

```bibtex
@misc{dictml_highdimregime,
  author = {Jung, Alexander},
  editor = {Olioumtsevits, Konstantina and Schnoor, Ekkehard},
  title = {high-dimensional regime},
  howpublished = {Dictionary of Applied Machine Learning (course edition)},
  year = {2026},
  doi = {10.5281/zenodo.21569296},
  note = {ISBN 978-952-64-3013-3, CC BY 4.0, retrieved 2026-11-20},
  url = {https://dictionaryofml.org/terms/highdimregime.html}
}
```
