The theory of Local Intrinsic Dimensionality (LID) has become a valuable tool for characterizing local complexity within and across data manifolds, supporting a range of data mining and machine learning tasks. Accurate LID estimation requires samples drawn from small neighborhoods around each query to avoid biases from nonlocal effects and potential manifold mixing, yet limited data within such neighborhoods tends to cause high estimation variance. As a variance reduction strategy, we propose an ensemble approach that uses subbagging to preserve the local distribution of nearest neighbor (NN) distances. The main challenge is that the uniform reduction in total sample size within each subsample increases the proximity threshold for finding a fixed number k of NNs around the query. As a result, in the specific context of LID estimation, the sampling rate has an additional, complex interplay with the neighborhood size, where both combined determine the sample size as well as the locality and resolution considered for estimation. We analyze both theoretically and experimentally how the choice of the sampling rate and the k-NN size used for LID estimation, alongside the ensemble size, affects performance, enabling informed prior selection of these hyper-parameters depending on application-based preferences. Our results indicate that within broad and well-characterized regions of the hyper-parameters space, using a bagged estimator will most often significantly reduce variance as well as the mean squared error when compared to the corresponding non-bagged baseline, with controllable impact on bias. We additionally propose and evaluate different ways of combining bagging with neighborhood smoothing for substantial further improvements on LID estimation performance.
Figures & tables
Figure 1: The leftmost figure shows the Lollipop dataset [ 44 ] overlaid with the cumulative distribution function (c.d.f) of the induced empirical distance distribution from the query at (2,2) , as a heatmap. The 2nd figure shows that, within close vicinity to the query, t , the c.d.f. is proportional to the square of the distance, becoming linear beyond the bounds of the 2D (circle-plate) submanifold, when the 1D (line) submanifold is reached. The 3rd figure shows a heatmap of LID estimates at the query at (0.5,0.005) using MLE [ 4 ] , as a function of the k -NN hyper-parameter, overlaid with the corresponding dataset distributed uniformly on a thin ribbon-like surface. The rightmost figure displays how LID estimates vary with k , not only affected by the interplay between locality preservation and sample size, but also changing with the resolution at which it is measured in practice. Within close vicinity from the query, where neither locality or resolution is critical, the small sample size results in high variance and — for estimators that are only asymptotically unbiased (including MLE) — also in bias.
Figure 2: Flowchart illustrating bagged LID estimation on a hypothetical, toy dataset. The algorithm is displayed for a single query point (with index 7) from the dataset. Note that it suffices to sample the bags only once and reuse them for different queries. The figure makes it clear that LID estimation can be done independently for each query point and for each bag, so processing is highly parallelizable across multiple nodes. For details on estimation across a dataset of queries, see the pseudo code in Appendix A.1 .
Baseline
Baseline hyper-par.
Bagging hyper-par.
Smoothing strategy
MLE [ 5 ]
k
r , B
pre or post
TLE [ 6 ]
k
r , B
pre or post
MADA [ 20 ]
k
r , B
pre or post
Table 1: LID estimators and hyper-parameters. “pre” and “post” specify whether smoothing is applied to the in-bag LID estimates (i.e. prior to aggregation) or to the bagged LID estimates, resp. All other hyper-parameters have been previously defined.
Figure 3: Comparison of the relative MSE achieved by three different LID estimators, MLE, TLE, and MADA, with and without smoothing, bagging, and three strategies for combining bagging with smoothing. The results are for 19 datasets using case-by-case optimal k and r hyper-parameters. The min-max normalized MSE values are subtracted from 1 before plotting, such that larger scores correspond to smaller relative MSEs.
Figure 4: MSE and its decomposition for each of the 19 datasets as a function of the sampling rate r used for bagged MLE as the LID estimator. Note that the baseline MLE is equivalent to r=1 , displayed on the rightmost bar of the individual charts.
Figure 5: Heatmaps of the relative difference (log-ratio) between the MSE achieved by the baseline estimator (MLE) and the MSE of its bagged counterpart for each of the 19 datasets and cross-combinations of values for the sampling rate r (x-axis) and the k -NN neighborhood size k (y-axis). Positive values, color-coded as blue, indicate that bagging outperforms the baseline, whereas negative values, color-coded in red, indicate the opposite. The relation is symmetric around zero and the darkness of the cells are proportional to the magnitude of the corresponding absolute value for the given dataset.
Appendix figures & tables32 assets
Supplementary material from the paper’s appendix.
Appendix
Figure 6: MSE and its decomposition for each of the 19 datasets, as a function of the number of bags B used for bagging of MLE as the baseline LID estimator (displayed on the leftmost bar of the individual charts). See Section A.3 for the detailed experimental setup.
Figure 7: Heatmaps of the relative difference (log-ratio) between the MSE achieved by the baseline estimator (MLE) and the MSE of its bagged counterpart for each of the 19 datasets and cross-combinations of values for the sampling rate r (x-axis) and the number of bags B (y-axis). Positive values, color-coded as blue, indicate that bagging outperforms the baseline, whereas negative values, color-coded in red, indicate the opposite. The relation is symmetric around zero and the darkness of the cells are proportional to the magnitude of the corresponding absolute value for the given dataset. See Section A.3 for the detailed experimental setup.
Method
Runtime Complexity At a single query
Runtime Complexity For a dataset as queries
Baseline
O(p(n))
O(np(n))
Bagging
O(Bp(nr))
O(Bnp(nr))
Baseline with Smoothing
O(n+ksp(n))
O(n2+np(n))
Bagging with post-smoothing
O(n+Bksp(nr))
O(n2+Bnp(nr))
Bagging with pre-smoothing
O(Brn+Bksp(nr))
O(Brn2+Bnp(nr))
Bagging with pre-smoothing and post-smoothing
O(n+Bksnr+Bks2p(nr))
O(n2+Bn2r+Bnp(nr))
Appendix
Table 2: Runtime complexities in general. (Naive Search)
Method
Runtime Complexity At a single query
Runtime Complexity For a dataset as queries
Baseline
O(p(n))
O(np(n))
Bagging
O(Bp(nr))
O(Bnp(nr))
Baseline with Smoothing
O(log(n)+ksp(n))
O(nlog(n)+np(n))
Bagging with post-smoothing
O(log(n)+Bksp(nr))
O(nlog(n)+Bnp(nr))
Bagging with pre-smoothing
O(Blog(nr)+Bksp(nr))
O(Bnlog(nr)+Bnp(nr))
Bagging with pre-smoothing and post-smoothing
O(log(n)+Bkslog(nr)+Bks2p(nr))
O(nlog(n)+Bnlog(nr)+Bnp(nr))
Appendix
Table 3: Runtime complexities in general. (Amortized search, Neighbor indices)
Method
Runtime Complexity At a single query
Runtime Complexity For a dataset as queries
Baseline
O(n)
O(n2)
Bagging
O(Brn)
O(Brn2)
Baseline with Smoothing
O(n+ksn)
O(n2)
Bagging with post-smoothing
O(n+Brksn)
O(n2+Brn2)
Bagging with pre-smoothing
O(Brn+Brksn)
O(Brn2)
Bagging with pre-smoothing and post-smoothing
O(n+Brks2n)
O(n2+Brn2)
Appendix
Table 4: Runtime complexities for k -NN estimation methods. (Naive Search)
Method
Runtime Complexity At a single query
Runtime Complexity For a dataset as queries
Baseline
O(log(n))
O(nlog(n))
Bagging
O(Blog(nr))
O(Bnlog(nr))
Baseline with Smoothing
O(kslog(n))
O(nlog(n))
Bagging with post-smoothing
O(log(n)+Bkslog(nr))
O(nlog(n)+Bnlog(nr))
Bagging with pre-smoothing
O(Blog(nr)+Bkslog(nr))
O(Bnlog(nr))
Bagging with pre-smoothing and post-smoothing
O(log(n)+Bks2log(nr))
O(nlog(n)+Bnlog(nr))
Appendix
Table 5: Runtime complexities for k -NN estimation methods. (Amortized search, Neighbor indices)
Dataset Name
d (GT LID)
dim
Ref. (Appendix)
M1_Sphere
10
11
D.1
M2_Affine_3to5
3
5
D.2
M3_Nonlinear_4to6
4
6
D.3
M4_Nonlinear
4
8
D.4
M5b_Helix2d
2
3
D.5
M6_Nonlinear
6
36
D.4
Appendix
Table 6: Collection of all datasets used in the experiments. Here d represents the ground-truth LID (GT LID) of the datasets, dim is their representation dimension (i.e., the full dimensionality of the data space), and the last column displays references to detailed descriptions of their sampling function as well as an example visualization.
Figure 8: Example visualization of the M1_Sphere dataset, with d=3,m=4 . Visualizing all 4 dimensions. The color range represents the fourth-dimensional axes.
Figure 9: Example visualization of the M2_Affine_3to5 dataset, with d=3 . Showing 4 of the 5 dimensions. The color range represents the fourth-dimensional axes.
Figure 10: Example visualization of the M3_Nonlinear_4to6 dataset, with d=4 . Showing 4 of the 6 dimensions. The color range represents the fourth dimensional axes.
Figure 11: Example visualization of the M4_Nonlinear/M6_Nonlinear/M8_Nonlinear datasets, with d=4,m=1 . Showing 4 of the 8 dimensions. The color range represents the fourth-dimensional axes.
Figure 12: Example visualization of the M5b_Helix2d dataset, with d=2 . Showing all 3 dimensions.
Figure 13: Example visualization of the M7_Roll dataset, with d=2 . Showing all 3 dimensions.
Figure 14: Example visualization of the M9_Affine dataset, with d=4 . Showing all 4 dimensions. The color range represents the fourth-dimensional axes.
Figure 15: Example visualization of the M10_Cubic dataset, with d=4 . Showing all 4 dimensions. The color range represents the fourth-dimensional axes.
Figure 16: Example visualization of the M11_Moebius dataset, with d=2,dim=3 . Showing all 3 dimensions.
Figure 17: Example visualization of the M12_Norm dataset, with d=4 . Showing all 4 dimensions. The color range represents the fourth-dimensional axes.
Figure 18: Example visualization of the M13a_Scurve dataset, with d=2,dim=3 . Showing all 3 dimensions.
Figure 19: Example visualization of the Mn1_Nonlinear/Mn2_Nonlinear dataset, with d=3,dim=12 . Showing 4 out of the 12 dimensions.
Figure 20: Example visualization of the lollipop dataset, with d=2 . Showing all 2 dimensions.
Figure 21: Example visualization of the uniform dataset, with d=3 , dim=4 . Showing all 4 dimensions.
Table 7: Table showing the optimal results for the MLE estimator across the different bagging variants with smoothing. The shown k and r values are the ones that achieved the lowest MSE across experiments for that specific dataset and estimator variant. While the MSE is the lowest one, the Variance and Bias-squared represent the decomposition of this MSE, and therefore, not necessarily the lowest on their own. The table is colored using a per-dataset (one for each row) logarithmic color scale based on the MSE to indicate large to small values as mild red to mild blue colors across the table cells (estimator variants). The best results in a row are additionally written with a bold font. This raw data is the basis of the MLE part of the radar charts analyzed in Section 6 of the main paper.
Table 8: Table showing the optimal results for the TLE estimator across the different bagging variants with smoothing. The shown k and r values are the ones that achieved the lowest MSE across experiments for that specific dataset and estimator variant. While the MSE is the lowest one, the Variance and Bias-squared represent the decomposition of this MSE, and therefore, not necessarily the lowest on their own. The table is colored using a per-dataset (one for each row) logarithmic color scale based on the MSE to indicate large to small values as mild red to mild blue colors across the table cells (estimator variants). The best results in a row are additionally written with a bold font. This raw data is the basis of the TLE part of the radar charts analyzed in Section 6 of the main paper.
Table 9: Table showing the optimal results for the MADA estimator across the different bagging variants with smoothing. The shown k and r values are the ones that achieved the lowest MSE across experiments for that specific dataset and estimator variant. While the MSE is the lowest one, the Variance and Bias-squared represent the decomposition of this MSE, and therefore, not necessarily the lowest on their own. The table is colored using a per-dataset (one for each row) logarithmic color scale based on the MSE to indicate large to small values as mild red to mild blue colors across the table cells (estimator variants). The best results in a row are additionally written with a bold font. This raw data is the basis of the MADA part of the radar charts analyzed in Section 6 of the main paper.
Figure 22: 19 separate bar charts, one for each data manifold. On the x-axis is a range of B (number of bags) hyper-parameters, set for the simple bagged estimator used to estimate LID, except for the first bar from the left, which represents the baseline estimator. The baseline estimator selected is the TLE. On the y-axis are the raw values of the MSE achieved by the given estimator. The bars are vertically split into variance and bias2 parts to illustrate the mean squared error decomposition, signaled by green and red colors. See Section A.3 for the detailed experimental setup and Section A.4.1 for the in-depth explanation of these results (originally illustrated with the MLE version of this plot).
Figure 23: 19 separate bar charts, one for each data manifold. On the x-axis is a range of B (number of bags) hyper-parameters, set for the simple bagged estimator used to estimate LID, except for the first bar from the left, which represents the baseline estimator. The baseline estimator selected is the MADA. On the y-axis are the raw values of the MSE achieved by the given estimator. The bars are vertically split into variance and bias2 parts to illustrate the mean squared error decomposition, signaled by green and red colors. See Section A.3 for the detailed experimental setup and Section A.4.1 for the in-depth explanation of these results (originally illustrated with the MLE version of this plot).
Figure 24: 19 separate bar charts, one for each data manifold. On the x-axis is a range of r (sampling rate) hyper-parameters, set for the simple bagged estimator used to estimate LID, including the last bar from the left, which represents the baseline estimator but is equivalent with the r=1 case. The baseline estimator selected is the TLE. On the y-axis are the raw values of the MSE achieved by the given estimator. The bars are vertically split into variance and bias2 parts to illustrate the mean squared error decomposition, signaled by green and red colors. See Section 5 of the main paper for the detailed experimental setup and Section 6 for the in-depth explanation of results (originally illustrated with the MLE version of this plot).
Figure 25: 19 separate bar charts, one for each data manifold. On the x-axis is a range of r (sampling rate) hyper-parameters, set for the simple bagged estimator used to estimate LID, including the last bar from the left, which represents the baseline estimator but is equivalent with the r=1 case. The baseline estimator selected is the MADA. On the y-axis are the raw values of the MSE achieved by the given estimator. The bars are vertically split into variance and bias2 parts to illustrate the mean squared error decomposition, signaled by green and red colors. See Section 5 of the main paper for the detailed experimental setup and Section 6 for the in-depth explanation of results (originally illustrated with the MLE version of this plot).
Figure 26: 19 separate heat maps, one for each data manifold. On the x-axis is a range of r (sampling rate) hyper-parameters, while on the y-axis is a range of B (number of bags) hyper-parameters. At each coordinate, the combination of the two hyper-parameters is set for the simple bagged estimator used to estimate LID. The baseline estimator selected is the TLE. The squares on the grid are colored based on the logarithm of the ratio between the MSE achieved by the baseline estimator and the MSE of the simple bagged estimator using that specific hyper-parameter combination. See Section A.3 for the detailed experimental setup and Section A.4.2 for the in-depth explanation of results (originally illustrated with the MLE version of this plot).
Figure 27: 19 separate heat maps, one for each data manifold. On the x-axis is a range of r (sampling rate) hyper-parameters, while on the y-axis is a range of B (number of bags) hyper-parameters. At each coordinate, the combination of the two hyper-parameters is set for the simple bagged estimator used to estimate LID. The baseline estimator selected is the MADA. The squares on the grid are colored based on the logarithm of the ratio between the MSE achieved by the baseline estimator and the MSE of the simple bagged estimator using that specific hyper-parameter combination. See Section A.3 for the detailed experimental setup and Section A.4.2 for the in-depth explanation of results (originally illustrated with the MLE version of this plot).
Figure 28: 19 separate heat maps, one for each data manifold. On the x-axis is a range of r (sampling rate) hyper-parameters, while on the y-axis is a range of k -NN hyper-parameters. At each coordinate, the combination of the two hyper-parameters is set for the simple bagged estimator used to estimate LID. The baseline estimator selected is the TLE. The squares on the grid are colored based on the logarithm of the ratio between the MSE achieved by the baseline estimator and the MSE of the simple bagged estimator using that specific hyper-parameter combination. See Section 5 of the main paper for the detailed experimental setup and Section 6 for the in-depth explanation of results (originally illustrated with the MLE version of this plot).
Figure 29: 19 separate heat maps, one for each data manifold. On the x-axis is a range of r (sampling rate) hyper-parameters, while on the y-axis is a range of k -NN hyper-parameters. At each coordinate, the combination of the two hyper-parameters is set for the simple bagged estimator used to estimate LID. The baseline estimator selected is the MADA. The squares on the grid are colored based on the logarithm of the ratio between the MSE achieved by the baseline estimator and the MSE of the simple bagged estimator using that specific hyper-parameter combination. See Section 5 of the main paper for the detailed experimental setup and Section 6 for the in-depth explanation of results (originally illustrated with the MLE version of this plot).
Estimating the intrinsic dimensionality (ID) of data is a fundamental problem in machine learning and computer vision, providing insight into the true degrees of freedom underlying high-dimensional observations. Existing methods often rely on geometric or distributional assumptions and can significantly fail when these assumptions are violated. In this paper, we introduce a novel ID estimator based on nearest-neighbor distance ratios that involves simple calculations and achieves state-of-the-art results. Most importantly, we provide a theoretical analysis proving that our estimator is universal, namely, it converges to the true ID independently of the distribution generating the data. We present experimental results on benchmark manifolds and real-world datasets to demonstrate the performance of our estimator.
Eng-Jon Ong, Omer Bobrowski, Gesine Reinert +1
School of Mathematical Sciences, Queen Mary University of London · Department of Statistics, Oxford University
While diffusion-based methods have recently emerged as effective tools for probing the intrinsic geometry of high-dimensional data, their statistical difficulty remains largely unexplored. We study estimation of the finite-scale population functional underlying FLIPD (Kamkari et al., 2024; arXiv:2406.03537), a diffusion-based local intrinsic dimension (LID) quantity defined through the logarithmic scale derivative of a Gaussian-smoothed density. Intuitively, Gaussian smoothing turns local dimension into a scale law: near a d-dimensional manifold, the kernel mass grows like σd, so differentiating with respect to the noise scale reveals the intrinsic exponent. Under a regular manifold model, we show uniformly over the model class that the finite-scale field differs from the manifold dimension d by at most O(σ2). We then establish a minimax lower bound of order (nσd)−1 for estimating this finite-scale field from n observations, for n−1/(2α+d)≲σ≤σ0. At the smallest scale covered by our lower-bound construction, the bound becomes the nonparametric rate n−2α/(2α+d).
Jaehee Seo, Wontae Jeong, Jisu Kim
Department of Statistics, Seoul National University
The manifold hypothesis suggests that data lies on manifolds with smaller intrinsic dimension (ID) than their ambient dimension. However there is no empirical agreement on the estimates for ID from different estimators for realistic datasets. Thus it is important to test ID estimators (IDEs) with targeted stressors. In this work, we consider the role of anisotropy. To this end, we propose HomID, a collection of homogeneous spaces with anisotropic embedding, for benchmarking ID estimators. We observe that methods that perform well on standard benchmarks systematically degrade on HomID under identical resource allocation. We further observe that anisotropic distortion of such benchmarks also results in performance degradation. Finally, we demonstrate that controlled anisotropic distortions induce systematic shifts in the distributions on which these methods rely, providing a concrete mechanism for the resulting estimation errors in two particular IDEs.
Aritra Das, Joseph T. Iosue, Victor V. Albert
Joint Center for Quantum Information and Computer Science (QuICS), NIST & UMD College Park. · Joint Quantum Institute (JQI), NIST & UMD College Park.