Noisy Derivative-Free Optimization With Value Suppression

Hong Wang, Hong Qian, Yang YuAAAI 2018 · OpenReview

Abstract

Derivative-free optimization (DFO) is a powerful tool for solving complex problems like policy search in noise-free environments. However, real-world applications often involve noisy evaluations, which can severely degrade DFO performance by creating "fake winners"—suboptimal solutions that appear superior due to noise. This work introduces Value Suppression (VS), a simple yet effective noise-handling mechanism. Unlike traditional methods that handle noise immediately or at the point of comparison, VS delays noise handling until the optimization process stalls. By re-evaluating the best-so-far solutions only when progress ceases, VS effectively "suppresses" overestimated values and allows the search to continue. Experiments on synthetic benchmarks and reinforcement learning tasks demonstrate that VS significantly outperforms existing methods in both accuracy and computational efficiency.

The Challenge of Noisy Optimization

Derivative-free optimization is essential for "black-box" scenarios where gradients are unavailable, such as hyperparameter tuning or training robot policies. In these settings, the algorithm relies solely on function evaluations. In noisy environments, a mediocre solution might receive an exceptionally high score by chance. This "lucky" outlier becomes a "fake winner," misleading the algorithm into focusing on a suboptimal region of the search space.

Traditional approaches to mitigate this include sampling, which averages multiple evaluations for every point, and threshold selection, which requires a new solution to be significantly better than the current best to be accepted. However, sampling is computationally expensive, and thresholding can still be inefficient or fail to dislodge a well-entrenched fake winner.

Value Suppression: A "Lazy" Approach to Noise

The proposed Value Suppression mechanism operates on a simple principle: do nothing about noise until you get stuck. The algorithm proceeds as follows:

  1. Search: The optimization continues normally, tracking the best-so-far solutions.
  2. Stagnation Trigger: If the best-so-far set hasn't been updated for a predefined number of iterations ($u$), the algorithm assumes it might be trapped by a noisy outlier.
  3. Suppression: The algorithm then re-evaluates the current best solutions. This re-sampling likely reveals the true, lower performance of "fake winners," effectively "suppressing" their values.
  4. Resumption: With the corrected values, the algorithm can move past the previous "ghost" peaks and resume its search for the true global optimum.

This framework was integrated into the SRACOS algorithm, resulting in SSRACOS (Suppressed SRACOS).

Experimental Evaluation

The authors tested VS against standard benchmarks and complex control tasks:

  • Synthetic Functions: Ackley and Sphere functions with added Gaussian noise.
  • Reinforcement Learning: Eight OpenAI Gym environments (e.g., Humanoid-v1, LunarLander-v2) where noise is inherent due to varying initial states.

Key Results

Value Suppression consistently outperformed sampling, re-evaluation, and thresholding methods across both synthetic and real-world benchmarks.

Performance comparison on synthetic Ackley and Sphere functions under noise.

On the 100-dimensional Ackley function, VS achieved a final value of 0.93, compared to 1.32 for Sampling and 3.69 for the baseline without noise handling. Crucially, VS reached these superior results with a significantly lower computational budget, often requiring less than half the evaluations of sampling-based methods.

Accumulated rewards on eight OpenAI Gym tasks with varying levels of extra noise.

In reinforcement learning tasks, VS demonstrated remarkable robustness. As shown in the multi-task comparison, VS (green line) consistently maintained higher accumulated rewards than competing methods, even as environmental noise increased. This suggests that the "lazy" re-evaluation strategy is particularly well-suited for high-dimensional, noisy policy search problems.

Conclusion

Value Suppression offers a paradigm shift in noise handling for derivative-free optimization. By delaying noise correction until it is strictly necessary to overcome stagnation, the method avoids the high overhead of constant sampling while effectively neutralizing the impact of noisy outliers. Its performance across diverse tasks highlights its potential as a robust and efficient standard for noisy black-box optimization. Future work may explore its utility in purely deterministic environments to help algorithms escape local optima.

Summary updated

Abstract

Derivative-free optimization has shown advantage in solving sophisticated problems such as policy search, when the environment is noise-free. Many real-world environments are noisy, where solution evaluations are inaccurate due to the noise. Noisy evaluation can badly injure derivative-free optimization, as it may make a worse solution looks better. Sampling is a straightforward way to reduce noise, while previous studies have shown that delay the noise handling to the comparison time point (i.e., threshold selection) can be helpful for derivative-free optimization. This work further delays the noise handling, and proposes a simple noise handling mechanism, i.e., value suppression. By value suppression, we do nothing about noise until the best-so-far solution has not been improved for a period, and then suppress the value of the best-so-far solution and continue the optimization. On synthetic problems as well as reinforcement learning tasks, experiments verify that value suppression can be significantly more effective than the previous methods.
BibTeX
@inproceedings{wang2018noisy,
  author = {Hong Wang and Hong Qian and Yang Yu},
  title = {{Noisy Derivative-Free Optimization With Value Suppression}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2018},
  url = {https://openreview.net/forum?id=ry-jXk-dZB},
}
Figure