Algorithmic Scaling via the Intrinsic Doubling Dimension

50 concepts24 papers1 proposal

High-dimensional data poses a fundamental challenge in computer science: as the number of features grows, the computational cost of geometric operations explodes. Standard dimensionality reduction techniques, such as the Johnson-Lindenstrauss lemma, allow us to project data into a lower-dimensional space while preserving pairwise distances. However, these classical methods typically scale the target dimension based on the total number of data points $n$. When dealing with massive, modern datasets, this logarithmic dependency on $n$ still yields target dimensions that are unnecessarily high.

The core insight of recent research is that real-world datasets rarely fill their high-dimensional ambient spaces uniformly. Instead, they often reside on low-dimensional structures or manifolds. By parameterizing algorithms around a metric space's doubling dimension rather than its ambient dimension or total point count, we can compress data and optimize geometric algorithms far more aggressively.

The Intuition of Bounded Local Expansion

To understand why the doubling dimension works, consider a simple geometric exercise: how many small balls of radius $r/2$ do you need to completely cover a larger ball of radius $r$?

  • On a one-dimensional line, you need exactly $2$ balls.
  • On a two-dimensional flat square, you need $4$ balls.
  • In a three-dimensional cube, you need $8$ balls.

In a general $D$-dimensional Euclidean space, you need $2^D$ balls. The exponent matches the dimension.

1D Line:   (---*---)  -->  (--*) (*--)  (2 balls)
2D Plane:  4 balls needed to cover 1 large ball
3D Space:  8 balls needed to cover 1 large ball

We can invert this relationship to define an intrinsic dimensionality for spaces that are not perfectly flat or Euclidean. A metric space is said to have a doubling dimension $d$ if any ball of radius $r$ can be covered by at most $2^d$ balls of radius $r/2$.

This definition captures the local expansion rate of the data. If a dataset consisting of millions of points in a $1000$-dimensional ambient space can always be covered hierarchically using a small number of balls, its doubling dimension $d$ is small. Kontorovich et al. leveraged this property in Non-uniform packings to prove that the density and packing bounds of a space remain highly predictable when constrained by this intrinsic dimensionality, even when the sizes of the covering regions vary dynamically.

Size-Independent Dimensionality Reduction

If the complexity of a dataset is governed by its local expansion rate rather than its absolute size, we should be able to perform dimensionality reduction to a target space that is completely independent of the number of points $n$.

This intuition has been successfully applied to a variety of clustering and optimization problems. For instance, in Randomized Dimensionality Reduction for Facility Location and Single-Linkage Clustering, Narayanan et al. demonstrated that for clustering problems where the number of clusters is not fixed beforehand, data can be projected into a lower-dimensional space determined solely by the intrinsic doubling dimension. By aligning the projection complexity with the underlying geometric structure, the authors achieved dramatic computational speedups without sacrificing solution quality.

Similarly, Gao et al. showed in Randomized Dimensionality Reduction for Euclidean Maximization and Diversity Measures that for maximization and diversity problems—where the goal is to select a subset of items that are as spread out as possible—the target dimension depends strictly on the doubling dimension.

Even when constraints are made more rigid, such as requiring cluster centers to be chosen directly from the dataset itself (discrete clustering), the doubling dimension remains a powerful tool. Jiang et al. demonstrated in Dimension Reduction for Clustering: The Curious Case of Discrete Centers that parameterizing the target dimension with the doubling dimension allows algorithms to bypass the pessimistic bounds typically imposed by the total point count.

Geometry-Aware Coresets and Compression

The utility of the doubling dimension extends beyond projection to data summarization techniques like coresets—small, weighted subsets of the original data that accurately approximate the loss function of a larger dataset.

Traditional coreset construction often relies on complexity measures like the VC dimension, which can be difficult to compute for complex models. By shifting the focus to the doubling dimension of the parameter or data space, researchers can bound the size of data summaries based on the intrinsic complexity of the data distribution.

For example, Wang et al. established in Robust and Fully-Dynamic Coreset for Continuous-and-Bounded Learning (With Outliers) Problems that coreset sizes can be bounded by the doubling dimension of the parameter space, enabling efficient data summarization for dynamic streaming environments with outliers. This principle was extended to relational databases by Chen et al. in Coresets for Relational Data and The Applications, proving that summaries can remain compact and efficient even when the ambient feature dimension is high, provided the underlying manifold is simple.

High-Dimensional Data ──> [Doubling Dimension Analysis] ──> Compact Coreset
(Ambient Dimension D)       (Intrinsic Dimension d << D)       (Size scales with d)

This geometric constraint also dictates how effectively we can compress samples for classification tasks. In Near-optimal sample compression for nearest neighbors, Gottlieb et al. utilized the doubling dimension to bound the size of a consistent subset for nearest neighbor classifiers. Because the local expansion rate is bounded, the number of prototype points needed to maintain classification boundaries depends on the intrinsic geometry rather than the ambient Euclidean dimension. For large-scale retrieval, Raginsky demonstrated in Locality-sensitive binary codes from shift-invariant kernels that the number of bits required for effective binary embeddings is fundamentally governed by this intrinsic manifold dimension, allowing high-dimensional vectors to be mapped to short binary strings while preserving similarity information.

Extending to Non-Euclidean Metrics

One of the most compelling reasons to design algorithms around the doubling dimension is its universality: it relies purely on distances, meaning it applies to arbitrary metric spaces where standard linear algebra tools like Principal Component Analysis (PCA) fail.

Lee introduced a unified embedding technique called measured descent in Measured descent: A new embedding method for finite metrics. By locally decomposing a finite metric space at varying scales, this method achieves distortion bounds that adapt gracefully to the doubling dimension of the metric, offering a way to map complex, non-Euclidean structures into normed spaces with minimal distortion.

This framework has also solved long-standing theoretical gaps in specific non-Euclidean spaces, such as the Manhattan ($\ell_1$) metric. While randomized dimensionality reduction has been well-understood in Euclidean spaces, the $\ell_1$ metric is mathematically less forgiving. To overcome this, Emiris et al. developed a two-stage process in Near-neighbor preserving dimension reduction via coverings for doubling subsets of ℓ1. Their approach combines point-set covering with random linear projections, exploiting the low intrinsic doubling dimension of a subset to preserve near-neighbor relationships within $\ell_1$ spaces.

By shifting our perspective from the ambient container of a dataset to its intrinsic expansion rate, the doubling dimension provides a robust, mathematically rigorous framework for scaling algorithms. It exposes the hidden simplicity of high-dimensional data, allowing compression, clustering, and embedding techniques to scale with the true complexity of the problem.

Key Foundational Work

Measured descent: A new embedding method for finite metrics (2004) — contributed 1 concept elements to this direction.
Random Projections for Manifold Learning (2007) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_intrinsic_dimension_scaling_doubling_dim_4b026a01,
  title = {intrinsic dimension scaling (doubling dimension scaling)},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/intrinsic-dimension-scaling-doubling-dimension-scaling/rdr_4b026a0124684affab1064b59bba75ab},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_intrinsic_dimension_scaling_doubling_dim_4b026a01_v1,
  title = {intrinsic dimension scaling (doubling dimension scaling)},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/intrinsic-dimension-scaling-doubling-dimension-scaling/rdr_4b026a0124684affab1064b59bba75ab/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake