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:
- Evolutionary Algorithms (EAs): Including Random Search and various Evolution Strategies (ES).
- 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