Jtdylktuy

Suppose one has a differentiable function $f:Bbb R^ntoBbb R$ that one can evaluate but for which one has no expression for the derivative. There exist several procedure for gaining an estimate for the gradient, for example one could evaluate
$$nabla f(x)approxsum_i frac{f(x+epsilon,e_i)-f(x-epsilon, e_i)}{2epsilon} e_i,tag{1}$$
or
$$nabla f(x) approx leftlanglesum_i frac{f(x+Delta)-f(x-Delta)}{2Delta_i}e_irightrangle_{p(Delta)}.tag{2}$$
where the brackets denote the expectation value in which $Delta$ is drawn from some symmetric probability distribution $p(Delta)$ centered around $0$ (this is known as SPSA).

These methods are generic in the sense that for $epsilonto0$ or $mathrm{Var}(p(Delta))to0$ they will always converge to the gradient of $f$. However they may be slow, for example $(1)$ requires very many evaluations in high dimensions.

Sometimes one already has a candidate function $overline{nabla f}$ for $nabla f$. This candidate will in general be wrong but can for example lie in the correct quadrant. My question:

Is there a method for estimating the gradient of $f$ that uses the candidate $overline{nabla f}$ as a suggestion?

The expected benefit of using $overline{nabla f}$ would be a speed-up of the procedure. I'm sure such a thing exists, but I can't find any literature because I do not know what to search for.

I'm not sure if math stack exchange is the right place to ask such a question, so I would also appreciate it if you could point me in a direction in which I am more likely to get an answer.

For the case where $overline{nabla f} = nabla overline{f}$ for some $overline{f}$, you can use control variates.

In particular, let $Delta$ be drawn from a symmetric probability distribution $p(Delta)$, and let
$$X = sum_i frac{f(x+Delta)-f(x-Delta)}{2Delta_i}e_i,$$
$$overline{X} = sum_i frac{overline{f}(x+Delta)-overline{f}(x-Delta)}{2Delta_i}e_i.$$

If $overline{nabla f}$ is a good candidate, $X$ and $overline{X}$ will be correlated, and we can exploit that.

Knowing that $mathbb{E}[overline{X}] = overline{nabla f}$, for any constant $c$ we can write

$$nabla f(x) = mathbb{E}[X] =
mathbb{E}[X + c(overline{X} - overline{nabla f})]$$

This effectively adds a correction to each of your Monte Carlo terms to make it more accurate for the candidate. If the candidate is correlated to the actual gradient, the real accuracy will also improve. This means you would need less terms to ge the same level of accuracy.

The optimal choice for the constant is $c = -frac{text{Cov}(X, overline{X})}{text{Var}(overline{X})}$. This is typically not known in advance, but can itself be estimated using random sampling (you can either sample separately, or you can start with some hand-picked initial value and improve it as you keep sampling).

If we don't have $overline{f}$, we can try to use a local approximation to it using $overline{nabla f}$ around $x$. If $Delta$ is unlikely to be large, using the first two terms of a Taylor series should be quite accurate.