# Numerical gradient of approximated probability function

I want to find an approximation of the gradient $\nabla V(J)$ of the following function $V(J) = P(X\in T(J))$. Where $X$ is a multidimensional stochastic vector with a smooth continuous probability density and $T$ is a (convex) set that depends on some parameters $J=(J_1,...,J_n)$. $V(J)$ is considered to be many times continuously differentiable.

I have $N$ independent samples $x_n$ drawn from $X$. And $V(J)$ is approximated with the relative frequency $$\hat{V}(J)=\frac{ | \{n \mid x_n\in T(J) \}| }{N}.$$ The approximation is piecewise constant.

Now I want to find an operator $\hat{D}$ that approximates the gradient.

For example: If J is one-dimensional. The gradient could be approximated by central difference $\hat{D}\hat{V}(J) = \frac{\hat{V}(J+h)-\hat{V}(J-h)}{2h}$. The problem with central difference is that since $\hat{V}$ is piecewise constant if $h$ is chosen too small, the difference is identically $0$ for most $J$.

The number of evaluations of $\hat{V}$ should be kept small as it is naturally quite expensive to compute. The approximation should be consistent in the sense that it becomes more accurate as $N$ increases.

Is there a standard way to solve this problem? Is there a limit on how accurate the approximation could get? Does it exist a theory for this kind of problems and where can I read more about it?

-
What's the quantifier doing in the sum in the displayed equation? Do you mean a sum over all $n$ such that $x_n\in T(J)$? I think that would be more clearly expressed by a sum over "$n:x_n\in T(J)$", or perhaps even more clearly simply by "$\lvert \{n\mid x_n\in T(J)\}\rvert$". – joriki Apr 4 '11 at 12:40
Thanks @joriki . Makes more sense this way. – Nxcho Apr 4 '11 at 12:58
You're welcome. Using \mid instead of | for the "such that" bar gives the proper spacing. – joriki Apr 4 '11 at 13:01

Perhaps there might be a solution based on a Fourier transform. If $A(J)(x)$ is the indicator function of $T(J)$ and $f(x)$ is the density of $X$, you have $V(J) = \int f(x) A(J)(x)\, dx = \int \overline{\hat{f}(k)} \widehat{A(J)}(k)\, dk$. Now the gradient (wrt $J$) of $A(J)(x)$ is a rather singular object, but the gradient of its Fourier transform is likely to be a smooth function, much more tractable. You could then use your samples to produce a numerical approximation of $\hat{f}$, and integrate numerically.

-
Thank you for your answer. I see some problems with this approach. $T(J)$ is a compact set which means that the transformed integral will be an infinite one. Also I want my method to work even without much a priori knowledge of $f$ so it can be hard to get a good global estimate of the pdf. But I will investigate if I can get some good results out of this approach. – Nxcho Apr 5 '11 at 7:48