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

In black-box optimization, noise in the objective function is often 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 (SA) is proposed as a simple but robust noise-handling technique. We theoretically prove that SA estimates the order of the medians of the noisy objective function values for 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.