Dictionary of Applied Machine Learning: 147 machine-learning terms, each with a definition, a figure, citations and a Python demo · All terms · Demos · Start here

high-dimensional regime

Updated on 2026-11-19

Readiness 95/100

▶ Run the Python demo Open in Colab Typeset PDF LaTeX source Markdown Cite this entry

See also effective dimension overfitting generalization regularization dimensionality reduction ridge regression

A machine learning (ML) 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.

Figure produced by the Python demo of the entry high-dimensional regime
Figure written by the entry's Python demo highdimregime.py, which recomputes what the entry states: the script block by block · open in Colab

Definition

B-leastsqConsider 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
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 $\featuredim$ days, learned by least squares on $\samplesize = 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 $\featuredim = \samplesize = 30$ at which the high-dimensional regime begins. Data generated by pythondemos/highdimregime.py
A machine learning (ML) 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} \label{equ_highdimregime_condition_dict} d_{\rm eff} \left( \mathcal{H} \right) > m \text{.} \end{equation} For the linear model above, the condition \(\eqref{equ_highdimregime_condition_dict}\) reads $d > m$. Empirical risk minimization (ERM) with the squared error loss delivers a solution of the least squares problem \begin{equation} \label{equ_highdimregime_leastsquares_dict} \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.

B-interpThe 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 \(\eqref{equ_highdimregime_leastsquares_dict}\) 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 (ANN) 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 (VC dimension) and by its Rademacher complexity. The sample size that a generalization guarantee needs grows in proportion to the VC dimension (Shalev-Shwartz and Ben-David, 2014, Thm. 6.8).

B-restoreTwo 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 (PCA), 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
Figure 2: The validation error of the same linear model at Krems against the number $\featuredim$ of features, for least squares (dashed curve), for least squares with the penalty term at $\regparam = 100$ (solid curve), and for least squares on the first $\featuredim' = 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 (Lasso) 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, curse of dimensionality, interpolation, overfitting, generalization, regularization, dimensionality reduction, ridge regression, least absolute shrinkage and selection operator, Vapnik–Chervonenkis dimension.

References

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

Cite this entry

@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}
}