Depth over Fidelity in Fixed-Budget Noisy Evolution Strategies

Note that Assumption 1 does not require global convexity. It only requires that the random update and its conditional mean stay inside a region where $f$ has curvature. A typical special case is: $f$ is $\alpha$-strongly convex on a ball $B(m,r)$ and the update is localized by design, for example, via step-size control or explicit clipping, so that $\|X-m\|\leq r$ and $\|\bar{X}-m\|\leq r$.

Concretely, we assume

and the bootstrap draws satisfy $\hat{\varepsilon}_{i}\stackrel{{\scriptstyle\text{i.i.d.}}}{{\sim}}\widehat{D}_{t}$. If there is strong cross-candidate correlation or if the standardized shape depends sharply on $x$, then expected rank weights depend on the joint law of $(\varepsilon_{1},\ldots,\varepsilon_{\lambda})$ and a univariate residual pool is insufficient.

The second term in (42) scales with the mass of pairwise gaps near $0$. It is small when candidate scores are well separated (large $|f(x_{i})-f(x_{j})|$ relative to noise), or when the gap distribution has a moderate density bound near $0$. The statement is already for a general deterministic $w$: the weight map enters only through $\|w\|_{\infty}$ in the smooth mismatch term and through the adjacent-drop scale $\Delta_{w}$ in the near-tie term.

To make $\mathrm{StdErr}_{t}$ explicit, suppose the stored residual uses estimated center/scale, $\widehat{z}_{n}=\operatorname{clip}((y_{n}-\widehat{f}(x_{n}))/\widehat{s}(x_{n}),[-M,M])$, while the ideal residual is (50). Since $\operatorname{clip}(\cdot,[-M,M])$ is 1-Lipschitz and $W_{1}(P,Q)\leq\mathbb{E}|X-Y|$ for any coupling $(X,Y)$ of $P,Q$, one convenient bound is

where $y_{n}=f(x_{n})+s(x_{n})\varepsilon_{n}$, $\alpha_{n}=\frac{f(x_{n})-\widehat{f}(x_{n})}{\widehat{s}(x_{n})}$ and $\beta_{n}=\frac{s(x_{n})-\widehat{s}(x_{n})}{\widehat{s}(x_{n})}$. Under winsorization $|\varepsilon_{n}|\leq M$, the second term is bounded by $M\,|s-\widehat{s}|/\widehat{s}$.

We keep the assumptions explicit and map each to a simple diagnostic, so the theory is falsifiable. See table 3 for details.

Theorem 1 formalizes the key mechanism behind “depth over fidelity”: under local curvature, conditional update dispersion incurs an unavoidable Jensen gap, so reducing dispersion can improve expected progress per oracle call. This experiment tests the full mechanism chain in the simplest setting where the curvature penalty is analytically transparent.

Setup. We use a strongly convex quadratic $f(x)=\frac{1}{2}\|x\|^{2}$ (strong convexity parameter $\alpha=1$) and sample $\lambda=16$ candidates in $d=40$ dimensions (truncation $\mu=8$). For each of 200 independently sampled candidate sets, we draw two independent noisy evaluation vectors (with additive Gaussian noise of standard deviation $\sigma_{\mathrm{noise}}=1.0$), producing two induced rankings. We measure: (i) a two-draw rank-disagreement score $M_{\mathrm{RD}}$ (same structure as the probe statistic $P$ in Eq. (56)); (ii) update dispersion $\|\Delta m^{(a)}-\Delta m^{(b)}\|^{2}$ under the two rankings; and (iii) the curvature loss (Jensen gap) $\mathbb{E}[f(m+\Delta m)]-f(m+\mathbb{E}[\Delta m])$, estimated via Monte Carlo (256 draws per candidate set).

Results and interpretation. Figure 7 verifies both links in the chain. First, dispersion increases with misranking (Pearson $r=0.45$; Fig. 7a), showing that ranking noise is directly converted into update randomness by truncation selection. Second, the curvature loss matches the quadratic identity $\mathbb{E}[f(m+\Delta m)]-f(m+\mathbb{E}[\Delta m])=\tfrac{1}{2}\mathrm{Var}(\Delta m)$ exactly (slope 1; Fig. 7b). Together, these results give a controlled, falsifiable confirmation of the theoretical story: misranking is not merely “label noise”, it induces update dispersion, and under curvature that dispersion translates into real expected objective loss.

A natural concern is that RB-PEM’s gains might be fragile (driven by a narrow hyperparameter choice), or they might simply reflect spending extra evaluations near the truncation boundary (i.e., implicit resampling). This ablation isolates these possibilities.

Setup. We evaluate RB-PEM variants on the COCO bbob-noisy high-misranking subset at $d=40$ and budget $B=100d$ (225 problems: 15 functions $\times$ 15 instances). For each problem instance, we report $\Delta\log_{10}\text{regret}=\log_{10}(f(\hat{x}_{B})-f^{\star})_{\text{CMA}}-\log_{10}(f(\hat{x}_{B})-f^{\star})_{\text{variant}}$, so $\Delta>0$ means the variant improves over CMA-ES. Figure 8 sweeps: (a) boundary reevaluation cap $K_{\max}\in\{0,1,3\}$; (b) bootstrap sample count $B_{\mathrm{boot}}\in\{16,32,64\}$; (c) noise-model variants used inside the bootstrap weight estimator.

Results and interpretation. All variants exhibit positive median improvements and clear majority win rates (62–72%; Fig. 8). Two implications are especially important. First, the improvement persists at $K_{\max}=0$ (66% win rate), where RB-PEM operates with essentially the same per-generation evaluation cost as vanilla CMA-ES. This strongly disfavors the hypothesis that RB-PEM wins primarily by spending extra evaluations at the boundary. Instead, it supports the intended interpretation: the main gain comes from how uncertainty is used (selection-stage smoothing of the rank weights), not from brute-force denoising. Second, performance is stable across bootstrap counts and across several plausible noise models, suggesting that the estimator is not brittle and that modest Monte Carlo effort (e.g., $B_{\mathrm{boot}}\approx 32$) is sufficient.

The CMA-ES baseline uses its standard logarithmic recombination weights throughout. Our default RB-PEM estimator uses a smooth power-lift weight map inside the bootstrap, and Probe-and-Switch inherits this default when it switches to RB-PEM. This ablation asks whether the gains depend on that bootstrap-internal choice. We rerun matched variants that replace only the bootstrap-internal map with the standard CMA-ES log weights from (31), holding seeds, candidate populations, budgets, and all other hyperparameters fixed.

Direct head-to-head comparisons also show near parity between the two bootstrap-internal weight maps: RB-PEM (log-weight) wins against RB-PEM (power-lift) on roughly $44\%$ of matched high-misranking problems, with median regret differences around $10^{-3}$. Median wall-clock overheads at $d=40$, $B=100d$ are similar as well: $1.70\times$, $1.64\times$, $1.66\times$, and $1.62\times$ CMA-ES for RB-PEM (power-lift), RB-PEM (log-weight), Probe-and-Switch (power-lift), and Probe-and-Switch (log-weight), respectively.

RB-PEM relies on reusing a pooled residual distribution; Appendix C shows that residual-pool mismatch can be decomposed into multiple falsifiable components. This experiment asks whether our diagnostics meaningfully distinguish successful runs from failures and whether they identify the relevant mismatch mode.

Setup. On the same 225 high-misranking COCO problems ($d=40$, $B=100d$), we compare RB-PEM against a representative evaluation-stage baseline (UH-CMA-ES with a conservative reevaluation budget). We label each run as good if RB-PEM achieves lower final regret and bad otherwise (193 good, 32 bad). We then compare four per-run diagnostic summaries (defined in Appendix C): drift $W_{1}$, shape $W_{1}$, scale $R^{2}$, and a centering-stability metric (“center rel”).

Results: diagnostics isolate specific failure modes. Figure 9a shows that shape mismatch and centering instability are the dominant distinguishers between good and bad runs: one-sided Mann–Whitney tests detect significant separation for shape $W_{1}$ ($p=0.003$) and center rel ($p=0.001$), while drift and scale do not separate at conventional levels. This selective pattern is desirable: rather than firing a generic alarm, the diagnostics point to a concrete assumption violation (“residuals are well-standardized and shape-stable”) as the likely culprit in failures.

Results: failures often manifest as depth collapse. Figure 9b shows per-generation traces of shape $W_{1}$ for a representative good and bad case. The bad case exhausts its fixed budget by generation 129, while the good case continues to generation 211 ($\Delta T=82$ generations; 39% of depth lost). This illustrates a concrete failure pathway that is consistent with the paper’s depth accounting: instability in standardization can increase boundary reevaluations (raising $K_{t}$), which directly consumes budget and eliminates the depth advantage RB-PEM is designed to preserve.

Probe-and-switch (Appendix D) uses a rank-disagreement statistic $P=\frac{1}{\lambda^{2}}\sum_{i}|r_{i}^{(a)}-r_{i}^{(b)}|$ (Eq. (56)). This statistic is essentially a normalized Spearman footrule distance between two permutations. To connect it to more familiar notions of misranking, we relate it to: (i) Kendall discordance (fraction of discordant pairs) and (ii) elite disagreement (how often the top-$\mu$ set changes), which directly governs truncation selection.

Theoretical relations. Let $q_{\mathrm{pair}}\in[0,1]$ be the fraction of discordant pairs between the two induced rankings (Kendall), and let $M_{\mathrm{top}\mu}\in[0,1]$ be the fraction of indices whose membership in the top-$\mu$ set differs. Standard inequalities between footrule and Kendall distances imply constant-factor bounds of the form

where $M_{\mathrm{RD}}$ is the two-draw rank-disagreement score (numerically the same object as $P$ up to notation).

Empirical validation. We sample 750 candidate sets from COCO bbob-noisy at $d=40$ with the default $\lambda=15$ and $\mu=7$. Figure 10 shows $(q_{\mathrm{pair}},M_{\mathrm{top}\mu})$ versus $M_{\mathrm{RD}}$ together with the bounds in Eq. (59). There are zero violations out of 750 points. This supports two practical interpretations: (i) $M_{\mathrm{RD}}$ is a scale-consistent proxy for overall rank instability (Kendall discordance), and (ii) large $M_{\mathrm{RD}}$ implies nontrivial instability of the top-$\mu$ set, which is precisely the part of the ranking that affects CMA-ES updates most strongly.

A tempting simplification would be to trigger switching based on a variance probe (estimate the noise variance at a point and switch when it is large). This experiment constructs a clean counterexample showing that variance at a single location can be arbitrarily misleading for rank-based ES, while rank disagreement remains reliable.

Radial (state-dependent) noise model. We consider heteroscedastic noise with scale increasing with distance to an initial reference point $x_{0}$: $\sigma_{\mathrm{eff}}(x)=\sigma\|x-x_{0}\|_{\mathrm{RMS}}$. Under this model, evaluations at $x_{0}$ are effectively noiseless, but ES candidates sampled away from $x_{0}$ experience substantial noise—exactly where misranking matters.

Probe decoupling. Figure 11a shows the key pathology: the variance probe stays at machine precision across all 54 problem instances (it never triggers), while the rank-disagreement probe $M_{\mathrm{RD}}$ spans a wide range and triggers on 49/54 problems (at $\tau=0.12$). Thus, variance can be decoupled from the misranking regime experienced by the candidate population.

Algorithmic consequence. This decoupling changes decisions. Figure 11b compares probe-and-switch using misranking detection (MR) versus a variance-based variant (Var). Misranking-based switching wins on 39/54 problems ($p=0.0007$, sign test). This provides direct support for our design choice in Appendix D: a probe should measure ranking instability in the current search distribution, not variance at an arbitrary point.

Proposition 5 shows that if the conditional advantage $\Delta(p)$ single-crosses, then a threshold rule in the probe statistic $P$ is Bayes-optimal among rules depending only on $P$. This experiment empirically checks whether $P$ behaves as a calibrated predictor of when RB-PEM wins.

Setup. We compute the probe statistic $P$ (Eq. (56)) and bin problems into quantiles of $P$. Within each bin we estimate the empirical win rate of RB-PEM over CMA-ES, with 95% Wilson score intervals. To test generalization and avoid within-suite leakage, we evaluate on a held-out test split of instances (instances 6–15), using thresholds calibrated on instances 1–5. We report two representative budgets to illustrate budget dependence.

Results and interpretation. Figure 12 shows a clear monotone trend: at low $P$ (stable ranks), RB-PEM wins with probability well below 0.5 (CMA-ES is preferred); at high $P$, RB-PEM wins with probability 0.7–0.8. The calibrated thresholds (vertical dashed lines) fall near the empirical 0.5 crossing, aligning with the decision-theoretic interpretation: the probe is measuring a quantity that is predictive of the algorithm crossover. The threshold shifts with budget in the expected direction: when the remaining budget is larger, the relative cost of RB-PEM’s bounded overhead is smaller, so switching becomes beneficial at lower misranking levels.

The probe costs $2\lambda$ evaluations, so it must be informative at modest budgets. This experiment quantifies the classification quality of the probe as we vary its cost by changing $\lambda$.

Setup. We sweep probe population sizes $\lambda\in\{4,8,16,32\}$. For each setting we compute $P$ and evaluate its ability to classify problems where RB-PEM beats CMA-ES (ground-truth labels from full runs) on 450 COCO problems at $d=40$, $B=200d$. We report ROC curves; the legend lists AUC and accuracy at a representative threshold.

Results and interpretation. Figure 13 shows that even the cheapest probe ($\lambda=4$, cost 8 evaluations) is strongly informative (AUC 0.71, accuracy 0.72), and performance improves up to $\lambda\approx 16$ (AUC 0.76). Increasing probe cost further does not help (AUC drops to 0.73 at $\lambda=32$), indicating diminishing returns and a clear cost-effectiveness plateau. This justifies using a modest probe budget comparable to the default ES population size.

Probe-and-switch introduces a single scalar hyperparameter: the switching threshold $\tau$. A practical method should not require fragile tuning. This experiment evaluates (i) how accuracy depends on $\tau$ and (ii) how much regret is incurred by choosing a suboptimal threshold.

Setup. We sweep $\tau\in[0,0.30]$ and evaluate classification accuracy of the misranking probe (MR) and a variance proxy (Var) at two budgets. We also compute decision regret: the mean $\log_{10}$ performance gap to an oracle that always chooses the better of CMA-ES and RB-PEM for each problem instance. We report both the train split (instances 1–5) and the held-out test split (instances 6–15).

Results and interpretation. Figure 14a shows a broad accuracy plateau: for MR, accuracy varies by only $\approx 2$ percentage points over $\tau\in[0.08,0.18]$. Across all thresholds, MR outperforms Var by roughly 5–6 percentage points, reinforcing the necessity of rank-based probing (cf. F5). Figure 14b shows that decision regret is highly asymmetric: very small $\tau$ causes over-switching (unnecessary RB-PEM overhead on low-misranking problems), while very large $\tau$ causes under-switching (missing beneficial RB-PEM deployments). Importantly, the regret curve is also flat across the plateau, so near-optimal decisions do not require precise threshold tuning; $\tau=0.12$ lies safely in the robust region.

The main paper argues that under fixed budget, evaluation-stage denoising is structurally disadvantaged because it reduces depth. This section provides two complementary robustness checks: (a) whether RB-PEM’s advantage persists across budgets and dimensions, and (b) whether UH-CMA-ES can be “rescued” by tuning its maxevals parameter.

a: Budget and dimension robustness. Figure 15a reports win rates of RB-PEM against three baselines across budgets $B\in\{50d,100d,200d\}$ and dimensions $d\in\{20,40\}$ (225 high-misranking COCO problems per setting). RB-PEM wins decisively against UH-CMA-ES (roughly 79–94%) and against Resample($k{=}10$) (roughly 78–83%) in every regime, and maintains majority wins even against vanilla CMA-ES. The advantage is larger at $d=40$ than at $d=20$, consistent with misranking becoming more damaging in higher dimensions and with the paper’s empirical observation that depth becomes increasingly predictive of performance as misranking increases.

b: UH-CMA-ES maxevals sweep. Figure 15b sweeps maxevals$\in\{1,10,30\}$. Across both budgets, UH-CMA-ES remains far below the 50% parity line versus CMA-ES and versus probe-and-switch. Moreover, increasing maxevals monotonically reduces UH-CMA-ES win rate: allocating more reevaluations per generation worsens fixed-budget performance. This supports the interpretation that UH-CMA-ES’s underperformance is not a tuning artifact but a depth-loss effect.

The COCO suite is synthetic and largely separable from end-to-end ML pipelines. This experiment tests whether the probe-and-switch principle generalizes to a small nonconvex real-data task where noise is induced by stochastic mini-batching.

Setup. We train a single-hidden-layer MLP (4 hidden units) on the digits0 binary classification task (digit 0 vs. non-0), with $n=256$ samples and $d=265$ parameters. We control ranking noise via mini-batch size $B_{\mathrm{batch}}\in\{4,16,256\}$ (smaller batches $\Rightarrow$ noisier objective values $\Rightarrow$ more misranking). We compare CMA-ES, probe-and-switch, and a warmstart variant that reuses the probe evaluations as part of the first generation, thereby removing the probe’s opportunity cost when the probe indicates “no switch.” All methods use the same total budget $B=40d=10{,}600$ and 50 random seeds.

Results and interpretation. Figure 16 shows three regimes. Moderate noise ($B_{\mathrm{batch}}=16$, $M_{\mathrm{RD}}\in[0.13,0.34]$): probe-and-switch improves over CMA-ES (66% win rate) and warmstart is stronger still (76% win rate), consistent with the paper’s main claim that selection-stage uncertainty integration is most beneficial in high-misranking regimes. Extreme noise ($B_{\mathrm{batch}}=4$): both variants are near parity (54% win rate), suggesting a saturation regime where all methods are heavily noise-limited. Deterministic ($B_{\mathrm{batch}}=256$, $M_{\mathrm{RD}}=0$): warmstart matches CMA-ES almost exactly (48/50 ties, i.e., 96%), demonstrating that the probe can correctly detect “no misranking” and that warmstarting can remove probe cost when switching is unnecessary. Overall, this nonconvex experiment supports the external validity of probe-and-switch and highlights warmstarting as a simple practical refinement in low-noise settings.

The main text visualizes convergence on a small set of representative functions. Table 5 provides the complete per-function summary on the full high-misranking function class used throughout the paper, to verify that the reported gains are not an artifact of selective function choice.

Setup. We report median final $\log_{10}$ regret at budget $B=100d$ for $d=40$ across 15 instances per function. We compare CMA-ES, UH-CMA-ES, RB-PEM, and probe-and-switch (bold indicates the best median per function).

Results and interpretation. Two patterns stand out. First, RB-PEM and probe-and-switch dominate UH-CMA-ES across the entire class (no exceptions), reinforcing the depth-fidelity argument: evaluation-stage reevaluation is consistently uncompetitive under strict budgets. Second, selection-stage methods usually outperform vanilla CMA-ES, with the largest gains on the functions where the noisy ranking is most unstable (e.g., f110, f111, f116). On the few functions where CMA-ES is marginally better, the gaps are small, consistent with a low-misranking regime where smoothing and any additional overhead bring limited benefit. This table therefore complements the main-text figures by showing that the “selection-stage wins” pattern is broad and not cherry-picked.

Table 1 and Fig. 4 report all-function evidence; here we unpack where those gains arise. The probe statistic separates bbob-noisy into a selected high-misranking subset and a more stable complement. Table 6 quantifies this split at $B=100d$. Always-on RB-PEM is strongest on the selected high-misranking functions but can be harmful on the complement, where smoothing and reevaluation overhead are often unnecessary. Probe-and-Switch preserves most of the high-misranking gain while reverting toward CMA-ES on the complement.

Table 7 gives an orthogonal view by COCO noise family. The moderate-Gaussian group is mostly stable-ranking, so always-on RB-PEM often pays overhead without enough ranking uncertainty to offset it. By contrast, the severe Gaussian, Cauchy, and multimodal groups contain regimes where selection-stage smoothing is more useful. The Cauchy row should be read as an empirical stress test: raw Cauchy noise violates the finite-variance assumption, while the implementation clips standardized residuals to $[-M,M]$ and therefore bootstraps from a winsorized working distribution.

Practical takeaway. Across the appendix, the empirical message is consistent with the theoretical one: when ranking noise is substantial, it is more sample-efficient (under a strict budget) to integrate uncertainty into selection weights (RB-PEM) than to spend evaluations trying to eliminate it, and a low-cost rank-disagreement probe provides a robust mechanism for avoiding overhead in low-misranking regimes.