On the Use of Bagging for Local Intrinsic Dimensionality Estimation

Kristóf Péter; Ricardo J. G. B. Campello; James Bailey; Michael E. Houle

cs.LGMar 25, 2026

On the Use of Bagging for Local Intrinsic Dimensionality Estimation

Authors: Kristóf Péter, Ricardo J. G. B. Campello, James Bailey, Michael E. Houle

Organizations: New Jersey Institute of Technology Newark, New Jersey, United States

Abstract

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+k_{s}p(n))$	$O(n^{2}+np(n))$
Bagging with post-smoothing	$O(n+Bk_{s}p(nr))$	$O(n^{2}+Bnp(nr))$
Bagging with pre-smoothing	$O(Brn+Bk_{s}p(nr))$	$O(Brn^{2}+Bnp(nr))$
Bagging with pre-smoothing and post-smoothing	$O(n+Bk_{s}nr+Bk_{s}^{2}p(nr))$	$O(n^{2}+Bn^{2}r+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)+k_{s}p(n))$	$O(n\log(n)+np(n))$
Bagging with post-smoothing	$O(\log(n)+Bk_{s}p(nr))$	$O(n\log(n)+Bnp(nr))$
Bagging with pre-smoothing	$O(B\log(nr)+Bk_{s}p(nr))$	$O(Bn\log(nr)+Bnp(nr))$
Bagging with pre-smoothing and post-smoothing	$O(\log(n)+Bk_{s}\log(nr)+Bk_{s}^{2}p(nr))$	$O(n\log(n)+Bn\log(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(n^{2})$
Bagging	$O(Brn)$	$O(Brn^{2})$
Baseline with Smoothing	$O(n+k_{s}n)$	$O(n^{2})$
Bagging with post-smoothing	$O(n+Brk_{s}n)$	$O(n^{2}+Brn^{2})$
Bagging with pre-smoothing	$O(Brn+Brk_{s}n)$	$O(Brn^{2})$
Bagging with pre-smoothing and post-smoothing	$O(n+Brk_{s}^{2}n)$	$O(n^{2}+Brn^{2})$

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(n\log(n))$
Bagging	$O(B\log(nr))$	$O(Bn\log(nr))$
Baseline with Smoothing	$O(k_{s}\log(n))$	$O(n\log(n))$
Bagging with post-smoothing	$O(\log(n)+Bk_{s}\log(nr))$	$O(n\log(n)+Bn\log(nr))$
Bagging with pre-smoothing	$O(B\log(nr)+Bk_{s}\log(nr))$	$O(Bn\log(nr))$
Bagging with pre-smoothing and post-smoothing	$O(\log(n)+Bk_{s}^{2}\log(nr))$	$O(n\log(n)+Bn\log(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,\text{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,\text{dim}=3$ . Showing all $3$ dimensions.

Figure 19: Example visualization of the Mn1_Nonlinear/Mn2_Nonlinear dataset, with $d=3,\;\text{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

\text{bias}^{2}

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

\text{bias}^{2}

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

\text{bias}^{2}

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

\text{bias}^{2}

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).

Intrinsic Dimensionality

Intrinsic dimensionality measures the effective degrees of freedom underlying data embedded in high-dimensional spaces.

See all 56 papers

A Universal Nearest-Neighbor Estimator for Intrinsic Dimensionality
Mar 11, 2026Eng-Jon Ong, Omer Bobrowski, Gesine Reinert +1Intrinsic Dimensionality
School of Mathematical Sciences, Queen Mary University of London · Department of Statistics, Oxford University
Minimax Lower Bound for Estimating Diffusion-based Local Intrinsic Dimension
Sep 4, 2026Jaehee Seo, Wontae Jeong, Jisu KimIntrinsic Dimensionality Minimax Estimation
Department of Statistics, Seoul National University
HomID : Benchmarking Intrinsic Dimension Estimators on Homogenous Manifolds with Anisotropic Embeddings
Oct 1, 2025Aritra Das, Joseph T. Iosue, Victor V. AlbertIntrinsic Dimensionality Manifold Learning
Joint Center for Quantum Information and Computer Science (QuICS), NIST & UMD College Park. · Joint Quantum Institute (JQI), NIST & UMD College Park.

Mar 11, 2026J/K move · Enter open · S save

A Universal Nearest-Neighbor Estimator for Intrinsic Dimensionality

Eng-Jon Ong, Omer Bobrowski, Gesine Reinert, Primoz Skraba

School of Mathematical Sciences, Queen Mary University of London · Department of Statistics, Oxford University

Intrinsic Dimensionality

Open paper AskPDF arXiv

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.

Abstract

Intrinsic Dimensionality

Explore similar work

A Universal Nearest-Neighbor Estimator for Intrinsic Dimensionality

Minimax Lower Bound for Estimating Diffusion-based Local Intrinsic Dimension

HomID : Benchmarking Intrinsic Dimension Estimators on Homogenous Manifolds with Anisotropic Embeddings