The Curse of Dimensionality

September 2026 · 14 min read

More features create more ways for observations to differ. If a method needs nearby examples for each kind of input, adding coordinates can spread a fixed dataset across many more combinations. This is one meaning of the curse of dimensionality.

There is a second issue: under some data distributions, distances become similar relative to their size. Neither statement means that every high-dimensional dataset is impossible to learn from. The distribution, useful structure and distance metric all matter.

The number of small regions grows quickly

Imagine each coordinate ranges from 0 to 1. Divide each range into four equal bins. One coordinate gives four cells, two coordinates give $4\times4=16$, and three give $4\times4\times4=64$:

With $d$ coordinates, there are $4^d$ cells. At ten coordinates that is 1,048,576 cells. A dataset of 1,000 rows can occupy at most 1,000 of them. The resolution per coordinate has stayed the same, but most combinations have no observed example.

This matters for methods that estimate a separate answer in each small neighborhood. They must either tolerate very little local data or expand the neighborhood, bringing together inputs that differ more. It does not imply that every model needs one example in every cell: a model can share information across regions by assuming useful structure.

How wide must a neighborhood become?

Make the assumptions explicit: observations are uniform in a $d$-dimensional unit cube, and the neighborhood is a smaller, axis-aligned cube lying wholly inside it. If its side length is $s$, its fraction of the volume is the product of $d$ equal sides. Call that fraction $f$:

Under this uniform distribution, volume fraction is also probability mass. To contain 1% of the mass, each side must span 1% of the range in one dimension, 10% in two dimensions, and about 63% in ten dimensions. Explore the same calculation below:

For 1,000 independent draws, this fixed region contains 10 observations on average; its actual count is random. It is not an exact formula for the radius of the ten nearest neighbors. Boundaries, nonuniform density and differently shaped neighborhoods change that problem.

Distances can lose relative contrast

Consider independent uniform coordinates again, and measure squared Euclidean distance from the fixed center $q=(0.5,\ldots,0.5)$. For a sampled point $x$, write $D^2$ for the sum of its squared coordinate differences:

Each new independent coordinate adds another nonnegative contribution. The average grows with dimension, while random fluctuations grow more slowly. To compare shapes fairly, divide each observed squared distance by the sample's mean squared distance. A value of 1 then means “equal to the average,” not zero distance.

The raw mean squared distances here are approximately 0.0845, 0.8419 and 8.3529. Distances have become larger, even though their relative spread has become smaller. We are displaying squared distances; taking a square root gives ordinary Euclidean distance and preserves the nearest-neighbor ordering.

If many irrelevant coordinates contribute to distance, useful differences can become harder to distinguish from the accumulated variation. A nearest-neighbor rule can then select points that are close under the chosen metric but unhelpful for the target. The feature-selection example shows this effect with just one extra column.

A hundred columns need not mean a hundred independent directions

Suppose all 100 coordinates are exact copies of a single number $t$. Every observation lies on a line. The Euclidean distance between two rows is ten times the difference between their $t$ values; adding those copies changes the scale but not the neighbor ordering or relative contrast.

The ambient dimension is the number of stored coordinates. The intrinsic dimension describes how many directions or degrees of freedom the data actually varies along. Correlation, constraints and a lower-dimensional manifold can make these very different. Small noise around a line creates a different problem from independent variation in every direction.

This is why high-dimensional nearest-neighbor methods can still work. The research on distance concentration states conditions and includes meaningful high-dimensional cases. Check your data rather than treating a feature count as a universal failure threshold.

Choose a response that preserves useful information

First check whether the distance matches the representation and task. Feature scaling changes Euclidean geometry; duplicated measurements can count the same distinction repeatedly. A distance that makes sense for a dense numerical measurement need not be appropriate for a sparse count vector.

Feature selection keeps chosen original inputs. PCA combines coordinates into linear directions; nonlinear reduction methods can model other structure. Compression helps only if the information retained serves the task. Large-variance directions are not automatically the most predictive ones.

Compare an appropriate baseline with the reduced pipeline on held-out data. Learn scaling, feature selection and projection inside each training fold. Also separate statistical quality from search speed: a faster nearest-neighbor index does not repair a poor similarity measure.

import numpy as np

for d in [1, 2, 10, 100]:
    side = .01 ** (1 / d)
    print(d, "side for 1% of the unit cube:", side)
    np.testing.assert_allclose(side ** d, .01)

rng = np.random.default_rng(28)
X = rng.random((5000, 100))  # Independent Uniform(0,1) coordinates.
summaries = []
for d in [1, 10, 100]:
    squared = ((X[:, :d] - .5) ** 2).sum(axis=1)
    relative = squared / squared.mean()
    q10, q90 = np.quantile(relative, [.1, .9])
    cv = squared.std(ddof=0) / squared.mean()
    summaries.append((d, squared.mean(), cv, q10, q90))
    print(d, "mean squared distance", squared.mean(),
          "relative spread", cv, "middle 80%", (q10, q90))
# d=1:   CV 0.8843, interval [0.0326, 2.3943]
# d=10:  CV 0.2785, interval [0.6501, 1.3663]
# d=100: CV 0.0905, interval [0.8849, 1.1180]

Optional implementation: measure distance spread

This C++ function computes squared distances to a supplied query, their mean and CV, and the 10th and 90th percentiles after normalizing by their mean. It measures a dataset; it does not infer that a particular neighbor is useful for prediction.

#include <algorithm>
#include <cmath>
#include <stdexcept>
#include <vector>
using Matrix = std::vector<std::vector<double>>;
struct Spread { double mean_squared, cv, q10, q90; };

Spread distance_spread(const Matrix& X, const std::vector<double>& query) {
    if (X.empty() || query.empty()) throw std::invalid_argument("empty input");
    for (double q : query) if (!std::isfinite(q))
        throw std::invalid_argument("finite query required");
    std::vector<double> squared;
    double mean = 0;
    for (const auto& row : X) {
        if (row.size() != query.size()) throw std::invalid_argument("shape mismatch");
        double value = 0;
        for (std::size_t j = 0; j < row.size(); ++j) {
            if (!std::isfinite(row[j])) throw std::invalid_argument("finite rows required");
            double delta = row[j] - query[j];
            value += delta * delta;
        }
        if (!std::isfinite(value)) throw std::overflow_error("squared distance overflow");
        squared.push_back(value); mean += value / X.size();
    }
    if (!(mean > 0) || !std::isfinite(mean))
        throw std::domain_error("positive finite mean needed for normalization");
    double variance = 0;
    for (double& value : squared) {
        value /= mean;
        variance += (value - 1) * (value - 1) / X.size();
    }
    std::sort(squared.begin(), squared.end());
    auto quantile = [&](double p) {
        double position = p * (squared.size() - 1);
        auto lo = static_cast<std::size_t>(position);
        auto hi = std::min(lo + 1, squared.size() - 1);
        return squared[lo] + (position - lo) * (squared[hi] - squared[lo]);
    };
    return {mean, std::sqrt(variance), quantile(.1), quantile(.9)};
}

References and further reading

• Hastie, Tibshirani and Friedman: The Elements of Statistical Learning — Chapter 2 discusses local methods and the curse of dimensionality.
• Beyer et al.: When Is “Nearest Neighbor” Meaningful? — conditions for distance concentration and examples where high-dimensional neighbors remain meaningful.
• Scikit-learn: Nearest Neighbors — distance-based prediction, representations and search algorithms.