Theoretical Analysis of Explicit Averaging and Novel Sign Averaging in Comparison-Based Search

Daiki Morinaga, Youhei Akimoto

TL;DR

Explicit averaging—the standard practice of resampling noisy objective functions to find their mean—is fundamentally flawed when dealing with heavy-tailed noise. This paper theoretically proves that for certain noise distributions, more samples can actually make your estimates worse. To fix this, the authors propose Sign Averaging, a robust alternative that averages the signs of pairwise differences to reliably estimate the order of medians, even under extreme noise.

What Problem Does This Paper Address?

In black-box optimization, we often don't have access to the true objective function $f(x)$, only a noisy version $f(x; \epsilon)$. Comparison-based algorithms, such as the Evolution Strategy with Covariance Matrix Adaptation (CMA-ES), don't care about the exact values; they only care about the ranking of candidate solutions.

The most common way to handle noise is "explicit averaging": query the function $K$ times and take the sample mean. While this works well for Gaussian noise, real-world noise (e.g., in simulations or financial modeling) can be "heavy-tailed," meaning extreme outliers are common. If the noise distribution lacks a finite mean or variance, the Law of Large Numbers breaks down. The authors set out to determine exactly when explicit averaging fails and how to provide a more robust ranking mechanism.

Methods

The authors employ two main strategies:

  1. Theoretical Analysis via Stable Distributions: They model noise using Stable Distributions $S(\alpha, \beta, \gamma, \delta)$. The parameter $\alpha \in (0, 2]$ is the "stability parameter" that determines the heaviness of the tails.
  2. $\alpha = 2$ is a Normal distribution (finite variance).
  3. $\alpha = 1$ is a Cauchy distribution (no finite mean).
  4. $\alpha < 1$ represents extremely heavy tails (e.g., Levy distribution).
  5. Sign Averaging (SA): Instead of averaging the noisy values themselves, the authors propose averaging the signs of the differences between two points $x_1$ and $x_2$.
  6. The estimator looks at $K$ pairs of samples and calculates: $\text{sign}(\sum_{k=1}^K \text{sign}(f(x_1; \epsilon_{1,k}) - f(x_2; \epsilon_{2,k})))$.
  7. Rank-Based Weighting: Because sign averaging is performed pairwise, it can lead to non-transitive rankings (e.g., A > B, B > C, but C > A). The authors introduce a weighting scheme that counts how many points in a population are estimated to be "better" than a specific point $x_i$, allowing SA to be seamlessly integrated into algorithms like CMA-ES.

Datasets

The paper uses synthetic "Test Functions" designed to simulate common optimization challenges:

  • Additive-noise ellipsoid: Noise is added directly to the function value.
  • Multiplicative-noise ellipsoid: Noise scales with the function value.
  • Linear-noise ellipsoid: Noise is a linear transformation of a noise vector.

These are tested under five noise regimes: Normal, Symmetric Stable ($\alpha=1.5$), Cauchy ($\alpha=1$), Symmetric Stable ($\alpha=0.5$), and Levy ($\alpha=0.5, \beta=1$).

Key Insights and Ideas

  • The Averaging Paradox: The paper proves a startling result (Theorem 3): if the noise is heavy-tailed enough ($\alpha < 1$), increasing the number of samples $K$ actually decreases the probability of correctly ranking two points. In these cases, explicit averaging is worse than doing nothing.
  • The Cauchy "Dead Zone": At $\alpha = 1$ (Cauchy noise), explicit averaging has zero effect on the ranking probability. No matter how many samples you take, the distribution of the mean remains as noisy as a single sample.
  • Invariance: Sign averaging is invariant under any strictly increasing transformation of the objective function. This is a powerful property for comparison-based search, as it ensures the algorithm behaves the same way regardless of whether you are optimizing $f(x)$ or $\log(f(x))$.
  • Median vs. Mean: While explicit averaging tries to estimate the order of means, sign averaging estimates the order of medians. Medians are naturally more robust to outliers, which is why SA succeeds where means fail.

Key Results

  • Theoretical Bounds: The authors provide a closed-form expression for the Order Estimation Probability (OEP). They show that for sign averaging, the OEP approaches 1 exponentially as $K$ increases, regardless of the noise's tail heaviness (Theorem 9).
  • Empirical Performance: In experiments with CMA-ES:
  • Explicit Averaging: Failed completely (diverged) when $\alpha \le 1$.
  • Sign Averaging: Successfully converged to the optimum across all tested values of $\alpha$, including the "impossible" $\alpha < 1$ cases.
  • Efficiency: For Gaussian noise ($\alpha=2$), sign averaging performed almost as well as explicit averaging, suggesting it is a "safe" default even when noise isn't heavy-tailed.

Limitations and Future Work

  • Assumption of Median Additivity: The proof for sign averaging relies on "Additivity of the Median" (Assumption 3), which holds for symmetric noise but may be violated in some highly asymmetric real-world scenarios.
  • Computational Cost: Pairwise sign averaging requires $K$ comparisons for every pair of points. While the authors proposed a weighting scheme to mitigate this, the overhead in very large populations remains a consideration.
  • Future Directions: The authors suggest investigating the Sample Median as an alternative to Sign Averaging, as it might offer similar robustness with different computational trade-offs. They also plan to test SA on a wider variety of non-stable, real-world noise distributions.

Summary updated

Abstract

In black-box optimization, noise in the objective function is inevitable. Noise disrupts the ranking of candidate solutions in comparison-based optimization, possibly deteriorating the search performance compared with a noiseless scenario. Explicit averaging takes the sample average of noisy objective function values and is widely used as a simple and versatile noise-handling technique. Although it is suitable for various applications, it is ineffective if the mean is not finite. We theoretically reveal that explicit averaging has a negative effect on the estimation of ground-truth rankings when assuming stably distributed noise without a finite mean. Alternatively, sign averaging is proposed as a simple but robust noise-handling technique. We theoretically prove that the sign averaging estimates the order of the medians of the noisy objective function values of a pair of points with arbitrarily high probability as the number of samples increases. Its advantages over explicit averaging and its robustness are also confirmed through numerical experiments.
BibTeX
@article{morinaga2025theoretical,
  author = {Daiki Morinaga and Youhei Akimoto},
  title = {{Theoretical Analysis of Explicit Averaging and Novel Sign Averaging in Comparison-Based Search}},
  journal = {IEEE Trans. Evol. Comput.},
  year = {2025},
  doi = {10.1109/tevc.2024.3465392},
}
Figure