Suppose I have a noisy equation f(x) = a, and I want to solve this with as few samples from f(x) as possible. Can anyone suggest any good algorithms, or approaches/techniques for inventing a specific one.f(x) is a noisy approximation of an exact unknown function g(x). I know the following* g(x) is monotonically increasing and takes x [0,inf) and returns [0,1]* I know the likelihood distribution of g(x) given f(x)* equally I know the exact distribution of f(x) for any g(x)Any hints?

How about kalman/recursive bayes on your series f(x) to estimate the coefficents in model g(x), which you solve analytically? Too cliche?

or if your distributions are non-gauss, use EM algo to generate mixtures in terms of gauss, and run a series of kalman's?

There are several procedures for handling this. One of the most primative (yet most effective) is the "Robins-Monro" stochastic approximation algorithm.

Thanks zeta, but I was hoping not to model g(x) as this introduces extra errors, and I've not really got any justification for any given model.frontofficequant - that sounds interesting, could you point me in the direction of any good papers on this? What sort of algorithm is it? Direct search?The concern I've been having with most of the algorithms I've tried is that they cannot make use of the special information, such as monotonicity and knowing the conditional distributions, and so they seem very slow to converge.Additionally, what I really need is to be able to bound this from below, i.e. to find the largest x such that g(x) <= a, to some confidence, however the added twist is that i think f(x) generally converges on g(x) more slowly for smaller x.I'm hoping to do this in less than 100 steps.

The original paper is:Robbins, H. and Monro, S. (1951). A stochastic approximation method. Ann. Math. Stat. 22, 400-407. I'm sure there are more recent and refined version of this algorithm that apply to different situations. In fact, there are entire text books on stochastic approximation and it's convergence properties in several contexts.