Hidden Sign-Pattern Bias in Scalable Covariance Search

Many optimizers carry a built-in preference for certain parts of the search space, and they show it even when the objective carries no information. Give such an optimizer a function that returns pure noise and its final answers do not spread evenly over the domain. They pile up near the center, against the walls, or in particular corners. This is called structural bias. So far it has been measured almost entirely in two dimensions, and almost entirely for optimizers that keep a full covariance matrix, the $d \times d$ matrix describing the shape of the sampling cloud. In real high-dimensional search nobody keeps that matrix, because it costs $O(d^2)$ memory and up to $O(d^3)$ compute. Practitioners switch instead to cheap stand-ins: a diagonal, a low-rank-plus-diagonal factorization, or a fast structured transform such as the Walsh-Hadamard matrix.

We propose to measure what these cheap stand-ins do to structural bias in hundreds to thousands of dimensions. Our central claim is that high-dimensional bias has a component that current per-coordinate tests cannot see. The final solutions can look uniform coordinate by coordinate while their joint sign pattern, meaning which side of the domain center each coordinate falls on, is strongly structured. One example is too few sign changes between neighbouring coordinates, the "low-sequency" failure that Bounce found in combinatorial Bayesian optimizers. We contribute two things. The first is a detection method that uses the symmetries of the hypercube to split any bias into two parts: a radial part (center or boundary) and an orientation part (sequency or specific corners). The second is the first map of both parts across full, diagonal, low-rank, and Walsh-Hadamard-structured covariance search.

Core Claim and Motivation

Two findings motivate the work. A Deep Dive Into Effects of Structural Bias on CMA-ES Performance Along Affine Trajectories analyzed 435,456 configurations of modular CMA-ES. CMA-ES, the covariance matrix adaptation evolution strategy, samples candidates from a Gaussian whose covariance it learns as it goes. The study found that the covariance adaptation module drives center bias, which appeared in 82% of configurations. The authors trace this to a mismatch between ellipsoidal sampling and a box-shaped domain. They also found that "mixed" bias, a pull toward the center and the bounds at once, produced the worst performance. The study is restricted to $d=2$, and it covers only the full $O(d^2)$ covariance. Separately, Bounce showed that BODi and COMBO fail badly when the optimum is not a low-sign-alternation pattern such as all zeros or all ones. Bounce did not ask where such a bias comes from in the surrogate's structure.

The two findings connect through geometry that only appears in high dimensions. In high dimensions a Gaussian's mass sits in a thin shell, and almost all of a hypercube's volume lies near its corners. A 2D center-versus-boundary picture is therefore the wrong summary. What matters is which of the $2^d$ orthants (the corner regions picked out by a choice of sign for every coordinate) the search ends up in. Each structured covariance plausibly favours different orthants:

  • A low-rank factor ties many coordinates to a few shared directions.
  • A diagonal treats every coordinate independently.
  • A Walsh-Hadamard parameterization, like the one in Walsh-Hadamard Variational Inference, is built from basis vectors ordered by sequency. It also depends on how the coordinates are ordered, which may couple neighbouring coordinates in a sequency-specific way.

WHVI itself failed on convolutional filters, where it produced 99.2% sparsity in AlexNet. That failure is at least suggestive that such transforms impose strong unintended structure. We treat it as suggestive only, since WHVI was built for variational inference and not for search.

To make the orientation part measurable, write $s_i = \mathrm{sign}(x_i - c_i)$ for the sign of coordinate $i$ of a final solution $x$ relative to the domain center $c$. Define its sequency as the number of neighbouring sign changes:

$$\mathrm{seq}(x) = \sum_{i=1}^{d-1} \mathbf{1}[s_i \neq s_{i+1}].$$

For an unbiased optimizer on a noise landscape the signs are independent fair coins, so $\mathrm{seq}(x) \sim \mathrm{Binomial}(d-1, 1/2)$. This gives an exact null distribution in any dimension. A marginal uniformity test, such as those in the BIAS toolbox and Deep BIAS, can pass even when the sequency distribution is shifted far from this null. The reason is that per-coordinate marginals carry no information about how coordinates co-vary.

Research Program

The method rests on a symmetry decomposition. The hypercube's symmetry group consists of coordinate permutations combined with reflections of individual coordinates, the maps $x_i \mapsto 2c_i - x_i$. Radial biases are unchanged by every element of this group. Center pull and boundary pull are both examples, because distance from the center and closeness to the walls do not care which coordinate is which. Orientation biases change under the group. Low sequency and a preference for particular corners are examples, because they depend on coordinate order or sign.

We therefore run each optimizer twice on the noise landscape:

  • As-is. The optimizer runs unchanged.
  • Symmetrized. The optimizer runs inside a fresh random group element for every run. Coordinates are shuffled and randomly reflected before the optimizer sees them, and the answer is mapped back afterwards.

Symmetrization leaves radial bias intact and destroys orientation bias. The difference between the two runs' sequency and orthant statistics therefore isolates the orientation part. The radial part is read off separately from a normalized distance-to-center statistic and a fraction-near-bounds statistic.

The optimizers form a single ladder of covariance structure, with everything else held fixed as far as possible. We use one implementation base with identical step-size control and identical bound handling. The rungs are:

  • Full covariance. Standard CMA-ES, feasible up to a few hundred dimensions.
  • Diagonal. The covariance is restricted to its diagonal.
  • Low-rank plus diagonal. Rank $k \in \{1, 5, 20\}$, mirroring the parameterization of ELRG-VI.
  • Walsh-Hadamard structured. Samples are $S_1 H \mathrm{diag}(g) H S_2 z$, with learned diagonals and the fast transform, in the style of WHVI.

Each rung is crossed with three bound-correction rules: saturation (clipping), reflection, and resampling. Quantifying the Impact of Boundary Constraint Handling Methods on Differential Evolution established that boundary handling can dominate structural bias, so leaving it uncrossed would confound the covariance effect.

On the Bayesian-optimization side we apply the same diagnostics to BODi, COMBO, Bounce, and the simple scaled-length-scale baseline from Understanding High-Dimensional Bayesian Optimization. That baseline initializes length scales to $0.1\sqrt{d}$ and uses RAASP perturbation of 20 coordinates. Running the diagnostics here asks whether the sequency statistic recovers the bias Bounce reported and whether it finds bias in methods thought to be neutral.

The analytic companion is a small calculation for the rank-one case. It asks when an evolution-path update combined with clipping produces positively correlated sign flips across coordinates, which is the mechanism that would lower sequency.

Baselines

The naive reference point is uniform random search with the same evaluation budget. Its final points match the Binomial null exactly and define "no bias" for every statistic.

The strongest existing detection method is the BIAS toolbox together with Deep BIAS, which use per-dimension uniformity tests and a SHAP-explained classifier to label bias as center, bounds, or uniform. We run it on exactly the same final-point sets. We count our method as better if it flags statistically significant orientation bias, meaning a sequency shift under the as-is run that vanishes after symmetrization, in configurations where Deep BIAS reports "uniform". It must also do this while keeping false-positive rates at the nominal level on random search.

For search performance the reference points are as follows:

  • Full CMA-ES. The only covariance structure with a published bias measurement: 82% center bias across modular configurations in 2D, from the Deep Dive paper. Our first check is to reproduce this rate at $d=2$ before scaling up. No reported high-dimensional bias rate for any structured covariance variant was found on Lacuna.
  • Bayesian optimization. Bounce is the strongest reported method on combinatorial benchmarks, and it outperformed BODi and COMBO on 125D ClusterExpansion. No reported numerical objective value for this benchmark was found on Lacuna, so we rerun Bounce from its repository with its default budget and trust-region settings, using the same seeds as every competitor.

The key ablation is the symmetrized wrapper applied to each method. It isolates orientation bias as the ingredient, and it tests whether removing that bias alone recovers performance.

Tuning budgets are equal across methods. Each method gets its authors' defaults plus the same small grid over population size or batch size, and at least 100 independent runs per configuration.

Why not just…?

Why not just run the existing BIAS toolbox in higher dimensions? It tests marginals. A population whose final points all satisfy $s_i = s_{i+1}$ has perfectly uniform marginals and maximal low-sequency bias. Our random-search calibration, and planted-bias controls in which we inject a known correlated sign structure, will show directly whether marginal tests miss what the sequency statistic catches. If the marginal tests catch it as well, the diagnostic contribution shrinks to the radial/orientation split, and we will report that.

Why not just randomize the benchmark, as BBOB does with shifts and rotations? Randomizing the problem averages bias away in aggregate scores but never measures it, and a random rotation would also destroy the axis-aligned structure that makes diagonal and Walsh-Hadamard samplers cheap. Our symmetrization deliberately uses only the cube's own symmetries. These are cheap to apply and preserve the box, and they give a measurement rather than an average. This alternative is a genuine threat on the performance question, though. If simply randomizing coordinate order fixes BODi-style failures, the practical recommendation is just that. Our experiments report the randomized variant as a method in its own right, not as a straw man.

Why not just use a diagonal covariance, which has no cross-coordinate coupling and so no joint sign structure? The diagonal removes coupling in the sampler, but clipping can still couple coordinates through shared step-size adaptation. Diagonal structure is also known to cost accuracy and calibration elsewhere: mean-field VI reached 76.63% versus ELRG-VI's 87.24% on CIFAR-10 with ResNet-18 in the ELRG-VI paper. Diagonal search is one rung of our ladder, and if it turns out bias-free and competitive, that is a publishable negative result for structured covariances.

Why not just use the scaled-length-scale Bayesian-optimization baseline, which already matches complex methods? The authors of that baseline themselves attribute part of its success on Lasso-DNA and Mopta08 to optima lying on the boundary. We test this by moving the optima off the boundary with an offset transform.

Proposed Experiments

We run the ladder on a pure-noise objective at $d \in \{2, 10, 50, 200, 1000\}$, with full covariance capped at $d=200$. Two statistics are recorded throughout: the sequency distribution against the Binomial null, via a two-sample test, and the orthant-occupancy entropy. Both are computed for the as-is and symmetrized runs.

Consequence tests on continuous benchmarks. We use affine-recombined BBOB trajectories built from f1, f3, f15, f16, and f21, lifted to 50 and 200 dimensions. The optimum is placed at the center, on the boundary, at a low-sequency corner, or at a high-sequency corner. The corner placement is new here. A covariance structure with orientation bias should succeed at low-sequency corners, fail at high-sequency ones, and lose the gap under symmetrization.

Consequence tests on the high-dimensional Bayesian-optimization suite. We use 50D LABS, 125D ClusterExpansion, Mopta08, and Lasso-DNA, each in its original form and in sign-flipped, permuted, and interior-offset variants.

The decisive checks are three:

  • Sequency detection. Whether Walsh-Hadamard and low-rank samplers show a sequency shift at $d \geq 200$ that disappears under symmetrization. This establishes orientation bias from structured covariance.
  • Recovery of Bounce's finding. Whether BODi's and COMBO's losses on randomized variants are predicted by their measured noise-landscape sequency bias. This links our diagnostic to the failure Bounce reported.
  • Dimensional growth of center bias. Whether full-covariance center bias measured at $d=2$ grows or fades with dimension. This answers the question the Deep Dive paper left open.

A null result on the first check, with structured covariances showing only radial bias, would still be informative. It would mean practitioners can swap in cheap covariances without new orientation artifacts, and that the low-sequency failures of combinatorial Bayesian optimization come from their kernels rather than from covariance structure.