That is the case for every possible method that has only oracle access and no bounds.
You either need to do away with the oracle model (e.g. interval arithmetic) or need to provide explicit bounds. For example, bounds could look like: Each evaluation gives you f(x), L=L(x) and r=r(x)>0 such that the function is L-Lipschitz in the ball B_r(x). Then you are guaranteed an approximation on compact domains in finitely many oracle calls. Note that AD can give speedups but cannot help you jump from “undecidable problem” to “decidable”.
Unqualified smoothness without explicit estimates is meaningless in most contexts (polynomials are dense; not even analyticity can help you!).
Edit: Lipschitz is overkill. You need access to the modulus of absolute continuity in a small but finite compact neighborhood. Local Hoelder is totally fine as an alternative.
Not sure about this; if the domain is smooth and otherwise connected (zeros are only numerical, not truly 0, and I can transform to logs for better calculations), I would try Hamiltonian Monte Carlo if I have AD.
Sure you can do heuristics. But my point is the following:
You are given oracle access to a polynomial P on the interval [0,1]. You want to output one of:
P is large: There exists at least one point with P(x)>1.
P is small: All points have P(x)<2.
Without additional information, this problem is undecidable. Simply because I can trace all evals of your algorithm and use polynomial interpolation to find an example where your algorithm fails. If you do AD, then I also fix the derivatives you evaluated.
Of course you are right in the mathematical sense, but in a practical problem one hopes that the function isn’t that bad. In any case, I think the original example has 2 modes, which should be manageable with heuristics.
