betaFeedback

WorksComputer Science

Shortcut Learning in Feature-Based Algorithm Selection

Abstract

Landscape features give learning models information about the objective function for algorithm selection, algorithm configuration, and performance prediction. Should these features capture more information? Not always, because a model may rely on information that the algorithms ignore. This phenomenon is called shortcut learning, and in-distribution accuracy can hide it. We propose the Rubber Ruler Test. It transforms the objective values of test instances with random strictly increasing transformations, reruns the algorithms, and measures prediction performance. Comparison-based algorithms such as CMA-ES perform identically after the transformation, so for them any drop reveals shortcut learning. On 10-dimensional BBOB, a model for two comparison-based algorithms learned shortcuts even from normalized objective values. The R^2 of a model using all ELA features dropped from 0.85 to 0.23, below 0.45 with invariant features only. Rank-based features reduced the drop when algorithms search using ranks. Data augmentation with transformed training instances improved prediction on transformed instances for every portfolio we studied, but lowered R^2 on original instances by up to 0.31. These results suggest that models should rely only on information that the algorithms use. We recommend reporting the Rubber Ruler Test alongside in-distribution accuracy and using it to choose feature extraction and data augmentation.

CCS Concepts

• Theory of computation → Bio-inspired optimization; • Computing methodologies → Supervised learning by regression.

Introduction

Automated algorithm selection (AAS) and automated algorithm configuration (AAC) are promising approaches to choosing an algorithm and its configuration for each black-box optimization problem [14]. This choice matters because the best algorithm and its configuration differ from one optimization problem to another.

Most AAS and AAC methods work in two steps. First, landscape analysis computes a feature vector for each optimization problem, called a problem instance, from sampled solutions and their objective values. The most common features come from exploratory landscape analysis (ELA) [18]. Second, a trained model maps the feature vector to an algorithm or a configuration, either directly or by predicting algorithm performance.

A common approach to improving AAS and AAC is to design landscape features that capture more information about the objective function [14, 24]. Should they really capture more information?

The answer is not always yes, because a model may rely on information that is irrelevant to the task. In machine learning, this phenomenon is called shortcut learning [5]. Such information can still correlate with the labels in the training data, so the model may learn it as a cue. As Figure 2 shows, the model then performs well on in-distribution data but poorly on out-of-distribution data. To trust a model, we must suppress shortcut learning.

Figure 2. A model that relies on an irrelevant feature fails on out-of-distribution test data. The horizontal axis is the irrelevant feature, and the vertical axis is the relevant feature. Filled markers are training data, and hollow markers are test data. In the training data, both features correlate with the class. In the test data, the irrelevant feature’s correlation is reversed. The background color shows the decision boundary of each model. The left model misclassifies two training points but correctly classifies all test points. The right model classifies all training points correctly but misclassifies every test point.

AAS and AAC research already applies one remedy: it normalizes the objective values of sampled solutions. The search behavior of many black-box optimization algorithms is invariant to positive affine transformations of the objective values [11]. A positive multiplier and an additive constant on the objective values are therefore often irrelevant to the task. Normalization removes this irrelevant information from the model’s input. Prior work has shown that normalization improves the generalization performance of AAS [22]. This improvement can be interpreted as the effect of suppressing shortcut learning.

However, normalization alone is not enough when the portfolio consists of comparison-based algorithms. Comparison-based algorithms, such as CMA-ES, search for solutions using only the order of objective values [10]. Their search behavior is therefore invariant to strictly increasing transformations of the objective values [7]. Normalization makes the model’s input invariant only to positive affine transformations. As the left panel of Figure 1 shows, a strictly increasing transformation changes some ELA feature values without changing the search behavior of CMA-ES. Thus, shortcut learning can still occur for comparison-based algorithms.

Figure 1. Even ELA features computed from normalized objective values give a model a shortcut for predicting algorithm performance. A strictly increasing transformation of the objective values does not change the search behavior of a comparison-based algorithm such as CMA-ES (top left), but changes the ELA feature values (bottom left). The model trained on all ELA features (all) scores R2=0.85R^2 = 0.85 on the original test instances but only 0.23 on the transformed ones (right), although the target is the same. The model trained only on features invariant to the transformation (invariant, Sec. 5.4) keeps R2=0.45R^2 = 0.45 on both test sets. Both models regress the probability that BIPOP CMA-ES beats Adaptive Nelder–Mead on 10-dimensional BBOB (Sec. 6.2).

To investigate shortcut learning in AAS and AAC, we propose the Rubber Ruler Test (§ 3). The test trains a model on the original training instances. It then applies strictly increasing transformations to the objective values of the test instances. It reruns the algorithms on the transformed instances. Finally, it measures the prediction performance of the model on the transformed instances. Measuring a landscape with a rubber ruler does not change the search behavior of comparison-based algorithms. For such algorithms, a model should therefore output the same predictions.

With the Rubber Ruler Test, we investigate shortcut learning and ways to suppress it in feature-based AAS on the BBOB (Black-Box Optimization Benchmarking) test suite [8, 9]. We select algorithms from three groups, defined by how they use objective values. G1 algorithms search using only the order of objective values. G2 algorithms search using the order and adapt their parameters using the values. G3 algorithms search using only the values.

Our first claim is that models can still learn shortcuts for a G1 portfolio even with normalized objective values. As the right panel of Figure 1 shows, a model using all ELA features computed from normalized objective values achieved an R2R^2 of 0.85 on the original test instances. On the Rubber Ruler Test, its R2R^2 dropped to 0.23. This is below 0.45, the R2R^2 of a model using only features invariant to the transformation. Part of the in-distribution R2R^2 of 0.85 therefore comes from relying on information that the algorithms ignore.

Our second claim is that rank-based feature extraction reduces the drop in prediction performance for G1 and G2 portfolios. This extraction computes features from the ranks of objective values. Its R2R^2 stayed at 0.66 for G1 and changed only from 0.62 to 0.61 for G2. In contrast, the R2R^2 of value-based extraction dropped to at most 0.23. Adding the value-based features to the rank-based ones did not reduce the drop (at most 0.25; Figure 4).

Figure 4. Rank-based extraction has the lowest R2R^2 on original test instances but the highest for G1 and G2 on transformed ones.

Our third claim is that data augmentation with transformed training instances improves prediction performance on transformed test instances for every portfolio we studied. For G1 and G2, data augmentation raised the R2R^2 of value-based extraction and concatenation from at most 0.28 to at least 0.53. For G3, it raised their R2R^2 from at most −0.81 to at least 0.13 on average (Figure 6).

Figure 6. Data augmentation raises the R2R^2 of value-based extraction and concatenation on the transformed test instances.

These results suggest an answer to our question. Models should rely only on information that the algorithms use. For comparison-based algorithms, rank-based extraction achieves this by removing the other information from the input. Data augmentation appears to reduce the reliance on such information during training. In-distribution evaluation ranked the feature extractions differently, with rank-based extraction last for every portfolio. We therefore recommend that researchers report the Rubber Ruler Test alongside in-distribution accuracy. The test applies to any AAS, AAC, or performance prediction model that receives information about the objective function. Its results also help researchers choose the feature extraction and whether to augment the training data.

Our contributions are threefold:

  • The Rubber Ruler Test, a test of whether the prediction performance of a model holds under strictly increasing transformations of the objective values (Sec. 4).

  • Evidence that shortcut learning occurs even with normalized objective values (Sec. 6.2).

  • Two remedies and when each applies: rank-based feature extraction for algorithms that search using ranks (Sec. 6.3) and data augmentation for portfolios that mix them with algorithms that search using values (Sec. 6.4).

Related Work

Škvorc et al. showed that positive affine transformations change many ELA feature values [25]. Prager and Trautmann argued that features that are not invariant to these transformations can degrade the generalization performance of models on unseen problem instances [22]. They therefore recommended normalizing objective values before computing features.

Petelin and Cenikj showed that leave-instance-out (LIO) evaluation overestimates AAS performance [20]. LIO evaluation splits the instances of each BBOB function into training and test data. They pointed out that LIO evaluation measures how well a model identifies functions, not AAS performance. They also warned against adopting LIO evaluation as a standard.

This work is novel in two respects. First, we define which transformations features should be invariant to: those that do not change the algorithms’ relative performance, not only positive affine transformations. Second, we show that part of the AAS performance under LIO evaluation can come from shortcut learning, in which a model relies on irrelevant information.

Preliminaries

Black-Box Optimization

In black-box optimization, no analytical information about the objective function is available. An optimization algorithm can use only solutions and their objective values. This work considers single-objective continuous optimization problems with box constraints. Let P\mathcal{P} be a set of problem instances. We define each problem instance p∈Pp \in\mathcal{P} as a pair of a feasible region Xp\mathcal{X}_p and an objective function fpf_p:

p:=(Xp,fp),fp:Xp→R,(1)p := (\mathcal{X}_p, f_p), \qquad f_p:\mathcal{X}_p \to\mathbb{R}, \tag*{(1)}

where Xp⊂Rd\mathcal{X}_p \subset\mathbb{R}^{d} is the dd-dimensional hyperrectangle defined by the box constraints. The goal of optimization is to find a solution with the smallest possible objective value.

Landscape Analysis

Landscape analysis computes a feature vector for a problem instance from sampled solutions and their objective values. In this work, landscape analysis also includes sampling the solutions. Let ω∈Ω\omega\in\Omega be the random seed used in landscape analysis. We define landscape analysis as a mapping

analyzer⁡:P×Ω→Φ,(2)\operatorname{analyzer}:\mathcal{P} \times\Omega\to\Phi, \tag*{(2)}

where Φ\Phi is the feature space. We write the feature vector of problem instance pp obtained with seed ω\omega as ϕp,ω:=analyzer⁡(p,ω)\phi_{p,\omega} := \operatorname{analyzer}(p,\omega).

Automated Algorithm Selection

AAS selects a suitable algorithm for each problem instance to obtain better optimization results. It selects from a set of candidate algorithms A\mathcal{A}. In this work, A\mathcal{A} is a finite set of two or more algorithms, and we call it the algorithm portfolio. A selector selector⁡:Φ→A\operatorname{selector}:\Phi\to\mathcal{A} selects an algorithm from a feature vector. We define AAS as the composition of landscape analysis and the selector:

AAS⁡:=selector⁡∘analyzer⁡:P×Ω→A.(3)\operatorname{AAS} := \operatorname{selector} \circ\operatorname{analyzer}:\mathcal{P} \times\Omega\to\mathcal{A}. \tag*{(3)}

We measure algorithm performance by the mean probability of superiority. Let ξ∈Ξ\xi\in\Xi be the random seed of an algorithm run. We regard each algorithm a∈Aa \in\mathcal{A} as a mapping a:P×Ξ→Ra:\mathcal{P} \times\Xi\to\mathbb{R}. This mapping takes a problem instance pp and a random seed ξ\xi and returns the smallest objective value found within a fixed evaluation budget. Using independent random seeds ξ\xi and ξ′\xi', we define the probability of superiority [28] of aa over a′a' as

PS⁡(p,a,a′):=Pr⁡(a(p,ξ)<a′(p,ξ′))\operatorname{PS}(p,a,a') := \Pr\left(a(p,\xi) < a'(p,\xi')\right)
+12Pr⁡(a(p,ξ)=a′(p,ξ′)).(4)\qquad+ \frac{1}{2}\Pr\left(a(p,\xi) = a'(p,\xi')\right). \tag*{(4)}

We then define the mean probability of superiority of aa as

J(p,a):=1∣A∣−1∑a′∈A∖{a}PS⁡(p,a,a′).(5)J(p,a) := \frac{1}{|\mathcal{A}|-1}\sum_{a' \in\mathcal{A}\setminus\{a\}} \operatorname{PS}(p,a,a'). \tag*{(5)}

If each algorithm runs once independently, J(p,a)J(p,a) is the expected fraction of the other algorithms that aa beats, counting ties as 1/21/2. For each problem instance pp, AAS should select an algorithm

a∗(p)∈arg max⁡a∈AJ(p,a),a^{*}(p) \in\underset{a \in\mathcal{A}}{\operatorname{arg\,max}} J(p,a),

that is, an algorithm that beats the most other algorithms on average.

The selector predicts the mean probability of superiority of each algorithm by regression and selects the algorithm with the largest predicted value. For each algorithm a∈Aa \in\mathcal{A}, a predictor predictor⁡a:Φ→[0,1]\operatorname{predictor}_{a}:\Phi\to[0,1] maps a feature vector ϕp,ω\phi_{p,\omega} to a prediction of J(p,a)J(p,a). We define the selector, with ties broken arbitrarily, as

selector⁡(ϕ):=arg max⁡a∈A predictor⁡a(ϕ).(6)\operatorname{selector}(\phi) := \underset{a \in\mathcal{A}}{\operatorname{arg\,max}}\ \operatorname{predictor}_{a}(\phi). \tag*{(6)}

We use regression because it takes into account how much a wrong selection loses, J(p,a∗(p))−J(p,a)J(p,a^{*}(p))-J(p,a). Classification with only a∗(p)a^{*}(p) as the label treats all wrong selections equally.

Shortcut Learning

Shortcut learning occurs when a predictor relies on a part of its input that helps prediction only during training [5]. We define a predictor h:Z→Rh:\mathcal{Z} \to\mathbb{R} as a function that predicts a target y∈Ry \in\mathbb{R} from an input z∈Zz \in\mathcal{Z}. We assume that the pair (z,y)(z,y) follows a distribution Dtrain\mathcal{D}_{\mathrm{train}} during training and a distribution Ddeploy\mathcal{D}_{\mathrm{deploy}} during deployment. For the predictors in AAS (Eq. (6)), hh, zz, and yy correspond to predictor⁡a\operatorname{predictor}_{a}, ϕp,ω\phi_{p,\omega}, and J(p,a)J(p,a), respectively. We split the input zz into two parts, z=(zcore,zspurious)z=(z_{\mathrm{core}},z_{\mathrm{spurious}}). We write LD\mathcal{L}_{\mathcal{D}} for the conditional independence under a distribution D\mathcal{D} and ̸ ⁣⊥D\not\!\perp_{\mathcal{D}} for its negation. If zcorez_{\mathrm{core}} and zspuriousz_{\mathrm{spurious}} satisfy both

zspurious⊥Dtrainy∣zcore,z_{\mathrm{spurious}} \perp_{\mathcal{D}_{\mathrm{train}}} y \mid z_{\mathrm{core}},
zspurious⊥Ddeployy∣zcore,(7)z_{\mathrm{spurious}} \perp_{\mathcal{D}_{\mathrm{deploy}}} y \mid z_{\mathrm{core}}, \tag*{(7)}

we call zcorez_{\mathrm{core}} the core feature and zspuriousz_{\mathrm{spurious}} the spurious feature. In other words, during training, the spurious feature carries information about yy that the core feature lacks. During deployment, it carries no such information. With these terms, shortcut learning means that a predictor relies on the spurious feature.

Rubber Ruler Test

The Rubber Ruler Test checks whether the prediction performance of a trained model holds when a strictly increasing transformation is applied to the objective values. The user provides the elements in the upper part of Table 1; the test fixes the rest.

ElementSetting
Provided by the user
Portfolio—
Landscape analysis—
Learning model—
Training instances—
Test instances—
Fixed by the test
Number of samples for f^pmin⁡,f^pmax⁡\hat{f}^{\min}_{p},\hat{f}^{\max}_{p}1000d1000d, or known values
Number of intervals KKUniform on {4,…,7}\{4,\ldots,7\}
Heights ckc_kN(0,σ2)\mathcal{N}(0,\sigma^2), σ=1\sigma=1
Evaluation metric for predictorsR2R^2
Evaluation metric for selectorsΘ\Theta

Table 1. Elements that the user provides (upper part) and that the Rubber Ruler Test fixes (lower part).

Extracting Features

The Rubber Ruler Test compares value-based and rank-based feature extraction. Both pass information about the objective values to the user-provided landscape analysis analyzer. Value-based feature extraction analyzer⁡value\operatorname{analyzer}_{\mathrm{value}} passes the min-max normalized objective values of the sampled solutions. Rank-based feature extraction analyzer⁡rank\operatorname{analyzer}_{\mathrm{rank}} passes the min-max normalized ranks of these objective values and assigns average ranks to ties. For τ∈{value,rank}\tau\in\{\mathrm{value},\mathrm{rank}\}, we write the feature vector as ϕp,ωτ:=analyzer⁡τ(p,ω)\boldsymbol{\phi}^{\tau}_{p,\omega} := \operatorname{analyzer}_{\tau}(p,\omega).

The two feature extractions differ in their invariance. Because of min-max normalization, value-based features are invariant to positive affine transformations but generally not to strictly increasing transformations. Rank-based features are invariant to both, because neither changes the ranks. That is, for any strictly increasing gg and the same seed ω\omega, ϕg∘p,ωrank=ϕp,ωrank\boldsymbol{\phi}^{\mathrm{rank}}_{g\circ p,\omega} = \boldsymbol{\phi}^{\mathrm{rank}}_{p,\omega}, where g∘p:=(Xp,g∘fp)g \circ p := (X_p, g \circ f_p).

Transforming Test Instances

Let ψ\psi be a strictly increasing function on [0,1][0,1] with ψ(0)=0\psi(0)=0 and ψ(1)=1\psi(1)=1. For a problem instance pp, we define the transformation

gψ,p(v):=ψˉ(v−f^pmin⁡f^pmax⁡−f^pmin⁡),(8)g_{\psi,p}(v) := \bar{\psi}\left(\frac{v-\hat{f}^{\min}_{p}}{\hat{f}^{\max}_{p}-\hat{f}^{\min}_{p}}\right), \tag*{(8)}

where f^pmin⁡\hat{f}^{\min}_{p} and f^pmax⁡\hat{f}^{\max}_{p} are the minimum and maximum of fpf_p over 1000d1000d solutions sampled uniformly at random from XpX_p, or the known values. The function ψˉ\bar{\psi} extends ψ\psi outside [0,1][0,1] by the identity. Because ψ(0)=0\psi(0)=0 and ψ(1)=1\psi(1)=1, ψˉ\bar{\psi} is strictly increasing on R\mathbb{R}, so values outside the estimated range also keep their order.

The Rubber Ruler Test draws ψ\psi from a distribution Dspline\mathcal{D}_{\mathrm{spline}} (examples in Figure 8). To draw ψ\psi, we draw the number of intervals KK uniformly from {4,…,7}\{4,\ldots,7\} and heights c0,…,cKc_0,\ldots,c_K independently from N(0,σ2)\mathcal{N}(0,\sigma^2). Let ss be the not-a-knot cubic spline through the points (k/K,ck)(k/K,c_k). Finally, we set

Figure 8. Functions ψ\psi drawn from Dspline\mathcal{D}_{\mathrm{spline}} warp normalized objective values nonlinearly but keep their order. The dashed line is the identity.

ψ(t):=∫0texp⁡(s(u)) du∫01exp⁡(s(u)) du,(9)\psi(t) := \frac{\int_{0}^{t}\exp(s(u))\,\mathrm{d}u}{\int_{0}^{1}\exp(s(u))\,\mathrm{d}u}, \tag*{(9)}

which is strictly increasing because exp⁡(s(u))>0\exp(s(u))>0.

Evaluating Trained Models

The Rubber Ruler Test uses the disjoint training set Ptrain\mathcal{P}_{\mathrm{train}} and test set Ptest\mathcal{P}_{\mathrm{test}} provided by the user, and the transformed test set

P~test:={gψp,p∘p∣p∈Ptest},ψp∼i.i.d.Dspline.(10)\widetilde{\mathcal{P}}_{\mathrm{test}} := \{g_{\psi_p,p}\circ p \mid p\in\mathcal{P}_{\mathrm{test}}\},\qquad\psi_p \overset{\mathrm{i.i.d.}}{\sim}\mathcal{D}_{\mathrm{spline}}. \tag*{(10)}

Each test instance pp and its transformed instance gψp,p∘pg_{\psi_p,p}\circ p share ωp\omega_p and the seeds ξ\xi of all algorithm runs. For each q∈Ptestq\in\mathcal{P}_{\mathrm{test}}, we obtain J(q,a)J(q,a) by running every algorithm on qq.

For each τ\tau and a∈Aa\in\mathcal{A}, the Rubber Ruler Test trains a predictor predictor⁡aτ\operatorname{predictor}^{\tau}_{a} with the same user-provided learning model to predict J(p,a)J(p,a) from ϕp,ωpτ\boldsymbol{\phi}^{\tau}_{p,\omega_p} on p∈Ptrainp\in\mathcal{P}_{\mathrm{train}}. We write its prediction as J^τ(p,a)\hat{J}_{\tau}(p,a).

For a set of problem instances QQ, the Rubber Ruler Test measures prediction performance by Rτ2(Q)R_{\tau}^{2}(Q). This is the coefficient of determination between J^τ(q,a)\hat{J}_{\tau}(q,a) and J(q,a)J(q,a) over q∈Qq\in Q, averaged over a∈Aa\in\mathcal{A}. For a selector, the Rubber Ruler Test instead uses Θ\Theta, the probability of superiority over the single best solver (SBS) [14] Eq. (12). The Rubber Ruler Test reports Rτ2(Ptest)R_{\tau}^{2}(\mathcal{P}_{\mathrm{test}}) and Rτ2(P~test)R_{\tau}^{2}(\widetilde{\mathcal{P}}_{\mathrm{test}}) for each τ\tau. A drop shows that the prediction performance does not hold under the transformation. If the transformation does not change JJ, as for comparison-based algorithms, a drop reveals shortcut learning.

The Rubber Ruler Test also outputs

τ∗∈arg⁡max⁡τ∈{value,rank} Rτ2(P~test).(11)\tau^{*}\in\underset{\tau\in\{\mathrm{value},\mathrm{rank}\}}{\arg\max}\ R_{\tau}^{2}(\widetilde{\mathcal{P}}_{\mathrm{test}}). \tag*{(11)}

Because τ∗\tau^{*} is chosen on P~test\widetilde{\mathcal{P}}_{\mathrm{test}}, its R2R^2 there can be optimistic. If Rτ∗2(P~test)R_{\tau^{*}}^{2}(\widetilde{\mathcal{P}}_{\mathrm{test}}) is still lower than Rτ∗2(Ptest)R_{\tau^{*}}^{2}(\mathcal{P}_{\mathrm{test}}), the user can consider data augmentation. The user can also add candidates to Eq. (11), such as concatenation or data augmentation.

Experimental Setup

Overview

We investigate three research questions:

RQ1 Does shortcut learning occur even with normalized objective values?

RQ2 Does rank-based feature extraction reduce the drop in prediction performance?

RQ3 Does data augmentation improve prediction performance on transformed test instances?

Table 2 shows the tasks and the conditions compared in each RQ. In every task, the predictors predict JJ, and we train and evaluate them with the procedure in § 3.3. All settings and instructions for reproduction are in our repository1. We implemented the code with Claude Code (Anthropic). We verified it through code review, automated tests, run-time checks such as the invariance of JJ for G1, and a script that checks the numbers quoted in the paper against the outputs.

RQCompared conditionsRegression G1Regression G2Regression G3Selection Mixed
RQ1All value-based features / invariant features✓
RQ2Three feature extractions✓✓✓✓
RQ3With / without data augmentation ×\times three feature extractions✓✓✓✓

Table 2. Compared conditions and portfolios in each RQ. All RQs use ELA features. Mixed is the portfolio G1 ∪\cup G2 ∪\cup G3.

We use two tasks: regression and selection. The regression task uses the G1, G2, and G3 portfolios, each of which consists of two algorithms from the same group (Table 3). For G1, the transformation does not change JJ (§ 4.3), so a drop in prediction performance indicates shortcut learning. For G2 and G3, the transformation also changes JJ, so a drop can also come from failing to track this change. The selection task uses the mixed portfolio G1 ∪ G2 ∪ G3 of all six algorithms and measures the performance of AAS by Θ\Theta (§ 4.6).

RQ1 tests whether the min-max normalization in value-based feature extraction (§ 3.1) prevents shortcut learning. In the G1 regression task, we compare a predictor that uses all 59 value-based ELA features (value-based extraction in RQ2) with a baseline that uses only invariant features (§ 4.4). The transformation changes neither the input of the baseline nor JJ. We conclude that shortcut learning occurs if the predictor with all features has a higher median R2R^2 than the baseline before the transformation but a lower median R2R^2 after it. The non-invariant features then carry the spurious feature in Eq. (7), mixed with information that stays valid under the transformation (Sec. 6.4).

RQ2 and RQ3 test the two remedies on both tasks. RQ2 compares three feature extractions: value-based, rank-based, and concatenation (τ=concat\tau= \text{concat}). Concatenation joins the value-based and rank-based feature vectors. We add it to examine whether more information improves prediction performance. RQ3 compares each feature extraction with and without data augmentation, which RQ1 and RQ2 do not use.

Problem Instances

We create 10-dimensional problem instances from the 24 BBOB functions [9], with the feasible region [−5,5]10[-5,5]^{10}. The training set Ptrain\mathcal{P}_{\mathrm{train}} consists of instances 11–110 of each function (2,400 instances). The test set Ptest\mathcal{P}_{\mathrm{test}} consists of instances 1–10 of each function (240 instances). This split is the LIO evaluation in § 1 [20].

We create the transformed test set P^test\hat{\mathcal{P}}_{\mathrm{test}} with the procedure in § 3.3, using the known minimum of each instance as f^pmin⁡\hat{f}^{\min}_{p}. RQ1 and RQ2 use Dspline\mathcal{D}_{\mathrm{spline}}. RQ3 instead uses four distributions that data augmentation does not use: Dspline\mathcal{D}_{\mathrm{spline}} with K∈{2,3}K \in\{2,3\} or

GroupAlgorithmInformation used
G1BIPOP CMA-ES [6]Ranks
G1Adaptive Nelder–Mead [4]Ranks
G2SHADE [26]Ranks and values
G2L-SHADE [27]Ranks and values
G3BOBYQA [21]Values
G3Dual Annealing [31]Values

Table 3. Algorithms and the information about objective values that they use in their search.

K∈{14,…,19}K \in\{14,\ldots,19\}, power functions ψ(t)=tγ\psi(t)=t^\gamma, and piecewise-linear functions (Appendix § 11).

Portfolios and Performance Measurement

We use six algorithms, grouped by the information about objective values that they use in their search (Table 3). Each algorithm runs 31 times on each problem instance, and each run uses 1000dd evaluations, including restarts. Each algorithm restarts when its normalized search scale falls below a threshold; this rule does not use objective values. We estimate the probability of superiority in Eq. (4) from all pairs of runs. Appendix § 11 lists the parameter settings and how we tuned them.

Feature Extraction

We compute ELA features with pflacco [23] from 50d=50050d = 500 solutions sampled by Latin hypercube sampling [17]. We compute the features once for each training instance, with one seed ω\omega, and 11 times for each test instance, with 11 seeds ω\omega. We drop the two features that take a non-finite value on something training or test instance, which leaves 59 features for all experiments. Of the 59 features, 36 depend only on the coordinates of the solutions or on the order of their objective values. We call them invariant features (Appendix § 11) because strictly increasing transformations do not change them.

Appendix E shows that the 48 features of the pretrained Deep-ELA [24] lead to the same conclusions in RQ2 and RQ3.

Learning Model and Data Augmentation

As the learning model, we use RealMLP-TD [13] from pytabkit with its default settings. For each condition, we train predictors with 11 random seeds of the learning model. Appendix § 14 shows the results with random forest [1] and XGBoost [3].

Data augmentation adds one transformed instance gψ,p∘ρg_{\psi,p}\circ\rho with ψp∼Dspline\psi_p\sim\mathcal{D}_{\mathrm{spline}} to the training set for each training instance pp. Each added instance shares ω\omega and the seeds ξ\xi with pp, and we obtain its JJ by running the algorithms on it.

Evaluation Metrics and Aggregation

For regression, we compute Rτ2R^2_{\tau} on the 240 test instances for each ω\omega. In the selection task, we compare AAS, which uses the selector in Eq. (6), with the single best solver (SBS). The SBS is the single algorithm with the highest mean JJ on Ptrain\mathcal{P}_{\mathrm{train}}, which is BIPOP CMA-ES. AAS and the SBS both receive 1050dd evaluations. AAS spends 50dd evaluations on computing features and 1000dd evaluations on running the selected algorithm, and it returns the best objective value among all its evaluations. For a set of problem instances QQ, we define the selection performance as

Θ(Q):=1∣Q∣∑q∈QPS⁡(q,AAS,SBS).(12)\Theta(Q) := \frac{1}{|Q|} \sum_{q \in Q} \operatorname{PS}(q,\mathrm{AAS},\mathrm{SBS}). \tag*{(12)}

A value of Θ>0.5\Theta> 0.5 means that AAS beats the SBS on average. As a reference, we also report Θ\Theta of an Oracle that predicts JJ perfectly. Like AAS, the Oracle spends 50d50d evaluations on computing features and 1000d1000d on the selected algorithm, so it can lose to the SBS.

Each condition gives one Rt2R^2_t and one Θ\Theta for each pair of a seed of the learning model and a seed ω\omega. For each seed of the learning model, we take the median over the 11 seeds ω\omega. In RQ3, we then average over the four distributions. We report the median of the resulting 11 values, and the statistical tests use these values.

Statistical Tests

We test the differences on the transformed test instances with two-sided exact tests at α=0.05\alpha= 0.05 with Holm correction [12] within each family of comparisons (Appendix C). We compare feature extractions with the Wilcoxon signed-rank test [30], paired by the seed of the learning model (11 pairs). We compare training with and without data augmentation with the Mann–Whitney UU test [16] (11 vs. 11 seeds). For RQ1, we also compare the predictor with all features and the baseline with the Wilcoxon signed-rank test, without correction, to supplement the criterion in Sec. 5.1.

These tests cover only the variation across model seeds; “significant” below refers to them. We note where a bootstrap interval over ω\omega and the test instances (Appendix H) includes zero.

Results

Preliminary Analysis

This analysis checks two preconditions for non-invariant features to act as spurious features. Strictly increasing transformations should change these features but not JJ of G1. We measure the change in a feature or in JJ, denoted by η\eta, as

Δη:=1sηmean⁡p∈Ptest∣η(p~)−η(p)∣,(13)\Delta_\eta:= \frac{1}{s_\eta} \underset{p \in P_{\mathrm{test}}}{\operatorname{mean}} \left|\eta(\tilde{p}) - \eta(p)\right|, \tag*{(13)}

where p~:=gψ,p∘ρ\tilde{p} := g_{\psi,p} \circ\rho and sηs_\eta is the standard deviation of η\eta over PtestP_{\mathrm{test}}. The transformation changed only the 23 non-invariant features, with a median change of 0.32 (Figure 3a). JJ of G1 was identical on all 240 instances, and the change in JJ was 0.25 for G2 and 0.80 for G3 (Figure 3b). Both preconditions therefore hold for G1.

Figure 3. Strictly increasing transformations change only non-invariant features, not JJ of G1. The vertical axis, labeled Shift, is Δη\Delta_\eta in Eq. (13). Gray names are invariant features.

RQ1: Does Shortcut Learning Occur Even with Normalized Objective Values?

Shortcut learning occurred in the G1 regression task even with normalized objective values (right panel of Figure 1). Before the transformation, the predictor with all features had an R2R^2 of 0.85, higher than the 0.45 of the baseline. After the transformation, its R2R^2 dropped to 0.23, below the baseline, whose R2R^2 did not change. This result meets the criterion in Sec. 5.1, and the difference between the two predictors after the transformation was significant (p<0.001p < 0.001). With four more draws of ψ\psi, this R2R^2 was between −0.04-0.04 and 0.13 (Appendix I). Random forest and XGBoost agreed (Appendix F).

For G1, only the non-invariant features change (Sec. 6.1). The drop therefore shows that the predictor relied on them, even though it also received all 36 invariant features.

RQ2: Does Rank-Based Feature Extraction Reduce the Drop in Prediction Performance?

Rank-based feature extraction reduced the drop in prediction performance for the G1 and G2 portfolios. After the transformation, rank-based extraction had an R2R^2 of at least 0.61 for G1 and G2, significantly higher than value-based extraction, which had at most 0.23 (Figure 4b). For G1, its R2R^2 did not change, because the transformation changes neither its input nor JJ. For G2, its R2R^2 changed by only 0.01, although JJ changed by 0.25.

Rank-based extraction did not reduce the drop for G3. After the transformation, all feature extractions had a negative R2R^2 for G3 (at most −0.80-0.80; Figure 4b). The transformation changes JJ of G3 the most (Figure 3b), because G3 algorithms search using values. With ψ\psi set to the identity, the rescaling in (8) alone changed JJ of G3 by 0.65 (Appendix I). The acceptance rule of Dual Annealing, unlike BOBYQA, depends on the scale of objective values, which both min-max normalization and ranks remove. This suggests that the input should also keep what the algorithms use.

The drawback of rank-based extraction is a lower R2R^2 before the transformation: 0.15–0.19 lower than that of value-based extraction for every group (Figure 4a). For G1, JJ depends only on the order of objective values. The advantage of value-based extraction for G1 therefore comes at least partly from information that is valid on the original test instances but not under the transformation (Sec. 6.2).

Concatenation avoided this drawback but did not reduce the drop. Its R2R^2 was within 0.01 of that of value-based extraction before the transformation and at most 0.25 for G1 and G2 after it. Concatenation includes all rank-based features, but the learning model still relied on the information that the transformation changes.

In the selection task, rank-based extraction also gave a significantly higher Θ\Theta after the transformation (0.62, versus 0.60 for the others; Figure 5), but the bootstrap interval of this advantage includes zero. Before the transformation, rank-based extraction gave the lowest Θ\Theta (0.65, versus 0.70 for the others).

Figure 5. On the transformed test instances, rank-based feature extraction gives a slightly higher Θ\Theta than the others in the selection task. In each violin, the left half shows the original test instances and the right half shows the transformed ones. The numbers are Θ\Theta.

RQ3: Does Data Augmentation Improve Prediction Performance on Transformed Instances?

Data augmentation significantly raised the R2R^2 of value-based extraction and concatenation on the transformed test instances for every group (Figure 6). For G1 and G2, it raised them from at most 0.28 to at least 0.53; for G3, from negative to positive values on average (Table 14). On the original test instances, it lowered these R2R^2 by 0.06–0.11 (Table 7). Doubling the training set with new untransformed instances did not give this gain (at most 0.27; Appendix I).

Test instancesExtractionELA G1ELA G2ELA G3ELA Θ\ThetaDeep-ELA G1Deep-ELA G2Deep-ELA G3Deep-ELA Θ\Theta
Originalvalue0.850.770.780.7040.850.790.830.707
rank0.660.620.630.6460.620.580.620.643
concat0.850.760.780.7040.830.800.820.708
Transformedvalue0.230.20−0.800.5980.13−0.12−0.720.560
rank0.660.61−0.950.6200.620.57−0.920.612
concat0.250.18−0.800.6000.14−0.02−0.660.566
RQ3, plainvalue0.240.25−0.810.5830.090.04−0.800.543
rank0.660.61−1.050.6190.620.57−0.990.611
concat0.260.28−0.830.5980.190.16−0.740.561
RQ3, aug.value0.580.530.160.6420.440.420.120.606
rank0.660.620.120.6460.610.580.120.642
concat0.690.610.130.6520.610.580.200.645
Original, aug.value0.750.680.71—0.820.760.73—
rank0.660.630.33—0.610.590.33—
concat0.760.700.72—0.790.740.70—

Table 7. All results of RQ2 and RQ3. R2R^2 (G1–G3, regression) and Θ\Theta (mixed portfolio, selection) are medians over 11 model seeds. Original: original test instances. Transformed: test instances transformed by DsplineD_{\mathrm{spline}} (RQ2). RQ3: test instances transformed by the four distributions that data augmentation does not use, without (plain) and with (aug.) data augmentation; Original, aug.: original test instances with data augmentation (Θ\Theta: Table 13). Bold marks the best feature extraction in each column of each block. The Oracle reaches Θ=0.756\Theta= 0.756 on the original and 0.753 on the transformed test instances.

TaskExtractionTrainingDspline,K∈{2,3}\mathcal{D}_{\mathrm{spline}}, K \in\{2, 3\}Dspline,K∈{14,…,19}\mathcal{D}_{\mathrm{spline}}, K \in\{14, \ldots, 19\}PowerPiecewise linear
G1 (R2R^2)valueplain0.3110.1500.2970.191
plain-48000.3070.0740.3020.159
aug.0.6090.5940.5470.590
rankplain0.6610.6610.6610.661
plain-48000.7380.7380.7380.738
aug.0.6550.6550.6550.655
concatplain0.3410.1540.3110.213
plain-48000.3680.1170.3250.190
aug.0.6900.7020.6470.696
G2 (R2R^2)valueplain0.3690.2660.1790.258
plain-48000.4130.2360.1900.264
aug.0.5410.5610.4290.554
rankplain0.6090.6050.6060.624
plain-48000.7190.7080.7060.720
aug.0.6230.6090.6120.625
concatplain0.3880.3000.2300.240
plain-48000.3830.2050.2160.246
aug.0.6280.6410.5260.643
G3 (R2R^2)valueplain−0.841−1.004−0.738−0.723
plain-4800−0.821−0.986−0.660−0.645
aug.0.0350.353−0.0630.239
rankplain−0.945−1.037−1.313−0.923
plain-4800−0.893−0.992−1.230−0.845
aug.0.1830.164−0.0310.143
concatplain−0.857−0.995−0.772−0.705
plain-4800−0.865−1.010−0.703−0.647
aug.−0.0110.366−0.0700.224
Mixed (Θ\Theta)valueplain0.5890.5930.5540.602
plain-48000.5920.5920.5600.610
aug.0.6470.6470.6250.647
rankplain0.6210.6160.6130.624
plain-48000.6350.6290.6300.639
aug.0.6490.6440.6440.648
concatplain0.6040.5980.5760.615
plain-48000.5990.5940.5640.613
aug.0.6570.6580.6410.662

Table 14. Results of RQ3 with ELA on each of the four distributions that data augmentation does not use (medians over 11 model seeds). Training conditions as in Table 13. The main paper reports the mean over the four distributions; for G3, some values stay negative after data augmentation.

After data augmentation, the R2R^2 of concatenation for G1 and G2 was higher than that of value-based extraction (Figure 6b). Compared with rank-based extraction, it was significantly higher for G1 (0.69 vs. 0.66) but not for G2 (0.61 vs. 0.62); the bootstrap interval of the G1 difference includes zero. Value-based extraction remained significantly below rank-based extraction (0.58 vs. 0.66 and 0.53 vs. 0.62). A non-invariant feature can mix information that the algorithms use and ignore. Data augmentation appears to have reduced the reliance on the latter (its predictions for G1 changed less; Appendix I), so concatenation could match rank-based extraction.

For G1 and G2, data augmentation did not significantly change the R2R^2 of rank-based extraction (at most 0.01). For G1, the added instances match the original ones in rank-based features and JJ. New untransformed instances instead raised this R2R^2 to 0.74 and 0.71, above every extraction with data augmentation (Appendix I).

For G3, data augmentation also raised the R2R^2 of rank-based extraction, from −1.05 to 0.12, but the drop remained. The R2R^2 for G3 was at most 0.16 on the transformed test instances, and the R2R^2 of rank-based extraction on the original ones fell from 0.63 to 0.33 (Table 7). The gain of value-based extraction and concatenation for G3 depends on ψ\psi accompanying the rescaling, because only ψ\psi changes their input (Appendix I).

In the selection task, data augmentation significantly raised Θ\Theta for every feature extraction, by 0.03–0.06 (Figure 7). After data augmentation, all three feature extractions reported 0.64–0.65; on the original test instances, data augmentation lowered the Θ\Theta of value-based extraction and concatenation by 0.02 (Appendix I).

Figure 7. Data augmentation raises Θ\Theta on the transformed test instances for every feature extraction. In each violin, the right half is with data augmentation.

Discussion

  • Diverse training instances may not be enough. Even in diverse training instances, as in MA-BBOB [29], the labels can correlate with information that the algorithms ignore. Weakening this correlation may require instances that change such information but not JJ, as data augmentation does (Sec. 6.4).

  • The test also applies to AAC and feature-free methods. It requires only a model that predicts algorithm performance from objective values, whether the model also takes a configuration or takes the sampled solutions directly.

  • Limitation: shifts the remedies do not address. The first kind keeps the order of objective values but changes algorithm performance, as the rescaling in Eq. (8) does for G3. No remedy we studied removed the drop for G3 (Sec. 6.4). The second kind changes the order itself, as on unseen functions, which the test does not cover. As in prior work on unseen problems [2], leave-one-function-out evaluation gave a median R2R^2 of at most −0.16-0.16 in every condition (Appendix G).

  • Limitation: scope of the evidence. RQ1 is an existence result, for which one portfolio suffices. Its direct evidence is a G1 portfolio on 10-dimensional BBOB with one budget and sample size, LIO evaluation, the known minimum as f^pmin⁡\hat{f}_p^{\min}, the range [0,1][0, 1] in Eq. (8), and σ=1\sigma= 1. With functions also resampled, the RQ1 baseline comparison is inconclusive (Appendix H).

  • Future work. Methods without supervised learning, such as those based on reinforcement learning [15] and large language models [32], also receive objective values and should be tested.

Conclusion

We proposed the Rubber Ruler Test and used it to show that shortcut learning can occur in feature-based AAS even with normalized objective values. Because in-distribution accuracy can hide shortcut learning, we recommend reporting the test alongside it. The Rubber Ruler Test is available as the Python package rubberruler2. Rank-based feature extraction suits algorithms that search using ranks and requires no extra runs. Data augmentation improved prediction on transformed instances for every portfolio we studied but requires

extra algorithm runs; for G1 and G2, new instances with rank-based extraction gave a higher R2R^2 there (not tested for significance). On the original instances, rank-based extraction lowered R2R^2 by 0.15–0.19, and data augmentation lowered it by up to 0.31. Feature designers should ask which information the algorithms use and check the answer with the test.

Acknowledgments

JSPS KAKENHI Grant Number JP25K21301 supported this work. Claude Code and Claude (Anthropic) assisted with implementing the experimental code and writing the paper. The authors verified all code and content and take full responsibility for them.

Shortcut Learning Increases the Deployment Error

This appendix shows that relying on the spurious feature (§ 2.4) increases the deployment error. Let hˉ(zcore):=E[h(z)∣zcore]\bar{h}(z_{\mathrm{core}}) := \mathbb{E}[h(z) \mid z_{\mathrm{core}}] be the predictor averaged over the spurious feature, with all expectations under Ddeploy\mathcal{D}_{\mathrm{deploy}}. Then

E[(h(z)−y)2]=E[(hˉ(zcore)−y)2]+E[(h(z)−hˉ(zcore))2],(14)\mathbb{E}[(h(z)-y)^2] = \mathbb{E}[(\bar{h}(z_{\mathrm{core}})-y)^2] + \mathbb{E}[(h(z)-\bar{h}(z_{\mathrm{core}}))^2], \tag*{(14)}

because the cross term vanishes by the definition of hˉ\bar{h} and the second condition of Eq. (7). The second term is the variation of the output caused by the spurious feature; it is positive whenever h(z)≠hˉ(zcore)h(z) \ne\bar{h}(z_{\mathrm{core}}) with positive probability, and we then say that hh relies on the spurious feature. Hence a predictor that relies on the spurious feature has a larger deployment error than the same predictor with this reliance removed. This argument requires the second condition of Eq. (7) to hold exactly under Ddeploy\mathcal{D}_{\mathrm{deploy}}. The non-invariant features do not satisfy it as a whole, because they also carry information that stays valid under the transformation (Sec. 6.4); the argument applies to the part of their information that loses its relation to yy. In the Rubber Ruler Test, we take zcorez_{\mathrm{core}} to be the information that the transformation does not change. For G1, JJ does not change either, so any change in the predictions comes from the reliance on zspuriousz_{\mathrm{spurious}}.

Examples of Transformations

Figure 8 shows functions ψ\psi drawn from Dspline\mathcal{D}_{\mathrm{spline}} (§ 3.2).

Experimental Details

All settings and instructions for reproduction are in our repository (§ 4.1).

Algorithms and predictors. The restart rule based on the search scale replaces the default termination criteria of every algorithm, and we disable the criteria based on objective values, such as those of BIPOP CMA-ES. SHADE and L-SHADE select solutions by comparison only but weight their parameter adaptation by the size of improvements in objective value. BOBYQA fits a quadratic model to objective values, and Dual Annealing accepts solutions based on differences in objective value. For the two-algorithm portfolios, J(p,a2)=1−J(p,a1)J(p,a_2) = 1 - J(p,a_1), so we train only the predictor for a1a_1 and predict a2a_2 by 1−J^(p,a1)1 - \hat{J}(p,a_1); for the mixed portfolio, we train one predictor per algorithm. On the sampled solutions, rank-based input equals a strictly increasing transformation of the objective values, so it is a valid input to Deep-ELA.

Distributions in RQ3. The four distributions that data augmentation does not use are Dspline\mathcal{D}_{\mathrm{spline}} with K∈{2,3}K \in\{2,3\}, Dspline\mathcal{D}_{\mathrm{spline}} with K∈{14,…,19}K \in\{14,\ldots,19\}, power functions ψ(t)=tγ\psi(t) = t^\gamma, and piecewise-linear functions. For power functions, log⁡γ∼N(0,1)\log\gamma\sim\mathcal{N}(0,1). For piecewise-linear functions, we draw the number of interior breakpoints uniformly from {4,…,7}\{4,\ldots,7\}, their positions uniformly from (0,1)(0,1), and the slope of each interval from exp⁡(N(0,1))\exp(\mathcal{N}(0,1)), and normalize so that ψ(1)=1\psi(1) = 1.

Families for Holm correction. We correct ELA and Deep-ELA separately. In RQ2, a family is the three pairwise comparisons of feature extractions for each portfolio. In RQ3, a family is the three pairwise comparisons for each portfolio and training condition; for data augmentation, a family is the nine cells (three portfolios ×\times three extractions) in the regression task and the three extractions in the selection task.

Tuned parameters. Tables 4 and 5 list the tuned parameters; all others are published settings or library defaults. All tuning used instance 11 of each of the 24 functions, which is a training instance, with 31 runs per configuration. In the regression task, we tuned only the weaker algorithm of each pair. We chose the parameters that minimize the Kolmogorov–Smirnov distance between the distribution of the probability of superiority over the 24 functions and the uniform distribution. The purpose is to spread the regression target over [0,1][0,1] (Figure 9). In the selection task, we tuned all six algorithms over one grid of 1,230 configurations. The score of a configuration on a function is its mean probability of superiority over the other configurations in the grid. For selection (budget 1000d1000d), we chose the combination of configurations that maximizes the mean over the 24 functions of the highest score among the six algorithms. For the SBS (budget 1050d1050d), we chose for each algorithm the configuration with the highest mean score. The SBS is then the algorithm with the highest mean JJ over the training instances, which is BIPOP CMA-ES.

Figure 9. Tuning brought the distribution of the probability of superiority closer to uniform. Histograms before and after tuning over the 24 functions used for tuning in the regression task; the horizontal dashed line is the uniform distribution.

AlgorithmSelected parameters
Adaptive Nelder–Meadoffset 0.25, εx=10−4\varepsilon_x = 10^{-4}
SHADEN=5dN = 5d, MF=0.7M_F = 0.7, MCR=0.4M_{CR} = 0.4, εx=10−8\varepsilon_x = 10^{-8}
Dual AnnealingT0=5230T_0 = 5230, qv=1.5q_v = 1.5, qa=−5q_a = -5, εx=10−8\varepsilon_x = 10^{-8}

Table 4. Tuned algorithms and parameters in the regression task. The offset is the shift of the initial simplex vertices from the start point relative to the width of the search range.

Invariant features. Table 6 lists the invariant features of each group, chosen from the feature definitions. In the preliminary analysis (§ 5.1), these 36 features did not change and the other 23 did. We removed two features because they take a non-finite value on some instance: ela_meta.quad_simple.cond on f5f_5, and ic.eps_ratio on test instances transformed by power functions. This follows the rule in § 4.4, which uses the features of the test instances but not their JJ. We apply the rule over all training and test instances so that every experiment uses the same 59 features; over the training instances alone, it would remove only the first of the two.

GroupNo.Invariant features
disp16all (16)
ela_level9all (9)
ela_meta8none
pca8the 4 computed from coordinates only (ending in _x)
fitness_distance6distance_mean, distance_std (2)
nbc5all but nb_fitness.cor (4)
ic4m0 (1)
ela_distr3none
Total5936

Table 6. Number of all and invariant ELA features in each group.

Preliminary Analysis

This appendix checks two preconditions for non-invariant features to act as spurious features: strictly increasing transformations change these features, but they do not change JJ of G1. We compare each test instance p∈Ptestp \in\mathcal{P}_{\mathrm{test}} with its transformed instance p~:=gψp,p∘p\tilde{p} := g_{\psi_p,p} \circ p (§ 3.3). For each of G1, G2, and G3, we compute JJ of the two algorithms in the group. We measure the change Δη\Delta_\eta of a feature or of JJ with Eq. (13) of the main paper. Dividing by the standard deviation lets us compare features and JJ on the same scale. For features, we report the median of Δη\Delta_\eta over the 11 seeds ω\omega. § 5.1 of the main paper reports the results (Figure 3). The change in JJ increases from G1 to G3. This order matches how the algorithms use objective values: G2 uses them only to adapt its parameters, whereas G3 uses them directly in its search. The rescaling in Eq. (8) alone changes JJ of G3 by 0.65 (Appendix § 17).

Deep-ELA Results and All Numbers

This appendix repeats RQ2 and RQ3 of the main paper with the 48 features of the pretrained Deep-ELA instead of the 59 ELA features. We use Deep-ELA without retraining it, and all other settings are the same as in the main paper. We do not use Deep-ELA in RQ1, because it has no invariant features: the transformation changed all 48 of its features, with a median Δη\Delta_\eta of 0.62 (Figure 10).

Figure 10. Strictly increasing transformations change all 48 Deep-ELA features. Axes as in Fig. 3.

Deep-ELA led to the same conclusions as ELA in RQ2 and RQ3. In RQ2, rank-based feature extraction gave the lowest R2R^2 on the original test instances but the highest R2R^2 for G1 and G2 on the transformed test instances (Figure 11). In the selection task, it also gave the highest Θ\Theta on the transformed test instances, with a larger advantage than ELA (Figure 13). In RQ3, data augmentation raised the R2R^2 of value-based extraction and concatenation on the transformed test instances (Figure 12) and raised Θ\Theta for every feature extraction (Figure 13).

(a) Original test instances.

(b) Transformed test instances.

Figure 11. RQ2 with Deep-ELA. Rank-based feature extraction gives the lowest R2R^2 on the original test instances but the highest R2R^2 for G1 and G2 on the transformed test instances.

Bar chart of $R^2$ for G1, G2, and G3 without data augmentation using value-based, rank-based, and concat feature extraction

(a) Without data augmentation.

(b) With data augmentation.

Figure 12. RQ3 with Deep-ELA. Data augmentation raises the R2R^2 of value-based extraction and concatenation on the transformed test instances. The test instances are transformed with four distributions that data augmentation does not use.

Figure 13. (a) RQ2. Left halves: original; right halves: transformed. (b) RQ3. Left halves: without data augmentation; right halves: with data augmentation (transformed test instances). Selection task with Deep-ELA. On the transformed test instances, rank-based feature extraction gives the highest Θ\Theta (left), and data augmentation raises Θ\Theta for every feature extraction (right). The numbers are Θ\Theta.

All numbers. Table 7 lists all results of RQ2 and RQ3 for ELA and Deep-ELA.

Other Learning Models

We replaced the learning model with random forest (scikit-learn defaults [19]) and XGBoost (the tuned defaults XGB-TD of Holzmüller et al. [13]); all other settings are the same as in the main paper. With both models, the main conclusions of RQ1–RQ3 did not change: shortcut learning in RQ1, the advantage of rank-based extraction for G1 and G2 in RQ2, and the gain from data augmentation for value-based extraction and concatenation in RQ3. Some other comparisons differed in significance. Most of them were not significant with RealMLP, such as concatenation versus value-based extraction in the selection task; with XGBoost and ELA, rank-based extraction for G3 was no longer significantly below value-based extraction. Table 8 lists the levels.

TaskExtractionRandom forest ELARandom forest Deep-ELAXGBoost ELAXGBoost Deep-ELA
RQ1G1 all features, original0.834–0.831–
G1 all features, transformed0.174–0.167–
G1 invariant features0.429–0.410–
RQ2G1 value0.1740.1950.1670.176
G1 rank0.6210.5750.6120.569
G1 concat0.1600.2520.1790.219
G2 value0.0990.0260.082−0.020
G2 rank0.5670.5780.5710.570
G2 concat0.0930.0840.0910.011
G3 value−0.735−0.609−0.756−0.664
G3 rank−0.767−0.790−0.794−0.821
G3 concat−0.748−0.603−0.739−0.649
Θ\Theta value0.5780.5480.5820.545
Θ\Theta rank0.5990.5930.6070.600
Θ\Theta concat0.5860.5540.5840.553
RQ3G1 value0.227 / 0.5000.201 / 0.4480.250 / 0.5200.151 / 0.440
G1 rank0.621 / 0.6230.575 / 0.5730.612 / 0.6050.569 / 0.569
G1 concat0.235 / 0.6320.276 / 0.5820.255 / 0.6210.232 / 0.585
G2 value0.191 / 0.4750.199 / 0.4110.182 / 0.4860.171 / 0.413
G2 rank0.586 / 0.5810.580 / 0.5870.584 / 0.5700.572 / 0.574
G2 concat0.183 / 0.5790.254 / 0.5670.191 / 0.5740.216 / 0.576
G3 value−0.630 / 0.255−0.709 / 0.156−0.655 / 0.216−0.804 / 0.136
G3 rank−0.835 / 0.156−0.849 / 0.134−0.869 / 0.113−0.887 / 0.109
G3 concat−0.624 / 0.295−0.681 / 0.235−0.621 / 0.257−0.769 / 0.226
Θ\Theta value0.575 / 0.6190.535 / 0.5940.583 / 0.6220.531 / 0.597
Θ\Theta rank0.599 / 0.6300.593 / 0.6260.607 / 0.6280.600 / 0.624
Θ\Theta concat0.579 / 0.6340.544 / 0.6230.584 / 0.6380.545 / 0.627

Table 8. Levels with random forest and XGBoost (medians over 11 model seeds). RQ1: R2R^2 for G1 on the original and the transformed test instances. RQ2: R2R^2 and Θ\Theta on the test instances transformed by Dspline\mathcal{D}_{\mathrm{spline}}. RQ3: R2R^2 and Θ\Theta on the test instances transformed by the four distributions that data augmentation does not use, without / with data augmentation.

Random forest.

  • RQ1: the R2R^2 of the predictor with all features dropped from 0.83 to 0.17, whereas that of the baseline stayed at 0.43 (Figure 14).

  • RQ2: on the transformed test instances, the R2R^2 of rank-based extraction for G1 and G2 was at least 0.57, whereas at most 0.25 for value-based extraction and concatenation; for G3, all extractions had a negative R2R^2. Before the transformation, the R2R^2 of rank-based extraction was lower than that of value-based extraction.

Figure 14. Shortcut learning in the G1 regression task also occurs with random forest and XGBoost. Axes as in the right panel of Figure 1.

  • RQ3: data augmentation reduced the drop of value-based extraction and concatenation for every group (from negative to positive values for G3); value-based extraction stayed below rank-based extraction for G1 and G2; data augmentation raised Θ\Theta for every feature extraction.

XGBoost.

  • RQ1: the R2R^2 of the predictor with all features dropped from 0.83 to 0.17, whereas that of the baseline stayed at 0.41 (Figure 14).

  • RQ2: on the transformed test instances, the R2R^2 of rank-based extraction for G1 and G2 was at least 0.57, versus at most 0.22 for value-based extraction and concatenation; for G3, all extractions had a negative R2R^2. Before the transformation, the R2R^2 of rank-based extraction was lower than that of value-based extraction.

  • RQ3: the same as for random forest.

Generalization to Unseen Functions

Our remedies address distribution shifts that keep the order of objective values (Sec. 7); unseen functions are not such a shift. We checked whether the remedies nevertheless improve the generalization of the regression of JJ to unseen functions with leave-one-function-out (LOFO) cross-validation. Each of the 24 folds trains on the training instances of 23 functions (2,300 instances) and predicts JJ on the 10 untransformed test instances of the held-out function; data augmentation adds transformed copies of the 2,300 instances as in RQ3. Conditions, learning models, seeds, and ω\omega are the same as in RQ3. We compute R2R^2 once per pair of model seed and ω\omega over the pooled 240 predictions. The LOFO R2R^2 was negative in all 36 conditions (Table 9), with medians from −0.94 to −0.16; even the upper quartile over seeds was negative in every condition (at most −0.10). The remedies changed the magnitude but not the sign, so none of them helped on unseen functions.

ExtractionAugmentationELA G1ELA G2ELA G3Deep-ELA G1Deep-ELA G2Deep-ELA G3
valueno−0.86−0.94−0.20−0.61−0.69−0.20
yes−0.81−0.67−0.34−0.51−0.58−0.38
rankno−0.70−0.65−0.32−0.69−0.65−0.38
yes−0.63−0.63−0.37−0.72−0.67−0.49
concatno−0.89−0.90−0.20−0.57−0.63−0.16
yes−0.73−0.66−0.35−0.58−0.66−0.50

Table 9. LOFO R2R^2 is negative in every condition (median over 11 model seeds).

Bootstrap Intervals

The tests in the main paper cover only the variation across seeds of the learning model (Sec. 5.7). This appendix gives percentile bootstrap intervals that also cover the seeds ω\omega and the test instances. Each of 10,000 bootstrap samples draws with replacement the 11 model seeds, the 11 seeds ω\omega, and, for each of the 24 functions, its 10 test instances. For each sample, we recompute R2R^2 on the drawn instances and Θ\Theta as their mean. As for the levels in the main paper, we then take the median over ω\omega for each model seed and the median over the model seeds. We take each difference within a sample. For data augmentation, we draw the model seeds of the two training conditions independently, as in the Mann–Whitney UU test. The interval runs from the 2.5th to the 97.5th percentile of the difference.

This procedure keeps the 24 functions fixed, as LIO evaluation does. A second version also draws the 24 functions with replacement before it draws their instances. It asks whether a difference would hold on other functions, which our experiments do not test (Appendix § 15). Table 10 and Table 11 list both intervals.

Table 10: Bootstrap 95% intervals of the differences with ELA. Estimate: the difference of the levels in the main paper. Functions fixed: resampling model seeds, ω\omega, and the test instances of each function. Functions resampled: resampling the 24 functions as well. †: the interval includes zero.

TaskTest instancesDifferenceEstimateFunctions fixedFunctions resampled
RQ1G1transformedinvariant − all features0.219[0.073, 0.343][−0.100, 0.621]†
G1−original − transformed, all features0.619[0.486, 0.740][0.352, 1.085]
G1−original − transformed, invariant features0.000[0.000, 0.000][0.000, 0.000]
G1originalall − invariant features0.400[0.341, 0.469][0.276, 0.617]
RQ2G1transformedrank − value0.428[0.287, 0.556][0.144, 0.869]
G1transformedrank − concat0.407[0.256, 0.559][0.133, 0.848]
G1originalrank − value−0.190[−0.242, −0.140][−0.326, −0.102]
G2transformedrank − value0.411[0.248, 0.537][0.142, 0.704]
G2transformedrank − concat0.423[0.260, 0.573][0.135, 0.748]
G2originalrank − value−0.148[−0.215, −0.093][−0.283, −0.062]
G3transformedrank − value−0.151[−0.312, 0.005]†[−0.575, 0.295]†
G3transformedrank − concat−0.145[−0.320, 0.061]†[−0.558, 0.333]†
G3originalrank − value−0.149[−0.205, −0.108][−0.319, −0.056]
G1−original − transformed, rank0.000[0.000, 0.000][0.000, 0.000]
G1−original − transformed, concat0.595[0.451, 0.743][0.340, 1.059]
G2−original − transformed, value0.574[0.418, 0.712][0.340, 0.895]
G2−original − transformed, rank0.015[−0.022, 0.063]†[−0.042, 0.088]†
G2−original − transformed, concat0.575[0.427, 0.736][0.331, 0.935]
Θ\Thetatransformedrank − value0.021[−0.005, 0.046]†[−0.044, 0.086]†
Θ\Thetatransformedrank − concat0.020[−0.008, 0.042]†[−0.047, 0.082]†
RQ3G1transformedaugmented − plain, value0.337[0.271, 0.412][0.154, 0.648]
G1transformedaugmented − plain, rank−0.006[−0.044, 0.037]†[−0.056, 0.053]†
G1transformedaugmented − plain, concat0.425[0.343, 0.534][0.240, 0.759]
G2transformedaugmented − plain, value0.273[0.191, 0.320][0.090, 0.453]
G2transformedaugmented − plain, rank0.003[−0.026, 0.072]†[−0.045, 0.099]†
G2transformedaugmented − plain, concat0.333[0.251, 0.408][0.166, 0.544]
G3transformedaugmented − plain, value0.970[0.831, 1.090][0.368, 2.269]
G3transformedaugmented − plain, rank1.170[0.995, 1.292][0.438, 2.582]
G3transformedaugmented − plain, concat0.965[0.849, 1.111][0.391, 2.310]
G1originalaugmented − plain, value−0.106[−0.146, −0.059][−0.193, −0.033]
G1originalaugmented − plain, rank−0.006[−0.044, 0.037]†[−0.056, 0.053]†
G1originalaugmented − plain, concat−0.086[−0.130, −0.042][−0.176, −0.021]
G2originalaugmented − plain, value−0.086[−0.138, −0.044][−0.192, −0.015]
G2originalaugmented − plain, rank0.011[−0.029, 0.071]†[−0.048, 0.099]†
G2originalaugmented − plain, concat−0.056[−0.105, −0.012][−0.144, 0.007]†
G3originalaugmented − plain, value−0.074[−0.120, −0.037][−0.162, −0.014]
G3originalaugmented − plain, rank−0.307[−0.354, −0.259][−0.557, −0.085]
G3originalaugmented − plain, concat−0.064[−0.108, −0.030][−0.139, 0.008]†
Θ\Thetatransformedaugmented − plain, value0.058[0.046, 0.068][0.020, 0.101]
Θ\Thetatransformedaugmented − plain, rank0.027[0.016, 0.045][−0.006, 0.088]†
Θ\Thetatransformedaugmented − plain, concat0.054[0.045, 0.070][0.019, 0.104]
G1transformedconcat − rank, augmented0.031[−0.014, 0.077]†[−0.043, 0.109]†
G1transformedconcat − value, augmented0.104[0.057, 0.148][0.033, 0.196]
G1transformedrank − value, augmented0.073[0.014, 0.131][−0.019, 0.182]†
G2transformedconcat − rank, augmented−0.004[−0.061, 0.031]†[−0.099, 0.063]†
G2transformedconcat − value, augmented0.087[0.042, 0.135][0.025, 0.175]
G2transformedrank − value, augmented0.091[0.050, 0.152][0.008, 0.217]
G3transformedconcat − rank, augmented0.018[−0.066, 0.133]†[−0.118, 0.232]†
G3transformedconcat − value, augmented−0.024[−0.062, 0.071]†[−0.089, 0.098]†
G3transformedrank − value, augmented−0.042[−0.131, 0.072]†[−0.229, 0.134]†
Θ\Thetatransformedconcat − rank, augmented0.006[−0.005, 0.020]†[−0.024, 0.042]†
Θ\Thetatransformedconcat − value, augmented0.010[0.004, 0.022][−0.001, 0.030]†
Θ\Thetatransformedrank − value, augmented0.004[−0.008, 0.019]†[−0.034, 0.043]†

Table 10.

TaskTest instancesDifferenceEstimateFunctions fixedFunctions resampled
RQ2G1 transformedrank − value0.484[0.335, 0.620][0.199, 0.912]
G1 transformedrank − concat0.480[0.317, 0.606][0.191, 0.885]
G1 originalrank − value−0.230[−0.302, −0.165][−0.411, −0.122]
G2 transformedrank − value0.686[0.526, 0.856][0.341, 1.170]
G2 transformedrank − concat0.593[0.433, 0.758][0.227, 1.070]
G2 originalrank − value−0.210[−0.284, −0.147][−0.381, −0.094]
G3 transformedrank − value−0.204[−0.450, −0.013][−0.957, 0.371]†
G3 transformedrank − concat−0.256[−0.467, −0.083][−0.905, 0.195]†
G3 originalrank − value−0.205[−0.249, −0.147][−0.366, −0.095]
G1 –original − transformed, rank0.000[0.000, 0.000][0.000, 0.000]
G1 –original − transformed, concat0.698[0.554, 0.826][0.445, 1.125]
G2 –original − transformed, value0.910[0.761, 1.081][0.646, 1.377]
G2 –original − transformed, rank0.014[−0.025, 0.056]†[−0.044, 0.079]†
G2 –original − transformed, concat0.821[0.668, 0.986][0.538, 1.287]
θ transformedrank − value0.052[0.018, 0.084][−0.034, 0.128]†
θ transformedrank − concat0.046[0.016, 0.080][−0.029, 0.118]†
RQ3G1 transformedaugmented − plain, value0.350[0.282, 0.422][0.165, 0.646]
G1 transformedaugmented − plain, rank−0.003[−0.038, 0.033]†[−0.054, 0.048]†
G1 transformedaugmented − plain, concat0.426[0.367, 0.506][0.259, 0.743]
G2 transformedaugmented − plain, value0.385[0.317, 0.462][0.218, 0.641]
G2 transformedaugmented − plain, rank0.010[−0.025, 0.053]†[−0.045, 0.078]†
G2 transformedaugmented − plain, concat0.428[0.351, 0.508][0.221, 0.735]
G3 transformedaugmented − plain, value0.923[0.810, 1.061][0.482, 1.952]
G3 transformedaugmented − plain, rank1.115[1.003, 1.287][0.475, 2.459]
G3 transformedaugmented − plain, concat0.940[0.823, 1.073][0.466, 2.026]
G1 originalaugmented − plain, value−0.028[−0.065, 0.008]†[−0.083, 0.021]†
G1 originalaugmented − plain, rank−0.003[−0.038, 0.033]†[−0.054, 0.048]†
G1 originalaugmented − plain, concat−0.041[−0.094, −0.006][−0.123, 0.007]†
G2 originalaugmented − plain, value−0.032[−0.079, 0.005]†[−0.110, 0.019]†
G2 originalaugmented − plain, rank0.008[−0.028, 0.055]†[−0.048, 0.078]†
G2 originalaugmented − plain, concat−0.061[−0.109, −0.015][−0.147, 0.003]†
G3 originalaugmented − plain, value−0.099[−0.144, −0.065][−0.215, −0.023]
G3 originalaugmented − plain, rank−0.292[−0.352, −0.252][−0.560, −0.062]
G3 originalaugmented − plain, concat−0.116[−0.157, −0.073][−0.234, −0.035]
θ transformedaugmented − plain, value0.063[0.048, 0.077][0.022, 0.108]
θ transformedaugmented − plain, rank0.030[0.011, 0.042][−0.013, 0.098]†
θ transformedaugmented − plain, concat0.084[0.070, 0.101][0.043, 0.132]
G1 transformedconcat − rank, augmented0.002[−0.039, 0.056]†[−0.066, 0.003]†
G1 transformedconcat − value, augmented0.172[0.130, 0.230][0.099, 0.297]
G1 transformedrank − value, augmented0.171[0.116, 0.239][0.052, 0.319]
G2 transformedconcat − rank, augmented0.006[−0.045, 0.055]†[−0.080, 0.101]†
G2 transformedconcat − value, augmented0.164[0.111, 0.229][0.083, 0.281]
G2 transformedrank − value, augmented0.157[0.086, 0.246][0.029, 0.314]
G3 transformedconcat − rank, augmented0.074[−0.025, 0.154]†[−0.172, 0.306]†
G3 transformedconcat − value, augmented0.074[0.017, 0.120][−0.020, 0.166]
G3 transformedrank − value, augmented0.000[−0.089, 0.098]†[−0.258, 0.261]
θ transformedconcat − rank, augmented0.004[−0.008, 0.021]†[−0.026, 0.041]†
θ transformedconcat − value, augmented0.039[0.029, 0.051][0.020, 0.063]
θ transformedrank − value, augmented0.036[0.016, 0.051][−0.012, 0.079]†

Table 11. Bootstrap 95% intervals of the differences with Deep-ELA. Estimate: the difference of the levels in the main paper. Functions fixed: resampling model seeds, ω\omega, and the test instances of each function. Functions resampled: resampling the 24 functions as well. †: the interval includes zero.

Functions fixed. With ELA, the interval excludes zero for the following differences.

  • RQ1: after the transformation, the baseline exceeded the predictor with all features by 0.219 ([0.073, 0.343]).

  • RQ2: after the transformation, rank-based extraction exceeded the other two extractions for G1 and G2; before the transformation, it was below value-based extraction in every group.

  • RQ3: data augmentation raised the R2R^2 of value-based extraction and concatenation in every group and Θ\Theta for every extraction; on the original test instances, it lowered the R2R^2 of value-based extraction and concatenation in every group.

The interval includes zero for the following differences.

  • RQ2: the advantage of rank-based extraction in the selection task (0.021, [−0.005, 0.046]) and the differences for G3 after the transformation.

  • RQ3: the change of rank-based extraction for G1 and G2 with data augmentation. After data augmentation, the difference between concatenation and rank-based extraction for G1 (0.031, [−0.014, 0.077]) and G2, all differences for G3, and the differences in Θ\Theta except that between concatenation and value-based extraction.

With Deep-ELA, the intervals agree with the following exceptions. The advantage of rank-based extraction in the selection task excludes zero (0.052, [0.018, 0.084]). For G3 after the transformation, rank-based extraction is below the other two extractions. After data augmentation, concatenation exceeds value-based extraction for G3, and rank-based extraction exceeds value-based extraction in Θ\Theta. The drawback of data augmentation on the original test instances includes zero for value-based extraction for G1 and G2.

Functions resampled. All intervals widen. With ELA, the interval for RQ1 includes zero ([−0.100, 0.621]): the 24 functions differ too much to decide whether the baseline would exceed the predictor with all features on other functions. The drop of the predictor with all features still excludes zero (0.619, [0.352, 1.085]), as do the advantage of rank-based extraction for G1 and G2 and the gain from data augmentation for value-based extraction and concatenation, but not this gain in Θ\Theta for rank-based extraction ([−0.006, 0.088]). The main paper therefore states its direct evidence for the 24 BBOB functions under LIO evaluation (§ 6).

Additional Controls

This appendix reports controls for statements in the main paper. They add test sets and one training condition; all other settings are the same as in the main paper. We reran all algorithms on every new instance.

The rescaling alone. The transformation gψ,pg_{\psi,p} rescales the objective values to [0,1][0,1] and then applies ψ\psi (Eq. (8)). To separate the two steps, we created a transformed test set with ψ\psi set to the identity, so that only a positive affine transformation remains (Identity in Table 12). The features and JJ of G1 did not change, so its R2R^2 did not change. For G2, JJ changed by 0.09 (0.25 with ψ∼Dspline\psi\sim\mathcal{D}_{\mathrm{spline}}), and the R2R^2 of value-based extraction fell only from 0.77 to 0.76. For G3, JJ changed by 0.65 (0.80 with ψ∼Dspline\psi\sim\mathcal{D}_{\mathrm{spline}}), and the R2R^2 of value-based extraction fell from 0.78 to −0.72-0.72. Dual Annealing accepts solutions based on differences in objective value, so the rescaling changes its search, whereas min-max normalization and ranks remove the scale from the features. On this test set, the input of every feature extraction is the same as on the original test instances, so no model can follow the change in JJ. With data augmentation, the R2R^2 for G3 therefore remained negative (−0.43-0.43 for value-based extraction, −0.01-0.01 for rank-based extraction, and −0.51-0.51 for concatenation), whereas it was 0.18–0.34 with ψ∼Dspline\psi\sim\mathcal{D}_{\mathrm{spline}}. The gain from data augmentation for G3 in Sec. 6.4 thus depends on ψ\psi accompanying the rescaling in both the training and the test instances: the change in the input caused by ψ\psi indicates that JJ has changed. The order of the feature extractions also differs: with the rescaling alone, rank-based extraction was the highest after data augmentation. For rank-based extraction, an instance and its transformed copy have the same input but, for G3, a different JJ, so a model trained with data augmentation cannot fit both; its R2R^2 on the original test instances fell from 0.63 to 0.33 (Table 7).

OriginalIdentityMainDraw 1Draw 2Draw 3Draw 4
ΔJ\Delta JG1–0.0000.0000.0000.0000.0000.000
G2–0.0850.2490.2180.2240.2210.216
G3–0.6540.8020.7840.7690.7720.785
JJ of BOBYQAG30.5130.7190.6870.6810.6790.6830.677
R2R^2G1value, plain0.8520.8520.233−0.0380.1290.0550.041
value, aug.0.7460.7460.6100.5450.5980.5940.547
rank, plain0.6610.6610.6610.6610.6610.6610.661
rank, aug.0.6550.6550.6550.6550.6550.6550.655
concat, plain0.8490.8490.255−0.0490.1560.0450.062
concat, aug.0.7640.7640.6910.6600.6870.6980.663
invariant, plain0.4520.4520.4520.4520.4520.4520.452
G2value, plain0.7700.7550.1960.0890.0680.1110.105
value, aug.0.6840.6730.5450.4850.5270.5380.488
rank, plain0.6210.6030.6070.6290.6220.6190.623
rank, aug.0.6320.6200.5990.6260.6330.6230.629
concat, plain0.7590.7580.1840.0930.0560.1090.090
concat, aug.0.7030.6930.6320.6020.6270.6270.599
G3value, plain0.784−0.723−0.798−0.769−0.874−0.735−0.736
value, aug.0.710−0.4320.2730.2180.3740.3360.261
rank, plain0.635−0.868−0.949−0.943−0.924−0.954−0.902
rank, aug.0.328−0.0140.1820.1910.1890.1670.184
concat, plain0.782−0.737−0.804−0.759−0.878−0.699−0.766
concat, aug.0.718−0.5120.3350.2800.3930.3370.317
Θ\Thetavalue, plain0.7040.7040.5980.5740.5750.5890.564
value, aug.0.6810.6810.6500.6400.6470.6520.640
rank, plain0.6460.6450.6200.6180.6210.6210.620
rank, aug.0.6500.6500.6470.6470.6480.6490.648
concat, plain0.7040.7040.6000.5770.5860.6000.570
concat, aug.0.6830.6830.6540.6520.6560.6620.656

Table 12. Results on further transformed test sets. Identity: ψ\psi is the identity, so only the rescaling in Eq. (8) remains. Main: the draw of ψ∼Dspline\psi\sim D_{\mathrm{spline}} in the main paper. Draws 1–4: four more draws. ΔJ\Delta_J is the change in JJ (Eq. (13)); R2R^2 and Θ\Theta are medians over 11 model seeds, without (plain) and with (aug.) data augmentation.

Further draws of ψ\psi. The main paper uses one draw of ψp∼Dspline\psi_p \sim\mathcal{D}_{\mathrm{spline}} for each test instance. We repeated the Rubber Ruler Test with four more draws (Draws 1–4 in Table 12). The conclusions did not change. For G1, the R2R^2 of the predictor with all features was between −0.04-0.04 and 0.13, below the 0.23 in the main paper and below the 0.45 of the baseline. The R2R^2 of rank-based extraction for G1 and G2 was at least 0.61, and data augmentation raised the R2R^2 of value-based extraction and concatenation in every group and every draw.

Training-set size. Data augmentation doubles the training set. To separate this effect from that of the transformation, we trained models on the 2,400 training instances and 2,400 new untransformed instances (100 more instances of each function), with the same number of parameter updates as with data augmentation (plain-4800 in Table 13). The SBS is the same in all training conditions. On the transformed test instances, plain-4800 stayed near the level without data augmentation for value-based extraction and concatenation; with ELA, for example, the R2R^2 of value-based extraction for G1 was 0.25 without data augmentation, 0.23 with plain-4800, and 0.58 with data augmentation. This holds for each of the four distributions (Table 14). The larger training set therefore does not explain the gain from data augmentation. On the original test instances, plain-4800 gave the highest R2R^2 and Θ\Theta in every cell. With the same number of additional algorithm runs, new instances thus raise prediction performance on the original instances, and transformed copies raise it on the transformed instances. For rank-based extraction for G1 and G2, plain-4800 was also the highest on the transformed instances, because the transformed copies add little to rank-based features. With ELA, its R2R^2 there (0.74 for G1 and 0.71 for G2) was also above that of every feature extraction with data augmentation (at most 0.69 and 0.62); we did not test differences across both feature extractions and training conditions. In the selection task, in contrast, data augmentation gave the highest Θ\Theta on the transformed instances (0.65, versus at most 0.63 with plain-4800). All differences between data augmentation and plain-4800 were significant (Mann–Whitney UU test with Holm correction, p≤0.001p \le0.001).

TaskExtractionOriginal test instancesTransformed test instances
PlainPlain-4800Aug.PlainPlain-4800Aug.
ELAG1 (R2R^2)value0.8520.8950.7460.2450.2290.582
rank0.6610.7380.6550.6610.7380.655
concat0.8490.8850.7640.2620.2450.686
G2 (R2R^2)value0.7700.8290.6840.2520.2660.525
rank0.6210.7350.6320.6130.7130.616
concat0.7590.8300.7030.2800.2690.613
G3 (R2R^2)value0.7840.8390.710−0.814−0.7750.157
rank0.6350.7290.328−1.055−0.9870.115
concat0.7820.8410.718−0.832−0.7990.133
Mixed (Θ\Theta)value0.7040.7200.6810.5830.5890.642
rank0.6460.6660.6500.6190.6330.646
concat0.7040.7190.6830.5980.5940.652
Deep-ELAG1 (R2R^2)value0.8450.8750.8170.0910.0620.441
rank0.6150.6670.6120.6150.6670.612
concat0.8340.8790.7920.1870.1780.613
G2 (R2R^2)value0.7940.8250.7620.0360.0220.421
rank0.5840.6640.5920.5680.6420.578
concat0.7980.8280.7370.1570.1840.585
G3 (R2R^2)value0.8250.8430.727−0.800−0.9230.123
rank0.6200.6860.328−0.992−0.9660.123
concat0.8200.8460.703−0.743−0.8110.197
Mixed (Θ\Theta)value0.7070.7150.7030.5430.5440.606
rank0.6430.6570.6450.6110.6200.642
concat0.7080.7150.6950.5610.5640.645

Table 13. Data augmentation against a training set of the same size without transformations (medians over 11 model seeds). Plain: 2,400 training instances. Plain-4800: these and 2,400 new untransformed instances. Aug.: these and their 2,400 transformed copies. Transformed: mean over the four distributions that data augmentation does not use. Bold marks the best training condition in each cell.

Results of RQ3 on each distribution. The main paper reports the mean over the four distributions that data augmentation does not use. Data augmentation raised the R2R^2 of value-based extraction and concatenation for every group, and Θ\Theta for every feature extraction, on each of the four distributions, with ELA (Table 14) and with Deep-ELA.

Drawback of data augmentation in the selection task. On the original test instances, data augmentation lowered the Θ\Theta of value-based extraction from 0.704 to 0.681 and that of concatenation from 0.704 to 0.683 with ELA (both significant), and raised that of rank-based extraction from 0.646 to 0.650 (Table 13). With Deep-ELA, it lowered the Θ\Theta of concatenation from 0.708 to 0.695 (significant); the other two changed by at most 0.004 (not significant).

Change in the prediction for G1. For G1, the transformation does not change JJ, so a change in the prediction measures the reliance on information that the algorithms ignore. We computed the mean of ∣Jτ(p~,a)−Jτ(p,a)∣\lvert J_{\tau}(\tilde{p},a)-J_{\tau}(p,a)\rvert over the test instances, on the four distributions that data augmentation does not use. With ELA, data augmentation reduced it from 0.189 to 0.086 for value-based extraction and from 0.186 to 0.053 for concatenation; with Deep-ELA, from 0.227 to 0.146 and from 0.205 to 0.083 (all significant). It is zero for rank-based extraction.

Variance of JJ and prediction error. A lower R2R^2 can also come from a smaller variance of JJ. The variance of JJ over the test instances was 0.154 for G1 and 0.067 for G2 before and after the transformation by Dspline\mathcal{D}_{\mathrm{spline}}, and fell from 0.119 to 0.097 for G3. Without data augmentation, the mean squared error of value-based extraction with ELA rose from 0.023 to 0.118 for G1, from 0.015 to 0.054 for G2, and from 0.026 to 0.174 for G3. The drops in R2R^2 therefore come from larger errors.

Identity of the runs for G1. In the regression task, every run of the two G1 algorithms gave the same result on an instance and on its transformed copy: none of the 148,800 runs on the training instances and none of the 14,880 runs on each of the ten transformed test sets differed in the best objective value, the number of evaluations, or the number of restarts. With the algorithm settings of the selection task (Table 5), up to 2.5% of the runs of Adaptive Nelder–Mead and 0.5% of those of BIPOP CMA-ES on a transformed test set differed in the best objective value or the number of restarts, but never in the number of evaluations. We attribute these differences to floating-point rounding, because a transformation can map two close objective values to the same number.

AlgorithmFor selection (budget 1000d1000d)For the SBS (budget 1050d1050d)
BIPOP CMA-ESσ0=4.0\sigma_0 = 4.0, λ0=30\lambda_0 = 30, εx=10−8\varepsilon_x = 10^{-8}σ0=5.0\sigma_0 = 5.0, λ0=30\lambda_0 = 30, εx=10−8\varepsilon_x = 10^{-8}
Adaptive Nelder–Meadoffset 0.25, εx=10−8\varepsilon_x = 10^{-8}offset 0.25, εx=10−8\varepsilon_x = 10^{-8}
SHADEN=5dN = 5d, MF=0.5M_F = 0.5, MCR=0.4M_{CR} = 0.4, εx=10−8\varepsilon_x = 10^{-8}N=5dN = 5d, MF=0.4M_F = 0.4, MCR=0.7M_{CR} = 0.7, εx=10−8\varepsilon_x = 10^{-8}
L-SHADENinit=5dN_{\mathrm{init}} = 5d, MF=0.3M_F = 0.3, MCR=0.4M_{CR} = 0.4, εx=10−8\varepsilon_x = 10^{-8}Ninit=5dN_{\mathrm{init}} = 5d, MF=0.3M_F = 0.3, MCR=0.6M_{CR} = 0.6, εx=10−8\varepsilon_x = 10^{-8}
BOBYQAinitial step 0.4, εx=10−4\varepsilon_x = 10^{-4}initial step 0.4, εx=10−6\varepsilon_x = 10^{-6}
Dual AnnealingT0=40000T_0 = 40000, qv=2.85q_v = 2.85, qa=−5q_a = -5, εx=10−6\varepsilon_x = 10^{-6}T0=500T_0 = 500, qv=1.5q_v = 1.5, qa=−50q_a = -50, εx=10−6\varepsilon_x = 10^{-6}

Table 5. Parameters selected for the selection task. The SBS uses BIPOP CMA-ES tuned separately for it. The initial step of BOBYQA is relative to the width of the search range.

References

  1. [1]Leo Breiman. 2001. Random Forests. Machine Learning 45, 1 (2001), 5–32. doi:10.1023/A:1010933404324DOI
  2. [2]Gjorjina Cenikj, Gašper Petelin, Moritz Seiler, Nikola Cenikj, and Tome Effimov. 2025. Landscape Features in Single-Objective Continuous Optimization: Have We Hit a Wall in Algorithm Selection Generalization? Swarm and Evolutionary Computation 94 (2025), 101894. doi:10.1016/j.swevo.2025.101894DOI
  3. [3]Tianqi Chen and Carlos Guestrin. 2016. XGBoost: A Scalable Tree Boosting System. In Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD). ACM, New York, NY, USA, 785–794. doi:10.1145/2939672.2939785DOI
  4. [4]Fuchang Gao and Lixing Han. 2012. Implementing the Nelder-Mead Simplex Algorithm with Adaptive Parameters. Computational Optimization and Applications 51, 1 (2012), 259–277. doi:10.1007/s10589-010-9329-3
  5. [5]Robert Geirhos, Jörn-Henrik Jacobsen, Claudio Michaelis, Richard Zemel, Wieland Brendel, Matthias Bethge, and Felix A. Wichmann. 2020. Shortcut Learning in Deep Neural Networks. Nature Machine Intelligence 2, 11 (2020), 665–673. doi:10.1038/s42256-020-00257-z
  6. [6]Nikolaus Hansen. 2009. Benchmarking a BI-Population CMA-ES on the BBOB-2009 Function Testbed. In Proceedings of the Genetic and Evolutionary Computation Conference Companion (GECCO Companion). ACM, New York, NY, USA, 2389–2396. doi:10.1145/1570256.1570333
  7. [7]Nikolaus Hansen. 2016. The CMA Evolution Strategy: A Tutorial. arXiv:1604.00772 [cs.LG] doi:10.48550/arXiv.1604.00772
  8. [8]Nikolaus Hansen, Anne Auger, Raymond Ros, Olaf Mersmann, Tea Tušar, and Dimo Brockhoff. 2021. COCO: A Platform for Comparing Continuous Optimizers in a Black-Box Setting. Optimization Methods and Software 36, 1 (2021), 114–144. doi:10.1080/10556788.2020.1808977DOI
  9. [9]Nikolaus Hansen, Steffen Finck, Raymond Ros, and Anne Auger. 2009. Real-Parameter Black-Box Optimization Benchmarking 2009: Noiseless Function Definitions. Technical Report RR-6829. INRIA. https://inria.hal.science/inria-00362633
  10. [10]Nikolaus Hansen and Andreas Ostermeier. 2001. Completely Derandomized Self-Adaptation in Evolution Strategies. Evolutionary Computation 9, 2 (2001), 159–195. doi:10.1162/106365601750190398
  11. [11]Nikolaus Hansen, Raymond Ros, Nikolai Mauny, Marc Schoenauer, and Anne Auger. 2011. Impacts of Invariance in Search: When CMA-ES and PSO Face Ill-Conditioned and Non-Separable Problems. Applied Soft Computing 11, 8 (2011), 5755–5769. doi:10.1016/j.asoc.2011.03.001
  12. [12]Sture Holm. 1979. A Simple Sequentially Rejective Multiple Test Procedure. Scandinavian Journal of Statistics 6, 2 (1979), 65–70. https://www.jstor.org/stable/4615733
  13. [13]David Holzmüller, Léo Grinsztajn, and Ingo Steinwart. 2024. Better by Default: Strong Pre-Tuned MLPs and Boosted Trees on Tabular Data. In Advances in Neural Information Processing Systems (NeurIPS), Vol. 37. Curran Associates, Inc., Red Hook, NY, USA, 26577–26658. doi:10.52202/979-8-4007-0837-8arxiv.org/abs/2407.04491
  14. [14]Pascal Kerschke, Holger H. Hoos, Frank Neumann, and Heike Trautmann. 2019. Automated Algorithm Selection: Survey and Perspectives. Evolutionary Computation 27, 1 (2019), 3–45. doi:10.1162/evco_a_00242DOI
  15. [15]Zeyuan Ma, Rongshu Guo, Jiacheng Chen, Zhenrui Liu, Guojun Peng, Yue-Jiao Gong, Yining Ma, and Zhiguang Cao. 2023. MetaBox: A Benchmark Platform for Meta-Black-Box Optimization with Reinforcement Learning. In Advances in Neural Information Processing Systems (NeurIPS), Vol. 36. Curran Associates, Inc., Red Hook, NY, USA, 10775–10795. doi:10.52202/078528-0474
  16. [16]Henry B. Mann and Donald R. Whitney. 1947. On a Test of Whether One of Two Random Variables Is Stochastically Larger than the Other. The Annals of Mathematical Statistics 18, 1 (1947), 50–60. doi:10.1214/aoms/1177730491
  17. [17]Michael D. McKay, Richard J. Beckman, and William J. Conover. 1979. A Comparison of Three Methods for Selecting Values of Input Variables in the Analysis of Output from a Computer Code. Technometrics 21, 2 (1979), 239–245. doi:10.1080/00401706.1979.10489755DOI
  18. [18]Olaf Mersmann, Bernd Bischl, Heike Trautmann, Mike Preuss, Claus Weihs, and Günter Rudolph. 2011. Exploratory Landscape Analysis. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO). ACM, New York, NY, USA, 829–836. doi:10.1145/2001576.2001690DOI
  19. [19]Fabian Pedregosa, Gaël Varoquaux, Alexandre Gramfort, Vincent Michel, Bertrand Thirion, Olivier Grisel, Mathieu Blondel, Peter Prettenhofer, Ron Weiss, Vincent Dubourg, Jake Vanderplas, Alexandre Passos, David Cournapeau, Matthieu Brucher, Matthieu Perrot, and Édouard Duchesnay. 2011. Scikit-learn: Machine Learning in Python. Journal of Machine Learning Research 12 (2011), 2825–2830. https://jmlr.org/papers/v12/pedregosa11a.html
  20. [20]Gašper Petelin and Jorgijna Cenikj. 2025. The Pitfalls of Benchmarking in Algorithm Selection: What We Are Getting Wrong. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO). ACM, New York, NY, USA, 1181–1189. doi:10.1145/3712256.3726336DOI
  21. [21]Michael J. D. Powell. 2009. The BOBYQA Algorithm for Bound Constrained Optimization without Derivatives. Technical Report DAMTP 2009/NA06. University of Cambridge. https://www.damtp.cam.ac.uk/user/na/NA_papers/NA2009_06.pdf
  22. [22]Raphael Patrick Prager and Heike Trautmann. 2023. Nullifying the Inherent Bias of Non-Invariant Exploratory Landscape Analysis Features. In Applications of Evolutionary Computation (EvoApplications) (LNCS, Vol. 13989). Springer, Cham, 411–425. doi:10.1007/978-3-031-30229-9_27
  23. [23]Raphael Patrick Prager and Heike Trautmann. 2024. Placco: Feature-Based Landscape Analysis of Continuous and Constrained Optimization Problems in Python. Evolutionary Computation 32, 3 (2024), 211–216. doi:10.1162/evco_a_00341DOI
  24. [24]Moritz Vinzent Seiler, Pascal Kerschke, and Heike Trautmann. 2025. Deep-ELA: Deep Exploratory Landscape Analysis with Self-Supervised Pretrained Transformers for Single- and Multiobjective Continuous Optimization Problems. Evolutionary Computation 33, 4 (2025), 513–540. doi:10.1162/evco_a_00367
  25. [25]Urban Škvorc, Tome Eftimov, and Peter Korošec. 2020. Understanding the Problem Space in Single-Objective Numerical Optimization Using Exploratory Landscape Analysis. Applied Soft Computing 90 (2020), 106138. doi:10.1016/j.asoc.2020.106138
  26. [26]Ryoji Tanabe and Alex S. Fukunaga. 2013. Success-History Based Parameter Adaptation for Differential Evolution. In Proceedings of the IEEE Congress on Evolutionary Computation (CEC). IEEE, Piscataway, NJ, USA, 71–78. doi:10.1109/CEC.2013.6557555DOI
  27. [27]Ryoji Tanabe and Alex S. Fukunaga. 2014. Improving the Search Performance of SHADE Using Linear Population Size Reduction. In Proceedings of the IEEE Congress on Evolutionary Computation (CEC). IEEE, Piscataway, NJ, USA, 1658–1665. doi:10.1109/CEC.2014.6900380DOI
  28. [28]András Vargha and Harold D. Delaney. 2000. A Critique and Improvement of the CL Common Language Effect Size Statistics of McGraw and Wong. Journal of Educational and Behavioral Statistics 25, 2 (2000), 101–132. doi:10.3102/10769986025002101DOI
  29. [29]Diederick Vermetten, Furong Ye, Thomas Bäck, and Carola Doerr. 2025. MA-BBOB: A Problem Generator for Black-Box Optimization Using Affine Combinations and Shifts. ACM Transactions on Evolutionary Learning and Optimization 5, 1 (2025), 19 pages. doi:10.1145/3673908DOI
  30. [30]Frank Wilcoxon. 1945. Individual Comparisons by Ranking Methods. Biometrics Bulletin 1, 6 (1945), 80–83. doi:10.2307/3001968DOI
  31. [31]Y. Xiang, D. Y. Sun, W. Fan, and X. G. Gong. 1997. Generalized Simulated Annealing Algorithm and Its Application to the Thomson Model. Physics Letters A 233, 3 (1997), 216–220. doi:10.1016/S0375-9601(97)00474-X
  32. [32]Chengrun Yang, Xuezhi Wang, Yifeng Lu, Hanxiao Liu, Quoc V. Le, Denny Zhou, and Xinyun Chen. 2024. Large Language Models as Optimizers. In International Conference on Learning Representations (ICLR). OpenReview.net. https://proceedings.iclr.cc/paper_files/paper/2024/hash/3339f19c5fcee3ad74502947a32be9e6-Abstract-Conference.htmlarxiv.org/abs/2309.03409

Paper details

vlnc:W_zs6nuh64
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Claude Code, Claude (Anthropic)

View statement
Looking for related papers…
Contents