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:
- Shrink the neighborhood to ensure locality, and you are left with too few points, leading to high-variance, unstable estimates.
- 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.
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), andM13a_Scurve. - High-Dimensional Spaces: Various affine and non-linear hypercubes/hypersurfaces (e.g.,
M2_Affine_3to5,M10a_Cubic,Mn1_Nonlinear). - Mixed Manifolds: The
Lollipopdataset, which explicitly mixes 1D (stick) and 2D (candy) structures. - Baseline Control: A high-dimensional
Uniformdataset.
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}$$
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