Going from 2 features to 10 at the same data density, how many more training rows do you need?

## The arithmetic "Density" here means rows per region of the feature space. Pick a resolution — say ten equal bins along each feature — and count the regions: ``` d = 1 -> 10 cells d = 2 -> 10^2 = 100 cells d = 3 -> 10^3 = 1,000 cells d = 10 -> 10^10 = 10,000,000,000 cells ``` Going from 2 features to 10 multiplies the number of cells by `10^10 / 10^2 = 10^8`. Holding the average number of rows per cell fixed therefore means holding `n / b^d` fixed, so `n` must be multiplied by a hundred million as well. If 1,000 rows gave a comfortable ten rows per cell in two dimensions, ten dimensions would need 100 billion rows for the same comfort. The general statement: **the sample size needed to maintain a fixed resolution grows like `b^d`, exponentially in the number of features.** The choice of ten bins is arbitrary and does not change the shape of the result — with five bins per feature it is `5^d`, still exponential. What matters is that each feature *multiplies* the space rather than adding to it. ## What this means in practice Real datasets in more than a handful of dimensions are almost entirely empty. Nearly every cell contains zero rows, and the ones that are occupied hold one. Any method that estimates something from the points *near* a query — nearest neighbours, kernel smoothing, histogram-style density estimates, a decision tree split deep enough to isolate a small region — is quietly asking for a locally dense sample it does not have. The neighbourhood it actually finds spans a large fraction of the range of every feature, which is a fancy way of saying the prediction is not local at all. A second, related fact about wide spaces is that the data sits near the boundary. In a unit cube, the fraction of the volume within 0.1 of an edge along at least one axis is `1 - 0.8^d`: about 36 percent at `d = 2`, 89 percent at `d = 10`, and essentially all of it by `d = 50`. So most query points are near a face of the space, where their neighbours are one-sided and prediction becomes extrapolation rather than interpolation. ## What it does not mean It does not mean every wide dataset is hopeless. The exponent that matters is the **intrinsic** dimension — the number of directions the data genuinely varies along. Strongly correlated columns, or data lying on a low-dimensional surface inside a high-dimensional space, mean the effective exponent is far smaller than the column count. It also does not condemn every model: methods that impose a strong global structure, like a linear model, do not need a dense local neighbourhood, because they pool information from the whole dataset to estimate a handful of parameters. The exponential requirement is the price of *not* assuming a form for the function. ## What to do with the number in an interview The useful takeaway is a direction of action, not the digit count. When someone proposes adding fifty more candidate features to a distance-based or otherwise local model, the exponential-sample argument is why the right response is to ask which of them carry signal, rather than to ask for more rows. Data collection scales linearly at best; the requirement scales exponentially. That asymmetry is what makes dimensionality reduction and feature selection non-optional in wide feature spaces, and it is the reason a model that ignores irrelevant directions outperforms one that averages over them.