# How Robust is UOBYQA to Worsening, Frozen Noise?
## Investigations on the bbob Test Suite With Outliers

Dimo Brockhoff, Tanguy Villain

► To cite this version:

Dimo Brockhoff, Tanguy Villain. How Robust is UOBYQA to Worsening, Frozen Noise? Investigations on the bbob Test Suite With Outliers. GECCO 2025 Companion - Genetic and Evolutionary Computation Conference Companion, Jul 2025, Malaga, Spain. pp.1842 - 1849, 10.1145/3712255.3734354. hal-05462362

HAL Id: hal-05462362

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

Submitted on 16 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>
<figure><img src="image_2.png" /></figure>

Latest updates: https://dl.acm.org/doi/10.1145/3712255.3734354

RESEARCH-ARTICLE

# How Robust is UOBYQA to Worsening, Frozen Noise? Investigations on the bbob Test Suite With Outliers

DIMO BROCKHOFF, INRIA Saclay, Palaiseau, France

TANGUY VILLAIN, CentraleSupélec - Paris-Saclay, Gif-sur-Yvette, Ile-de-France, France

Open Access Support provided by:

INRIA Saclay

CentraleSupélec - Paris-Saclay

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

Published: 14 July 2025

Citation in BibTeX format

GECCO '25 Companion: Genetic and Evolutionary Computation Conference Companion

July 14 - 18, 2025

Malaga, Spain

Conference Sponsors:

SIGEVO
# How Robust is UOBYQA to Worsening, Frozen Noise?
## Investigations on the bbob Test Suite With Outliers

Dimo Brockhoff

Tanguy Villain

Inria and CMAP, CNRS, Ecole Polytechnique, IP Paris

CentraleSupélec and ESSEC

Palaiseau, France

Paris campus, France

firstname.lastname@inria.fr

firstname.lastname@student-cs.fr

## ABSTRACT

UOBYQA, short for Unconstrained Optimization By Quadratic Approximation, is one of the well-known solvers derived and implemented by Michael J. D. Powell. In each step, the algorithm builds a quadratic surrogate of the objective function, interpolating quadratically many points for which the true function values are known. The model is optimized within the so-called trust region and the resulting solution is evaluated next. Adaptation of the trust region radius allows for fast convergence on a wide range of (noiseless) functions without the need for derivatives.

In this workshop paper, we investigate the effect of (frozen) non-negative, i.e., worsening noise on UOBYQA with varying probability of solutions being affected by the noise. To this end, we use the COCO platform and its newest addition, the noiseer, applied to the classical bbob functions. The numerical benchmarking experiments showcase that UOBYQA is negatively affected by the noise, but surprisingly little over a wide range of noise strengths for some of the bbob functions.

## CCS CONCEPTS

* Computing methodologies → Continuous space search.

## KEYWORDS

Benchmarking, Black-box optimization

**ACM Reference Format:**

Dimo Brockhoff and Tanguy Villain. 2025. How Robust is UOBYQA to Worsening, Frozen Noise? Investigations on the bbob Test Suite With Outliers. 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.3734354

## 1 INTRODUCTION

Powell published his UOBYQA solver in 2002 to perform "Unconstrained Optimization By Quadratic Approximation" [7]. As a black-box or derivative-free algorithm, it makes sense to be compared in the context of the COCO platform and provide the numerical benchmarking data to the public for further use via COCO's data archive. We do this on the set of 24 noiseless bbob functions in another paper for the Blackbox Optimization Benchmarking workshop [1]. Here, we want to explore how UOBYQA, as implemented in the Python pdfo module by Ragonneau and Zhang [9],

can handle noisy problems. The COCO platform offers, for this case, a new functionality in 2025 where a noiseer can be wrapped around any benchmark function and disturbs its function values by adding a half-Cauchy distributed value to the function's objective value on some solutions. This non-negative noise is "frozen" or deterministic in the sense that it makes some of the solutions look worse (because the solver is supposed to minimize) and re-evaluating such a "disturbed" solution will not allow to get rid of the bad value. The amount of noise can thereby be changed as a probability $p_{add}$ that any randomly sampled search point appears changed from its original objective function value. For further details, we refer to the Github issue, describing the new feature: https://github.com/numbbo/coco-experiment/issues/36.

## 2 UOBYQA IN A NUTSHELL

UOBYQA is a trust-region method, building in each iteration a quadratic model which interpolates the objective function at $(n+1)(n+2)/2$ solutions with $n$ being the search space dimension (or, in other words, the number of variables). The model's optimum within the current trust region (a Euclidean ball of a given trust region radius around the current iterate) is evaluated next on the original objective function. Before the algorithm continues with the next iteration, the interpolation set and the trust region radius are updated. Different from other, later developed solvers by Powell such as NEWUOA, BOBYQA or LINCOA, which use underdetermined quadratic interpolation in the early stages of the algorithm, UOBYQA needs to first evaluate $(n+1)(n+2)/2$ solutions before the first time, a quadratic model is build.

UOBYQA can be seen as a typical trust-region algorithm (where in particular the trust region radius is adaptively decreased and increased), with the restriction that a lower bound on the radius is ensured. The trust region radius' lower bound by itself can only decrease with time based on certain conditions. For more details on the internal workings of the algorithms, in particular about the updates of the trust region radius and the interpolation points, we refer the interested reader to the original paper by Powell [7] which is available online via Springer and in particular provides the algorithm's pseudocode. The paper by Ragonneau and Zhang [9] further gives a more abstract view on the algorithm in the context of Powell's other solvers.

## 3 EXPERIMENTAL PROCEDURE

### 3.1 Algorithm and Parameter Tuning

For our benchmarking experiments, we use the pdfo module from the Python package index PyPI, version 2.1.0, together with the

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

This work is licensed under a Creative Commons Attribution 4.0 International License. GECCO '25 Companion, July 14-18, 2025, Malaga, Spain

© 2025 Copyright held by the owner/author(s).

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

https://doi.org/10.1145/3712255.3734354
<table><caption>**Table 1:** Median runtimes of the benchmarking experiment per function evaluation in microseconds for varying noise level $p_{add}$ and dimension.</caption><thead><tr><th></th><th>2-D</th><th>3-D</th><th>5-D</th><th>10-D</th><th>20-D</th></tr></thead><tbody><tr><td>no noise</td><td>170</td><td>180</td><td>220</td><td>490</td><td>1 700</td></tr><tr><td>p<sub>add</sub> = 0.02</td><td>200</td><td>200</td><td>250</td><td>550</td><td>1 800</td></tr><tr><td>p<sub>add</sub> = 0.05</td><td>200</td><td>200</td><td>250</td><td>480</td><td>1 400</td></tr><tr><td>p<sub>add</sub> = 0.1</td><td>180</td><td>170</td><td>210</td><td>400</td><td>1 300</td></tr><tr><td>p<sub>add</sub> = 0.2</td><td>160</td><td>130</td><td>180</td><td>390</td><td>1 300</td></tr><tr><td>p<sub>add</sub> = 0.3</td><td>180</td><td>150</td><td>150</td><td>370</td><td>1 300</td></tr><tr><td>p<sub>add</sub> = 0.4</td><td>190</td><td>170</td><td>130</td><td>370</td><td>1 300</td></tr></tbody></table>

cocoex and cocopp modules of COCO, version 2.8.1 and 2.7.3 respectively. We choose the algorithm UOBYQA [7] as the representative algorithm from pdfo in our experiments as it shows the best performance among the five solvers available in pdfo [1].

For our numerical experiments, we use the default setting of pdfo except for two changes. First, the final trust region radius was set to $10^{-15}$ to allow the algorithm to converge to COCO's (relatively difficult) hardest target precision of $10^{-8}$. Second, the budget-based stopping criterion was firing only when the total number of $10^4$ function evaluations was exhausted (instead of the default 500n which resulted in too early stopping in higher dimensions).

## 3.2 CPU Timing

In order to evaluate the CPU timing of UOBYQA, we have run its Python implementation from pdfo on the entire bbob test suite [5] for $10^4$ function evaluations according to [6] and the current example experiment of COCO (including success-based restarts until 75% of all 15 instances are solved to a precision of $10^{-8}$, the total budget of $10^4$ function evaluations is exhausted or until a maximum of 20 restarts are performed). The Python code was run on a single processor of a 64-core machine with Intel Xeon E5-2683 v4 cpus with 2.10GHz. The Python version was 3.10.8. The times per function evaluation over all default values of the $p_{add}$ parameter (i.e. $p_{add} \in \{0, 0.02, 0.05, 0.1, 0.2, 0.3, 0.4\}$) for dimensions 2, 3, 5, 10, 20 are given in Table 1. The times for larger values of $p_{add}$ are similar to the shown values for $p_{add} = 0.4$. From Table 1, we observe no clear trend when changing the noise level, $p_{add}$, but increased runtimes in 20-D by about a factor of 10 when compared to the runtimes in 2-D.

## 4 RESULTS

This section presents the results from experiments according to [6] and [3] on the benchmark functions given in [2], extended with the noiser.py towards problems with frozen noise. To this end, each bbob problem is wrapped by the COCO noiser.py, adding positive deterministic/frozen noise on x% of the search space (with $x \in \{0, 2, 5, 10, 20, 30, 40, 50, 60, 70, 80, 90, 100\}$). The corresponding percentage is prepended to the algorithm name(s) in the following cumulative runtime distribution plots: Figures 1, 2, 3, and 4. Table 2 shows, in addition, the expected runtime (ERT) for a selected set of $p_{add}$ values in dimension 20 (results for some functions

are removed entirely for readability when all ERT values are infi- nite). Additional tables and plots—in particular the ones omitted here but also for different dimensions—can be found on the supple- mentary material webpage at https://brockho.github.io/bbob2025- SupplementaryMaterial/.

The **expected runtime (ERT)**, used in Table 2, depends on a given target precision, $I_{target} = f_{opt} + \Delta f$, and is computed over all relevant trials as the number of function evaluations executed during each trial while the best function value did not reach $f_t$, summed over all trials and divided by the number of trials that actually reached $f_t$ [4, 8]. **Statistical significance** is tested with the rank-sum test for a given target $\Delta f_t$ using, for each trial, either the number of needed function evaluations to reach $f_t$ (inverted and multiplied by -1), or, if the target was not reached, the best $\Delta f$- value achieved, measured only up to the smallest number of overall function evaluations for any unsuccessful trial under consideration.

## 4.1 Global Influence Of the Noise

When looking over all bbob functions, we see that UOBYQA is clearly affected by the noise and the effect is stronger in higher dimensions: In dimension 20, even a small noise probability of 2% reduces the performance of the algorithm significantly and all positive noise probabilities behave similarly. In dimension 5, the drop in performance is more gradual until probabilities higher than 10% do not change the behavior much anymore. Except for the group of multi-modal functions (that are not solved well even in the noiseless case), all function groups show the same behavior.

## 4.2 Results on Specific Functions

The results on the single functions, however, provide more surprising insights. While on most functions, the global trend can be observed as described above, for a few functions, the behavior of UOBYQA is different.

On the **sphere function** for example, a higher dimension makes the problem “easier” to solve for UOBYQA. In dimension 5, we observe the same behavior than in the empirical runtime distributions aggregated over all functions: the performance degrades slowly with increasing noise level until there is no change anymore for values of $p_{add}$ larger than 80%. In dimension 20, on the contrary, the algorithm can still solve the sphere function to a precision of $10^{-8}$ for noise levels as high as 90%, though a factor of (only) 10–100 slower than in the noiseless case. Note that the sphere function is the only bbob function that is truly convex quadratic where UOBYQA's surrogate model fits perfectly the function as soon as enough points are evaluated which are not affected by the noise.

A similar behavior can be observed on the **Gallagher 101 peaks** function where (with restarts) the function can be solved until a noise probability of 90%. In the case of the **linear slope** function, UOBYQA even solves the function with all solutions being affected by noise.

Interesting is also to observe that for several functions, for example the separable and rotated ellipsoid but also the Bent Cigar function in 5-D, a much larger probability of noise (> 90%) is easier to solve than a medium probability (≈ 30%). The performance is too low to observe the same effect visually in 20-D.
# 5 CONCLUSIONS

Running Powell's UOBYQA solver (as implemented by Ragonneau and Zhang in their pdfo package) on the bbob suite, disturbed by additive, frozen half-Cauchy distributed noise reveals surprising behavior. In higher dimensions, UOBYQA is robust to large portions of the search space being perturbed by additive, only worsening noise on the sphere, Gallagher, and Attractive Sector functions. In lower dimensions and on functions that UOBYQA can solve without noise, even small noise levels show a negative effect on the performance.

# ACKNOWLEDGMENTS

This work was partly motivated by the COST Action CA22137 "Randomised Optimisation Algorithms Research Network" (ROAR-NET), supported by COST (European Cooperation in Science and Technology), in particular in the context of WP3 "Single- and Multiobjective Optimisation".

# REFERENCES

[1] Dimo Brockhoff and Tanguy Villain. 2025. Benchmarking Powell's Legacy: Performance of Five Derivative-Free Solvers in pdfo on the bbob Test Suite. In Genetic and Evolutionary Computation Conference (GECCO) Companion. ACM, New York, NY, USA.

[2] S. Finck, N. Hansen, R. Ros, and A. Auger. 2009. Real-Parameter Black-Box Optimization Benchmarking 2009: Presentation of the Noiseless Functions. Technical Report 2009/20. Research Center PPE. http://coco.lri.fr/downloads/download15.03/bbobdocfunctions.pdf Updated February 2010.

[3] Nikolaus Hansen, Anne Auger, Dimo Brockhoff, and Tea Tušar. 2022. Any-time Performance Assessment in Blackbox Optimization Benchmarking. IEEE Transactions on Evolutionary Computation 26, 6 (2022), 1293–1305.

[4] 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: http://dx.doi.org/10.1080/10556788.2020.1808977

[5] N. Hansen, S. Finck, R. Ros, and A. Auger. 2009. Real-Parameter Black-Box Optimization Benchmarking 2009: Noiseless Functions Definitions. Technical Report RR-6829. INRIA. http://hal.inria.fr/inria-00362633/en/

[6] N. Hansen, T. Tušar, O. Mersmann, A. Auger, and D. Brockhoff. 2016. COCO: The Experimental Procedure. ArXiv e-prints arXiv:1603.08776 (2016).

[7] Michael JD Powell. 2002. UOBYQA: unconstrained optimization by quadratic approximation. Mathematical Programming 92, 3 (2002), 555–582.

[8] Kenneth Price. 1997. Differential evolution vs. the functions of the second ICEO. In Proceedings of the IEEE International Congress on Evolutionary Computation. IEEE, Piscataway, NJ, USA, 153–157. DOI: http://dx.doi.org/10.1109/ICEC.1997.592287

[9] T. M. Ragonneau and Z. Zhang. 2023. PDFO: a cross-platform package for Powell's derivative-free optimization solvers. (2023). DOI: http://dx.doi.org/10.48550/arXiv.2302.13246 arXiv:2302.13246
<figure><img src="image_5.png" /><figcaption>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 subgroups in 5-D. As reference algorithm, the best algorithm from BBOB 2009 is shown as light thick line with diamond markers.</figcaption></figure>
<figure><img src="image_6.png" /><figcaption>Figure 2: 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 subgroups in 20-D. As reference algorithm, the best algorithm from BBOB 2009 is shown as light thick line with diamond markers.</figcaption></figure>
<figure><img src="image_7.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 5.</figcaption></figure>
<figure><img src="image_8.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 20.</figcaption></figure>