Does Dimensionality Reduction via Random Projections Preserve Landscape Features?

1. Problem Statement

Exploratory Landscape Analysis (ELA) is a data-driven framework used to characterize black-box optimization problems by extracting numerical features from sampled points and their objective values. These features facilitate downstream tasks such as automated algorithm selection, configuration, and problem classification.

However, ELA faces significant scalability challenges in high-dimensional settings ($D \gg 20$):

• Computational Cost: Many feature classes (e.g., meta-models, level sets, cell mappings) become prohibitively expensive to compute as dimensionality increases.
• Sparsity and Variance: High-dimensional spaces suffer from the "curse of dimensionality," leading to sparse sampling, high estimator variance, and unreliable feature values.
• Proposed Mitigation: Dimensionality reduction (specifically projecting points into a lower-dimensional space) has been suggested to make ELA feasible for large-scale problems.

The Core Question: While projecting data reduces computational costs, it is unclear whether the ELA features computed in this reduced space still accurately reflect the intrinsic properties of the original high-dimensional landscape, or if they are merely artifacts of the projection distortion.

2. Methodology

The authors investigate the robustness of ELA features under Random Gaussian Embeddings (RGEs), a data-agnostic dimensionality reduction technique.

• Experimental Setup:

  • Benchmark: The noiseless BBOB (Black-Box Optimization Benchmarking) problem collection from the COCO platform, comprising 24 functions across 5 categories and 15 instances each ($D=20$).
  • Sampling: Latin Hypercube Sampling (LHS) designs were generated with two budgets: limited ($S = 10D = 200$) and abundant ($S = 100D = 2000$).
  • Projection: Points were projected into lower dimensions $d \in \{2, 5, 10\}$ using random linear matrices $A$ drawn from a standard normal distribution. Compression ratios ($r = d/D$) were $0.1, 0.25, 0.5$.
  • Feature Sets: 13 distinct feature sets were analyzed, including:
    • Distribution-based (ela_distr)
    • Level-set (ela_level)
    • Meta-model (ela_meta)
    • Nearest-better clustering (nbc)
    • Dispersion (disp)
    • Information content (ic)
    • Fitness-distance correlation (fitness_distance)
    • PCA-based (pca)

• Evaluation Metric:
  The authors defined a relative feature shift ($\delta$) to measure the distortion induced by projection:
  $$\delta = \frac{\tilde{t} - t_{ref}}{|t_{ref}| + \epsilon}$$
  Where $\tilde{t}$ is the feature value in the projected space and $t_{ref}$ is the value in the original space. They analyzed the distribution of this shift across multiple random embedding realizations to distinguish between robustness (low variance) and invariance (zero shift).

3. Key Contributions

1. Systematic Investigation of RGEs in ELA: The study is the first to rigorously analyze how random linear projections affect a broad spectrum of ELA features across different problem instances and sample budgets.
2. Identification of Feature Sensitivity: The authors categorize features based on their sensitivity to projection-induced geometric distortions, distinguishing between those that remain stable and those that are highly volatile.
3. Distinction Between Robustness and Informativeness: A critical theoretical contribution is the finding that robustness does not imply informativeness. A feature may be stable under projection (low variance) but still converge to a value that reflects projection artifacts rather than the true landscape characteristics.
4. Visual and Theoretical Proof of Distortion: The paper demonstrates that RGEs can induce artificial multimodality and alter neighborhood structures, violating the assumption of uniform space-filling required by many ELA features.

4. Key Results

• Feature Sensitivity Hierarchy:

  • Most Robust: Features based purely on objective values (e.g., fitness_distance.fitness_mean, ela_distr statistics) are invariant because they do not depend on the spatial coordinates.
  • Moderately Robust: Features relying on global covariance structures (e.g., certain PCA descriptors, ela_meta.lin_simple.intercept) show low sensitivity, likely due to the centering of LHS designs.
  • Highly Sensitive: Features dependent on local neighborhood relations and topology (e.g., nbc, ic, ela_level) suffer significant distortion. Random projections collapse distinct points, creating artificial clustering and distorting distance metrics, which leads to biased estimates of ruggedness and multimodality.

• Projection-Induced Artifacts:

  • Projection-Consistent Convergence: Some features (e.g., ela_level) stabilize under projection but converge to values different from the original space. This creates a false sense of reliability while masking the true landscape properties.
  • Projection-Induced Shift: Other features (e.g., ic.eps_s) systematically shift in a specific direction (e.g., indicating higher ruggedness) as dimensionality decreases, driven by increased effective point density in the reduced space.

• Impact of Sample Size:
  While increasing the sample size reduces estimator variance, it does not eliminate the systematic bias introduced by the projection itself. The distortion is inherent to the embedding mechanism, not just the sampling density.

5. Significance and Implications

• Caution for High-Dimensional ELA: The study concludes that ELA features computed in reduced spaces cannot be directly interchanged with those from the original high-dimensional space. Relying on projected features for algorithm selection or configuration may lead to suboptimal decisions due to biased landscape characterization.
• Guidance for Practitioners: If dimensionality reduction is necessary, practitioners should restrict themselves to a small subset of robust features (primarily fitness-only statistics and coarse-grained dispersion measures) and avoid features relying on local topology or complex level-set geometries.
• Future Directions: The authors suggest that simple random projections are insufficient for preserving landscape fidelity. Future work should explore structured embeddings or a priori knowledge of the problem structure to better align the reduction process with the intrinsic geometry of the objective function.

In summary, while dimensionality reduction via random projections offers a computational shortcut for ELA in high dimensions, it fundamentally alters the geometric and topological structure of the search space. Consequently, most ELA features lose their representativeness of the original problem, posing a significant risk to the reliability of data-driven optimization strategies.