On the Use of Bagging for Local Intrinsic Dimensionality Estimation

Kristóf Péter, Ricardo J. G. B. Campello, James Bailey, Michael E. HoulearXiv 2026 · arXiv

TL;DR

Local Intrinsic Dimensionality (LID) estimation is vital for understanding high-dimensional data, but it suffers from a harsh bias-variance tradeoff: small local neighborhoods cause massive estimation variance, while larger ones introduce non-local bias. This paper introduces a method-agnostic ensemble wrapper based on subbagging (subsampling without replacement) that dramatically reduces variance and mean squared error (MSE). By combining bagging with neighborhood smoothing, the authors unlock a highly parallelizable approach that consistently outperforms standard baseline estimators.

What Problem Does This Paper Address?

Many machine learning and data mining tasks deal with high-dimensional data that actually resides on lower-dimensional structures called submanifolds. Local Intrinsic Dimensionality (LID) quantifies the true complexity of the data space at a specific query location—essentially answering, "How many variables do I actually need to explain the data distribution right here?"

To capture truly local properties, LID estimators must only look at nearby data points. However, this introduces a fundamental dilemma:

  1. Shrink the neighborhood to ensure locality, and you are left with too few points, leading to high-variance, unstable estimates.
  2. Expand the neighborhood to reduce variance, and you risk pulling in non-local structures or mixing distinct manifolds, which introduces heavy bias.

While variance-reduction techniques exist, they are often tied to specific mathematical formulations. The authors seek a general, method-agnostic wrapper to stabilize any neighborhood-based LID estimator without sacrificing locality.

Methods

The authors propose adapting bootstrap aggregating (bagging) to the context of LID estimation. However, standard bagging (sampling with replacement) creates duplicate data points, which distorts distance distributions and violates the continuity assumptions of LID estimators.

To solve this, they use subbagging—sampling without replacement to create $B$ separate bags, each containing a fraction $r$ (sampling rate) of the original dataset.

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.

The $k$ and $r$ Interplay

Subbagging introduces a unique challenge: because each bag has fewer total points, a fixed number of nearest neighbors ($k$) requires expanding the physical search radius. This creates a complex interplay between the neighborhood size $k$ and the sampling rate $r$. The authors provide a rigorous theoretical analysis (Theorem 1) proving that decreasing $r$ de-correlates the bags and caps the limiting variance, though it requires careful tuning to manage bias.

Combining Bagging with Smoothing

The authors also integrate neighborhood smoothing (averaging local estimates) with bagging in three distinct configurations:

  • Post-smoothing: Smoothing the final aggregated ensemble estimates.
  • Pre-smoothing: Smoothing the individual estimates within each bag before aggregation.
  • Pre- and Post-smoothing: Applying both techniques simultaneously to maximize variance reduction.

Datasets

The approach was evaluated using 19 benchmark datasets commonly used in manifold learning research, each containing $n = 2,500$ points with known ground-truth LID:

  • Geometric Manifolds: M1_Sphere, M5b_Helix2d, M7_Roll (Swiss roll variant), M11_Moebius (Moebius strip), and M13a_Scurve.
  • High-Dimensional Spaces: Various affine and non-linear hypercubes/hypersurfaces (e.g., M2_Affine_3to5, M10a_Cubic, Mn1_Nonlinear).
  • Mixed Manifolds: The Lollipop dataset, which explicitly mixes 1D (stick) and 2D (candy) structures.
  • Baseline Control: A high-dimensional Uniform dataset.

Key Insights and Ideas

  • The $k/r$ Ratio Rule: The hyperparameter space is generally split by a clear boundary. If the ratio of neighborhood size to sampling rate ($\frac{k}{r}$) stays below a dataset-specific constant, bagging consistently outperforms the baseline. The strongest gains happen in the "bottom-left" region (small $k$, small $r$).
  • Bagging and Smoothing are Symbiotic: Bagging and neighborhood smoothing target variance reduction differently. Bagging de-correlates the data subsets, while smoothing averages out local structural noise.
  • Diminishing Returns of Ensemble Size ($B$): While increasing the number of bags $B$ strictly reduces variance without affecting bias, the benefits diminish rapidly. The authors show that a value as small as $B = 10$ provides excellent performance with minimal computational overhead.

Key Results

The authors tested their bagging wrapper across three distinct baseline LID estimators: Maximum Likelihood Estimation (MLE), Extended Maximum Likelihood Estimation (TLE), and Manifold-Adaptive Dimension Estimation (MADA).

A remarkably consistent performance hierarchy emerged across nearly all 19 datasets: $$\text{Baseline} < \text{Bagged} < \text{Smoothed} < \text{Bagged + Post-smoothing} < \text{Bagged + Pre-smoothing} < \text{Bagged + Pre- \& Post-smoothing}$$

Radar charts comparing relative MSE across MLE, TLE, and MADA variants. Larger covered areas indicate better performance.

As shown in the radar charts, combining pre- and post-smoothing with bagging (the outermost light-blue line) systematically minimizes Mean Squared Error across almost every manifold type.

Limitations and Future Work

  • Synthetic vs. Real-World Data: The evaluation relies entirely on synthetic benchmarks where ground-truth LID is mathematically defined. Real-world datasets with complex noise, missing data, and poorly defined manifolds still need comprehensive testing.
  • Indirect Evaluation: Testing on real-world data will require evaluating performance indirectly via downstream tasks like outlier detection or adversarial example classification.
  • Out-of-Bag (OOB) Selection: The authors note that future work will explore using out-of-bag samples from the bagging process to enable fully unsupervised model and hyperparameter selection.

Summary updated

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.
BibTeX
@misc{peter2026use,
  author = {Kristóf Péter and Ricardo J. G. B. Campello and James Bailey and Michael E. Houle},
  title = {{On the Use of Bagging for Local Intrinsic Dimensionality Estimation}},
  year = {2026},
  eprint = {2603.24384},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2603.24384},
}
Figure