Random Projections Quietly Break the AI Optimization Toolkit Everyone Trusts

If you have ever tried to characterize a high-dimensional black-box optimization problem, you have probably bumped into Exploratory Landscape Analysis (ELA), the standard toolkit for turning sampled points and their objective values into a numeric fingerprint of a problem's landscape. A new paper accepted to GECCO 2026 asks a deceptively simple question about a popular shortcut: when we squash the search space with random projections to make ELA tractable, are the resulting features still meaningful? The short answer is mostly no.

Why bother with landscape features

The difficulty of solving a continuous, static, bound-constrained single-objective black-box optimization problem depends on the characteristics of the fitness landscape and the algorithm being used, and ELA uses numerical features generated via sampling to describe those characteristics. Those features feed downstream jobs like automated algorithm selection, configuration, and problem classification. The catch: accurate computation is expensive, so only approximations are available in practice, and those approximations can be unreliable enough to introduce systemic errors.

The pain worsens as dimensionality climbs. Several ELA feature classes, notably meta-model, level-set, and cell mapping features, either require training regressors and classifiers repeatedly or scale exponentially with dimension. A common workaround is to project the sampled points into a much lower-dimensional space using Random Gaussian Embeddings (RGEs) and compute the features there. RGEs are simple random linear maps z = (1/sqrt(d)) A x with Gaussian entries in A, and the Johnson-Lindenstrauss lemma guarantees that pairwise Euclidean distances are approximately preserved. The question the authors pursue is whether that distance preservation is enough for ELA to still tell you something true about the original problem.