💻 computer science

Sampling on Random Subspaces under Limited Data in the Context of Exploratory Landscape Analysis

This paper proposes and evaluates a random linear embedding sampling strategy for Exploratory Landscape Analysis under limited data budgets, demonstrating that allocating evaluations to randomly oriented low-dimensional subspaces can improve the robustness of landscape descriptors compared to traditional full-space sampling, though effectiveness varies by feature class and problem type.

Original authors: Iván Olarte Rodríguez, Anja Jankovic, Thomas Bäck, Elena Raponi

Published 2026-07-10

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Iván Olarte Rodríguez, Anja Jankovic, Thomas Bäck, Elena Raponi

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are a detective trying to solve a mystery, but you only have a tiny budget for clues. Your job is to figure out what the "landscape" of a problem looks like—whether it's a smooth hill, a jagged mountain range, or a maze of traps. In the world of computer optimization, this is called Exploratory Landscape Analysis (ELA). Usually, detectives try to spread their limited clues out evenly across the entire map, hoping to get a good view of everything.

But here's the twist: when the map is huge (like a 20-dimensional puzzle) and your clue budget is tiny, spreading them out evenly leaves you with a very sparse, blurry picture. It's like trying to understand the texture of a giant rug by poking it with a needle in just a few random spots; you might miss the patterns entirely.

The New Strategy: The "Slice and Dice" Approach
The authors of this paper suggest a different way to spend those precious clues. Instead of poking the whole giant rug, they propose picking a few random, thin slices of the rug and poking those densely. They call this sampling on random subspaces.

Think of it like this: If you want to understand a 3D cake but only have enough frosting to cover a small area, you could spread a thin layer of frosting over the whole top (the old way). Or, you could cut a few thin, vertical slices of the cake and cover those slices thickly with frosting. By concentrating your limited resources on these random slices, you get a much clearer, more detailed look at the texture and structure of the cake within those slices.

What They Actually Did
The researchers tested this idea using a standard set of 24 tricky math problems (known as the BBOB test suite) in a 20-dimensional space. They had a fixed budget of 10 times the dimension (so, 200 clues for a 20-dimensional problem). They compared their "slice" method against the traditional "spread everything out" method.

They didn't just guess; they ran simulations 40 times for each setup with different random seeds to make sure the results weren't just luck. They measured how close their "slice" maps were to a super-detailed "gold standard" map created with a massive budget of 2,000 clues.

The Findings: It Depends on What You're Looking For
The results suggest that the "slice" method is a promising alternative, but it's not a magic bullet that works for everything.

The Winners: For features that look at how spread out the data is (called dispersion) or how much information is packed into the landscape (called information content), the slice method worked surprisingly well. In fact, for these specific features, concentrating the budget on a single slice (or a few slices) often gave a clearer picture than spreading the budget thin over the whole space.
The Losers: However, if you are trying to understand the entire global shape of the problem (like fitting a giant curve across the whole map), the slice method struggled. The traditional "spread out" method was still better for these specific tasks.
The Sweet Spot: They found that cutting the problem down to half its size (a compression ratio of 0.5) was usually the best balance. If they cut it down too much (to 0.1 or 0.25), they lost too much important information, and the picture became blurry again.

What They Explicitly Rule Out
The paper argues against the idea that the old way (spreading samples evenly across the full space) is always the best default, especially when you are short on time or money. They show that sticking to the old method can lead to noisy, unstable results that change wildly depending on where you happened to poke your needle.

How Sure Are They?
The authors are careful not to call this a "solved problem." They state that their results suggest this is a promising path. They emphasize that the effectiveness depends heavily on which specific feature you are trying to measure and what kind of problem you are solving. It's not a universal win; it's a tool that works better than the standard tool for some jobs, but not all.

The Bottom Line
If you are a detective with a tiny budget, don't just scatter your clues randomly over the whole city. The paper suggests that focusing your limited energy on a few random, deep dives might actually help you understand the neighborhood's structure better than a shallow sweep of the whole map. But remember, you still need to pick the right dive spots, because some mysteries just need a full view to be solved.

Technical Summary: Sampling on Random Subspaces under Limited Data in Exploratory Landscape Analysis

Problem Statement
Exploratory Landscape Analysis (ELA) is a data-driven methodology used to characterize black-box optimization problems by transforming sampled decision vectors and objective values into structured numerical features. These descriptors support downstream tasks such as algorithm selection, configuration, and problem classification. However, the reliability of ELA features is heavily dependent on sample size. In resource-constrained settings—common in high-dimensional optimization or expensive real-world applications where function evaluations are costly—standard space-filling designs (e.g., Latin Hypercube Sampling) often fail. When the sampling budget is limited, these designs result in sparse coverage of the decision space, leading to high variance and instability in feature estimates, particularly for those relying on local geometric structures or neighborhood relationships.

Methodology
To address the trade-off between global representativeness and local sampling density, the authors propose a sampling strategy based on random linear embeddings. Instead of distributing a fixed budget uniformly across the full $D$ -dimensional ambient space, the budget is reallocated to randomly oriented low-dimensional affine subspaces.

The study evaluates four specific sampling configurations in a 20-dimensional setting ( $D=20$ ) using the noiseless BBOB test suite:

Full/ELAA: Uniform sampling in the full ambient space; features computed in the ambient space.
Sliced/ELAA (Multiple Embeddings): The budget is split across $K$ random embeddings of dimension $d$ . Samples are generated in each subspace, mapped back to the ambient space, and features are computed on the union of these points.
All_in/ELAA (Single Embedding, Ambient Evaluation): The entire budget is allocated to a single random embedding. Points are mapped to the ambient space for evaluation, and features are computed in the ambient space.
All_in/ELAR (Single Embedding, Reduced Evaluation): The entire budget is allocated to a single random embedding. Points are evaluated in the ambient space, but features are computed directly within the reduced $d$ -dimensional subspace.

The embedding matrices are generated using standard normal distributions, with optional column normalization to preserve Euclidean distances. To handle boundary constraints, samples generated in the embedded space are mapped to the ambient space and clipped to the feasible domain. The study utilizes compression ratios ( $r = d/D$ ) of 0.1, 0.25, and 0.5.

Key Contributions

Proposal of a New Sampling Strategy: The authors introduce a method that reallocates a fixed evaluation budget to randomly generated low-dimensional subspaces to increase effective sampling density, avoiding the artificial distortions associated with projecting pre-sampled points.
Empirical Analysis of Stability: The paper conducts a comprehensive comparison of feature stability between full-space sampling and embedding-based sampling across six classical ELA feature sets (including ela_distr, ela_level, ela_meta, nbc, disp, and ic) and 24 BBOB functions.
Analysis of Compression Ratios: The study investigates the impact of varying compression ratios, highlighting the trade-off between increased sampling density and information loss.
Evaluation Protocol: The authors assess the reliability of these strategies by measuring the Wasserstein-1 distance between feature distributions obtained under limited budgets and a high-fidelity reference distribution (2000 samples).

Results
The experimental results, aggregated over 40 random seeds per configuration, reveal that the effectiveness of the sampling strategy is highly dependent on the specific feature class and the underlying problem landscape:

Feature Dependence:
- Meta-model features (ela_meta): Full-space sampling (Full/ELAA) generally outperforms subspace methods, as these features rely on global coverage to fit linear models.
- Dispersion (disp) and Information Content (ic): Embedding-based sampling, particularly with a moderate compression ratio ( $r=0.5$ ), often matches or outperforms full-space sampling, suggesting these features are robust to localized sampling.
- Level-set features (ela_level): Strategies involving a single embedding with feature computation in the reduced space (All_in/ELAR) consistently achieve top rankings.
Compression Ratio Impact: Aggressive compression (e.g., $r=0.1$ ) systematically degrades performance across most feature sets, indicating that retaining a moderate level of landscape information is necessary. A ratio of $r=0.5$ provides the best overall trade-off.
Overall Performance: The Sliced/ELAA strategy with $r=0.5$ achieves the best consensus ranking, performing consistently well across both feature and function aggregations. However, no single method is statistically superior across all settings.

Significance and Claims
The paper concludes that under limited evaluation budgets, the standard practice of uniform full-space sampling is often suboptimal for characterizing problem landscapes. The authors claim that structured subspace sampling constitutes a promising alternative that can improve the stability of specific ELA feature subsets.

The significance of this work lies in shifting the perspective of sampling from a passive data collection step to an active design choice. By demonstrating that concentrating samples within informative subspaces can yield more reliable descriptors than distributing them sparsely across the full space, the authors provide a practical mechanism for enhancing landscape characterization in resource-constrained optimization scenarios. The study acknowledges limitations, noting that the approach is currently validated on 20-dimensional benchmarks and that features relying on global structure may still struggle under localized sampling. Future work is suggested to explore benchmarks with low intrinsic dimensionality and to assess the impact of these strategies on downstream algorithm selection tasks.

Technical Summary: Sampling on Random Subspaces under Limited Data in Exploratory Landscape Analysis

More like this