Dangers of using the noisy oracle without provable error-bounds #51
-
|
My understanding of the noisy oracle is that you provide a function to compute it along with error-bounds that describe the maximum difference between the exact and noisy versions. My exact simulation is a long simulation and I wish to provide the noisy oracle by running the same simulation-program with lower values on precision parameters (such as floating point width etc). The only error-bound I can provide with this method is some conservative estimate, I have nothing that I can truly prove. What happens if - for some value in my domain - my estimate is slightly wrong? Will it cause mayhem like calling a binary search on a non-sorted list or will it just slightly confuse the algorithm and slow down the convergence? |
Beta Was this translation helpful? Give feedback.
Replies: 1 comment 1 reply
-
|
There is one complication that could arise: if you evaluate the true global optimum (or very close to it) with the noisy oracle, and give a wrong estimate, the algorithm may never realize that the true optimum is located in that region, and will not perform an accurate evaluation in that area. I guess you could consider this as "confusing the algorithm", rather than mayhem. The reason for this is that the algorithm also considers re-evaluating a point that was evaluated with the noisy oracle, using the accurate oracle: this is based on the provided bounds, if the algorithm estimates that the true optimum is precisely where the noisy evaluation was confused. This estimate is based on the given bounds: the algorithm does not assume that the bounds could be wrong. It will not break anything, but the convergence proof of the algorithm fails if your error bounds turn out to be wrong. |
Beta Was this translation helpful? Give feedback.
-
|
Very helpful, thank you. I guess that possibility is acceptable, since the goal of optimizing for me is to find a 'good' solution. I think my fears were based on thinking about gradient-based methods, where an imprecise evaluation would result in an extremely misleading derivative in terms of magnitude and direction. |
Beta Was this translation helpful? Give feedback.
There is one complication that could arise: if you evaluate the true global optimum (or very close to it) with the noisy oracle, and give a wrong estimate, the algorithm may never realize that the true optimum is located in that region, and will not perform an accurate evaluation in that area. I guess you could consider this as "confusing the algorithm", rather than mayhem.
The reason for this is that the algorithm also considers re-evaluating a point that was evaluated with the noisy oracle, using the accurate oracle: this is based on the provided bounds, if the algorithm estimates that the true optimum is precisely where the noisy evaluation was confused. This estimate is based on the g…