# On the Robustness of Nelder-Mead to Positive and Negative Noise Outliers with Heavy-Tails on the BBOB Test Suite

Alexandre Chotard, Anne Auger

► To cite this version:

Alexandre Chotard, Anne Auger. On the Robustness of Nelder-Mead to Positive and Negative Noise Outliers with Heavy-Tails on the BBOB Test Suite. GECCO 2025 Companion: Proceedings of the Genetic and Evolutionary Computation Conference Companion, Jul 2025, Malaga, Spain. pp.1859-1866, 10.1145/3712255.3734335. hal-05479485

HAL Id: hal-05479485

https://inria.hal.science/hal-05479485v1

Submitted on 28 Jan 2026

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons CC BY 4.0 - Attribution - International License
# On the Robustness of Nelder-Mead to Positive and Negative Noise Outliers with Heavy-Tails on the BBOB Test Suite

Alexandre Chotard

alexandre.chotard@univ-littoral.fr

OSMOSE, LISIC, Université du Littoral de la Côte d'Opale

Calais, France

Anne Auger

anne.auger@inria.fr

Inria, CMAP, CNRS, Ecole Polytechnique, Institut

Polytechnique de Paris

Paris, France

## Abstract

We investigate the robustness to noise and outliers of the Nelder-Mead derivative-free optimization algorithm implemented in the `scipy.optimize` Python library. Using the `noisifier` module from the `COCO` platform, we investigate the impact of adding or subtracting a positive Cauchy noise to the function value with a certain probability p. This probability is varied from 0 till 0.4 allowing to appraise the impact of the noise. We find that Nelder-Mead has highly asymmetric performances with respect to adding a positive noise (i.e. degrading artificially possibly good solutions) or adding a negative noise (i.e. making possibly bad solutions appear good). When adding positive noise, Nelder-Mead shows some robustness in low dimensions (≤ 5). However adding negative noise has very detrimental consequences for the performances of Nelder-Mead, even with a low value of p or in low dimension.

## CCS Concepts

* Computing methodologies → Continuous space search.

## Keywords

Benchmarking, Black-box optimization

## ACM Reference Format:

Alexandre Chotard and Anne Auger. 2025. On the Robustness of Nelder-Mead to Positive and Negative Noise Outliers with Heavy-Tails on the BBOB Test Suite. In *Genetic and Evolutionary Computation Conference (GECCO '25 Companion), July 14-18, 2025, Malaga, Spain*. ACM, New York, NY, USA, 8 pages. https://doi.org/10.1145/3712255.3734335

## 1 Introduction

Understanding how noise impacts the behaviour of optimization algorithms is of great importance, whether relating to algorithm design, analysis, or choosing the right algorithm in applications. In continuous optimization, on a $n$-dimensional search space $\mathcal{X}$, additive noise, i.e. evaluating $x$ as $\tilde{f}(x) := f(x) + \xi$ where $f: \mathcal{X} \to \mathbb{R}$ is the function that we aim to minimize and $\xi$ is a real-valued random variable, is especially challenging as when the algorithm approaches the optimum, the difference in $f$-value between different points generally becomes negligible compared to the influence of the noise.

Instead of all $\tilde{f}$-evaluations being noisy, we consider here that an evaluation has a probability p of being noisy, and investigate how this probability p impacts the performance of an optimization algorithm. While noise if often modelled in analysis as Gaussian, we consider here noise following a Cauchy distribution, having a heavy-tail rather than an exponentially vanishing one. Thus the perturbations to the f-value can be considerably larger than in a Gaussian-noise setting. Furthermore, we separate the noise in either a positive perturbation by adding $|\xi|$ with a probability $p_{add}$, which make points appear worse than they are, and a negative perturbation by subtracting $|\xi|$ with a probability $p_{sub}$, making points appear better than they are. This allow us to investigate and quantify the symmetry or asymmetry of the algorithm with respect to positive or negative perturbations.

The algorithm that we investigate is Nelder-Mead, a well-known derivative-free comparison-based continuous optimization algorithm that is additionally affine-invariant [5]. It operates using a simplex, a geometric shape with $n + 1$ vertices in an $n$-dimensional space. The algorithm iteratively updates the simplex through four main operations: reflection, expansion, contraction, and shrinkage. In each step, the function values at the simplex vertices are evaluated, and the worst-performing vertex is replaced using one of these transformations to explore the search space efficiently. Nelder-Mead is known to be a very efficient in small dimensions ($n \le 5$), but its performances typically scales very poorly with dimension [1]. It suffers in particular from a degeneracy of the simplex: the simplex collapses into a lower-dimensional subspace.

In this context, we benchmark the `scipy.optimize` implementation of the Nelder-Mead algorithm on the bbob testbed [3] with positive and negative noise outliers and evaluate using the `COCO` platform the impact of the noise. We particularly test with different probabilities of having outliers and measure the impact on the performances.

The paper is organized as follows: in Section 2 we detail how the experiments are produced, in Section 3 we analyze our results, and in Section 4 we discuss what we learnt from these results and what we do not know.

Publication rights licensed to ACM. ACM acknowledges that this contribution was authored or co-authored by an employee, contractor or affiliate of a national government. As such, the Government retains a nonexclusive, royalty-free right to publish or reproduce this article, or to allow others to do so, for Government purposes only. Request permissions from owner/author(s).

GECCO '25 Companion, Malaga, Spain

© 2025 Copyright held by the owner/author(s). Publication rights licensed to ACM.

ACM ISBN 979-8-4007-1464-1/2025/07

https://doi.org/10.1145/3712255.3734335
<figure><img src="image_2.png" /></figure>

<figure><img src="image_3.png" /></figure>

<figure><img src="image_4.png" /></figure>

<figure><img src="image_5.png" /></figure>

<figure><img src="image_6.png" /></figure>

(a)

<figure><img src="image_7.png" /></figure>

<figure><img src="image_8.png" /></figure>

<figure><img src="image_9.png" /></figure>

<figure><img src="image_10.png" /></figure>

<figure><img src="image_11.png" /></figure>

(b)

<caption>Figure 1: Bootstrapped empirical cumulative distribution of the number of f-evaluations divided by dimension (FEvals/DIM) for 51 targets with target precision in $10^{[-8...2]}$ for all functions and dimensions in $\{2, 3, 5, 10, 20\}$. As reference algorithm, the best algorithm from BBOB 2009 is shown as light thick line with diamond markers.</caption>
<figure><img src="image_12.png" /><figcaption>Figure 2: Empirical cumulative distribution of simulated (bootstrapped) runtimes, measured in number of f-evaluations, divided by dimension (FEvals/DIM) for the 51 targets $10^{[-8..2]}$ in dimension 2.</figcaption></figure>

## 2 Experimental Procedure

Following [2] and [4], `scipyannya.fmin`'s implementation of Nelder-Mead is ran using COCO's [3] cocoex module, version 2.7.5, on the BBOB test suite from the COCO platform on instances 1 to 15 with a budget of $n \times 10^4$ function evaluations for each problem of the testbed, and dimension $n$ in {2, 3, 5, 10, 20}. The `scipy` implementation of Nelder-Mead has 4 different termination criteria, `xtol`, `ftol`, `maxfun` and `maxiter`<fnref n="1" />. In order to avoid the algorithm terminating too early, we set `xtol` to $10^{-10}$ and `ftol` to $10^{-11}$, which should be low enough relatively to the most difficult target on BBOB. We set `maxfun` to the budget $n \times 10^4$, and left `maxiter` to None. To sum up, the algorithm is launched on the noisy problem $\tilde{f}$

with the command `scipyannya.fmin(\tilde{f}, x₀, xtol = 10⁻¹⁰, ftol = 10⁻¹¹, maxfun = n * 10⁴)`, where $x₀$ is a starting point provided by COCO's ExperimentRepeater class. The version of `scipy` used in this experiment is version 1.15.2.

Each BBOB problem $f$ is wrapped by COCO `cocoex.noiser`. `Noisifier` with parameters $p_{add}$ and $p_{sub}$ to a function $\tilde{f}$ such that

$$ \tilde{f}(x) := \begin{cases} f(x) + \frac{|\xi|}{|\xi|} & \text{with probability } p_{add}, \\ f(x) - \frac{|\xi|}{|\xi|} & \text{with probability } p_{sub}, \\ f(x) & \text{else.} \end{cases} $$

Note that the events of adding positive or negative noise cannot co-occur, and $p_{add} + p_{sub} \le 1$. More specifically in our experiments, either $p_{add}$ or $p_{sub}$ is set to 0, so that we observe only positive or only negative perturbations. Furthermore, the noise is so-called frozen, meaning that for any $x \in \mathcal{X}$, multiple evaluations of $x$ will always return the same value $\tilde{f}(x)$. The noise $\xi$ follows a standard

<footnote n="1">¹`maxfun` has a default value of 200n, which is low in our setting. Perhaps surprisingly, excluding the conditions on `maxfun` and `maxiter`, the algorithm terminates only if both conditions on `xtol` and `ftol` are met rather than just one of them.</footnote>
<figure><img src="image_13.png" /><figcaption>Figure 3: Empirical cumulative distribution of simulated (bootstrapped) runtimes, measured in number of f-evaluations, divided by dimension (FEvals/DIM) for the 51 targets $10^{[-8..2]}$ in dimension 2.</figcaption></figure>

Cauchy distribution multiplied by $a := \pi/2$. The coefficient $a$ is chosen such that the probability that $|\xi| \ge k$ is approximately $1/k$ for $k \ge 10$. To investigate the effect of noise, Nelder-Mead is ran on each BBOB problem with $p_{add} + p_{sub} \in \{0, 0.02, 0.05, 0.1, 0.2, 0.3, 0.4\}$.

## 3 Results

The plots were produced using COCO's cocopp module, version 2.7.2. Each curve is labeled with the corresponding $p_{add}$ or $p_{sub}$ value followed by 'add' or 'sub', depending on whether positive noise $|\xi|$ was added or subtracted.

Figure 1 displays the ECDFs of the runtime distribution of the Nelder-Mead algorithm, for dimensions 2, 3, 5, 10 and 20, aggregated over 51 targets, and on all 24 functions of the BBOB test, showing the global scaling with dimension and outliers probabilities. The detailed ECDFs for every BBOB function are provided for dimension 2 in Figure 2 for positive outliers and in Figure 3 for negative

outliers, similarly for dimension 5 in Figure 4 and Figure 5, for dimension 10 in Figure 6 and Figure 7. Due to a lack of space the rest is not shown. Single function's ECDFs in dimension 20 are less informative as even without noise, Nelder-Mead has poor performance in dimension 20, as can be seen in Figure 1.

As one may expect, the results show that increasing $p_{add}$ or $p_{sub}$ increases the difficulty of most problems. This is less clear on functions such as f24 or f7 where Nelder-Mead stops early (as displayed by an early plus sign) due to the convergence of the simplex, as the progress we see next is due to restarts and simulated restarts. For f7 in dimension 2 for positive noise as shown in Figure 2, higher levels of noise even appear to help. One may even find this reasonable, as the difficulty on f7 is due to plateaus, and that higher noise could conceivably help in avoiding premature convergence of the simplex. However by comparing with the results on f7 with negative noise, we see that without noise we have
<figure><img src="image_14.png" /><figcaption>Figure 4: Empirical cumulative distribution of simulated (bootstrapped) runtimes, measured in number of *f*-evaluations, divided by dimension (FEvals/DIM) for the 51 targets $10^{[-8..2]}$ in dimension 5.</figcaption></figure>

identical results to $p_{add}$ equal to 0.4, thus the differences we see could be mostly stochastic and should not be overinterpreted.

The results show that Nelder-Mead is somewhat robust to the addition of positive noise. In dimension 2 as seen in Figure 2, Nelder-Mead is almost not affected for $p_{add} \le 0.2$, although its performance quickly deteriorates for $p_{add}$ equal to 0.3 and furthermore for $p_{add}$ equal to 0.4. As dimension increases however, this robustness decreases: the performances of Nelder-Mead deteriorates in dimension 3 for $p_{add} \ge 0.2$, in dimension 5 for $p_{add} \ge 0.1$ and in dimension 10 even $p_{add}$ equal to 0.02 shows some impact from the noise, while for $p_{add} \ge 0.05$ Nelder-Mead is heavily impacted.

However this robustness does not hold when subtracting positive noise. In dimension 2, even a small level of noise with $p_{sub}$ equal to 0.02 has a noticeable impact after 200 *f*-evaluations, and higher probabilities of noise quickly deteriorates ECDFs to some limit. This weakness to negative outliers quickly worsens as dimension

increases, and for dimension 5, as can be seen in Figure 5, even a small probability of noise $p_{sub}$ equal to 0.02 has catastrophic consequences for the ECDFs of Nelder-Mead, similar to $p_{sub}$ equal to 0.4 on most but the simplest functions such as the linear slope *f*5. Note that for high noise probabilities, even in low dimensions the impact of negative outliers is much more severe than for positive outliers.

# 4 Discussion

Our experiments show a large discrepancy in the ECDFs of Nelder-Mead with respect to positive or negative outliers. This asymmetry is not surprising: for negative noise, as the simplex gets closer to the optimum, the signal-to-noise ratio decreases, the best point will be more and more frozen to a particularly lucky random outlier, which will hamper the ability of the simplex to move through the search space. Negative noise bias the reflection and contraction
<figure><img src="image_15.png" /><figcaption>Figure 5: Empirical cumulative distribution of simulated (bootstrapped) runtimes, measured in number of *f*-evaluations, divided by dimension (FEvals/DIM) for the 51 targets $10^{[-8..2]}$ in dimension 5.</figcaption></figure>

steps into accepting negative outliers into the simplex. The simplex thus will be composed of more and more random lucky outliers, while non-noisy points will be progressively removed. This process continues until a new point is rejected, and the shrink step moves all points of the simplex closer to the lucky best point, allowing non-outliers into the simplex again. In contrast, positive noise biases the reflection, expansion and contraction steps to remove (possibly good) outliers from the simplex. Note that when the local variations in fitness value are small compared to the noise, as long as there are two or more outliers left in the simplex, the reflection step will tend to accept any non-perturbed point, which is not desired behaviour. When there is no outlier in the simplex, positive noise can make good points rejected and trigger the shrink step prematurely. The shrink step then is likely to add positive outliers back to the simplex. In the case of $p_{add}$ equal to 1, the effect of noise is more similar to negative noise: as the simplex approaches the optimum, the

best point will be more and more stuck to a particularly lucky random point with low noise. This is marginally less problematic than with negative outliers, as when luck becomes extreme enough, the variations in fitness value become comparable relative to the luck level. This will however take longer and longer as the simplex approaches the optimum, so the difference in practice with negative outliers should mostly be due to other effects.

While this general outline can be predicted and appear to be supported by our results, it is of little help in quantitative prediction with respect to the impact of noise on the performances of Nelder-Mead, and how much noise difficulty scales with outlier probability, the dimension of the problem or different function characteristics. Our results show that, for low enough values of $p_{add}$ ($p_{add} \le 0.05$), Nelder-Mead is almost not impacted by positive outliers in low dimension ($n \le 5$). Nelder-Mead does show some robustness for higher values of $p_{add}$, although this robustness quickly decreases as
<figure><img src="image_16.png" /><figcaption>Figure 6: Empirical cumulative distribution of simulated (bootstrapped) runtimes, measured in number of f-evaluations, divided by dimension (FEvals/DIM) for the 51 targets $10^{[-8..2]}$ in dimension 10.</figcaption></figure>

dimension increases: while in dimension 2, for $p_{add} \le 0.3$, Nelder-Mead's performances are very similar to the noiseless scenario, in dimension 5 and if $p_{add} \ge 0.1$, Nelder-Mead's performances are heavily impacted. For negative outliers, the impact is severe even in dimension 2 and for $p_{sub}$ equal to 0.02, and quickly increases as $p_{sub}$ or the dimension increases. It is not clear to us why higher dimension has such a strong effect on the sensitivity of Nelder-Mead to noise. While the general outline we discussed should hold for outliers with non heavy-tailed distributions, we do not know how much our quantitative results generalize to other outlier distribution, or how they would translate in terms of outlier probability and noise strength.

## References

[1] Nikolaus Hansen. 2009. Benchmarking the Nelder-Mead downhill simplex algorithm with many local restarts. In *Proceedings of the 11th Annual Conference Companion on Genetic and Evolutionary Computation Conference: Late Breaking*

Papers. 2403–2408.

[2] Nikolaus Hansen, Anne Auger, Dimo Brockhoff, and Tea Tušar. 2022. Anytime performance assessment in blackbox optimization benchmarking. *IEEE Transactions on Evolutionary Computation* 26, 6 (2022), 1293–1305.

[3] N. Hansen, A. Auger, R. Ros, O. Mersmann, T. Tušar, and D. Brockhoff. 2021. COCO: A Platform for Comparing Continuous Optimizers in a Black-Box Setting. *Optimization Methods and Software* 36 (2021), 114–144. Issue 1. doi:10.1080/10556788.2020.1808977

[4] Nikolaus Hansen, Tea Tušar, Olaf Mersmann, Anne Auger, and Dimo Brockhoff. 2016. COCO: The experimental procedure. *arXiv preprint arXiv:1603.08776* (2016).

[5] John A Nelder and Roger Mead. 1965. A simplex method for function minimization. *The computer journal* 7, 4 (1965), 308–313.
<figure><img src="image_17.png" /><figcaption>Figure 7: Empirical cumulative distribution of simulated (bootstrapped) runtimes, measured in number of *f*-evaluations, divided by dimension (FEvals/DIM) for the 51 targets 10[−8..2] in dimension 10.</figcaption></figure>