Analysis of Different Types of Regret in Continuous Noisy Optimization

Sandra Astete-Morales, Marie-Liesse Cauwet, Olivier TeytaudGECCO 2016

Abstract

The performance measure of an algorithm is a crucial part of its analysis. Performance can be determined by studying the convergence rate of the algorithm in question, specifically by measuring how a sequence of approximations approaches the real optimum. The concept of "Regret" is widely used in bandit literature and optimization to assess this performance. In numerical evaluations of noisy algorithms, researchers often rely on approximations of regret. This paper discusses two types of approximations used in practice: Approximate Simple Regret (ASR) and Robust Simple Regret (RSR). Using specific algorithms and the noisy sphere function, we demonstrate that ASR—a metric common in many optimization testbeds—fails to accurately estimate the true Simple Regret (SR) convergence rate, often leading to misleading conclusions about algorithm quality.

Introduction

In continuous noisy optimization, the goal is to find the minimum of a function where every observation is corrupted by random noise. To evaluate how well an algorithm performs, we typically measure its Simple Regret (SR): the difference between the true function value at the algorithm's current "best guess" (the recommendation point) and the actual global optimum.

However, many popular benchmarking frameworks, such as BBOB/COCO, utilize Approximate Simple Regret (ASR). ASR tracks the best search point ever evaluated rather than the algorithm's formal recommendation. While ASR is mathematically convenient because it is monotonic (it never increases), this paper investigates a fundamental concern: Is ASR actually a reliable proxy for SR?

Methodology

The authors analyze the convergence rates—defined as the slope $s(Regret)$ on a log-log scale—for two distinct classes of algorithms:

  1. Evolutionary Algorithms (EAs): Including Random Search and various Evolution Strategies (ES).
  2. Stochastic Gradient Descent (SGD): Specifically Shamir’s and Fabian’s algorithms, which estimate gradients through function evaluations.

The study utilizes the Noisy Sphere Function ($f(x) = \|x - x^*\|^2 + \mathcal{N}(0, \sigma^2)$) as the primary benchmark. This function allows for clean theoretical proofs and controlled experiments, serving as a standard model for understanding how algorithms navigate quadratic landscapes under Gaussian noise.

The Discrepancy: Search vs. Recommendation

The core issue identified is the difference between a "search point" and a "recommendation." ASR rewards "lucky" search points. In a noisy environment, an algorithm might evaluate a point far from the optimum that happens to return a very low value due to a negative noise realization. ASR records this as a success. However, unless the algorithm actually "knows" this point is the optimum and recommends it, the true Simple Regret remains high.

This leads to a performance inversion where metrics and actual performance disagree:

  • Random Search: Under ASR, it shows a healthy convergence rate (slope of $-2/d$). Under true SR, it does not converge at all (slope $\ge 0$).
  • High-Performing SGD: Algorithms like Shamir’s achieve an optimal SR slope of $-1$. However, under ASR, they appear to have a slope of $0$, making them look like they are failing to converge.

Key Results and Comparison

The theoretical findings are summarized in the following comparison of convergence slopes:

Algorithm Simple Regret (SR) Slope Approx. Simple Regret (ASR) Slope
Random Search 0 (No convergence) $-2/d$ (False convergence)
Shamir (SGD) $-1$ (Optimal) 0 (False stagnation)
Fabian (SGD) $\approx -1$ $\approx 0$

Experimental validation on a 2D noisy sphere confirmed these results. When using ASR, the leaderboard was completely inverted: the superior SGD algorithms appeared to be the worst performers, while basic Evolutionary Strategies appeared superior simply because they sampled more points, increasing their chances of encountering a "lucky" noise-corrupted value.

Robust Simple Regret (RSR)

The authors also evaluate Robust Simple Regret (RSR), a metric that requires an algorithm to maintain a good recommendation over a specific window of time. While RSR mitigates some of the extreme optimism found in ASR, the paper proves that it can still overestimate performance compared to the true SR, failing to act as a perfect substitute.

Conclusion

The study concludes that ASR is a dangerously misleading metric for noisy optimization. It can make poor algorithms look optimal and high-performing algorithms look non-convergent. While SR is more difficult to use in standard benchmarking tools because it is non-monotonic, it remains the only truthful measure of an algorithm's optimization logic. The authors suggest that the optimization community must find new metrics that are both stable for benchmarking and faithful to the actual convergence of the algorithm's recommendations.

Summary updated

Abstract

The performance measure of an algorithm is a crucial part of its analysis. The performance can be determined by the study on the convergence rate of the algorithm in question. It is necessary to study some (hopefully convergent) sequence that will measure how "good" is the approximated optimum compared to the real optimum. The concept of Regret is widely used in the bandit literature for assessing the performance of an algorithm. The same concept is also used in the framework of optimization algorithms, sometimes under other names or without a specific name. And the numerical evaluation of convergence rate of noisy algorithms often involves approximations of regrets. We discuss here two types of approximations of Simple Regret used in practice for the evaluation of algorithms for noisy optimization. We use specific algorithms of different nature and the noisy sphere function to show the following results. The approximation of Simple Regret, termed here Approximate Simple Regret, used in some optimization testbeds, fails to estimate the Simple Regret convergence rate. We also discuss a recent new approximation of Simple Regret, that we term Robust Simple Regret, and show its advantages and disadvantages.
BibTeX
@inproceedings{astetemorales2016analysis,
  author = {Sandra Astete-Morales and Marie-Liesse Cauwet and Olivier Teytaud},
  title = {{Analysis of Different Types of Regret in Continuous Noisy Optimization}},
  booktitle = {GECCO},
  year = {2016},
}
Figure