Kernel-based differentiation

Question

Consider a $\mathcal{C}^1$ function $V:\Omega\rightarrow\mathbb{R}$ where $\Omega\subset\mathbb{R}^n$. If a random vector $X$ has a parametric density $p_\theta(\textbf{x})$ that's smooth in its parameters and uniformly supported on $\Omega$ we can use the score estimator for a stochastic derivative wrt $\theta\in\mathbb{R}^m$:

$$ \nabla \mathbb{E}\left[V(X)\right] = \mathbb{E}\left[V(X)\nabla \log p_\theta(X)\right] $$

Consider now $p_\theta$ as the density for $X\sim N(f(\theta), \epsilon I)$. Then $\nabla \log p_\theta (X)= \epsilon^{-1}J_f(\theta)^\top(f(\theta)- X)$. This then makes it look like we can get a deterministic approximate derivative for $V$ without access to a gradient oracle for $V$, for small $\epsilon$:

$$ \nabla V(f(\theta))\approx\epsilon^{-1} J_f(\theta)^\top\int d\textbf{x}\;p_\theta(\textbf{x})V(\textbf{x})(f(\theta)-\textbf{x}) $$

By continuity of $\nabla V$ equality should hold in the limit. Since the integral above looks like a Gaussian convolution, perhaps this is some kind of generalization of the standard $m$-dimensional finite difference procedure for generating an approximation to $\nabla V\circ f$.

Does this have a name? If $V$ is, say, $L$-Lipschitz at $f(\theta)$, then would using a quadrature rule for the integral yield a sensible gradient approximation (sensible being as good or better than the $O(m\epsilon^2)$ 2-norm error of symmetric finite differences)?

Edit. Perhaps the integral approximation is distracting. Let's assume we can compute the exact value of the integral and ask the same question about its accuracy for a fixed $\epsilon$ (indeed, for a Monte Carlo approximation, we can make the the integral accurate with high probability by the weak LLN). Though any thoughts on the internal integral would be much-appreciated.

Answer 1

Posting a partial answer in hopes of inspiring a full one. For simplicity take $f(x)=x$. Reparameterize to $\xi\sim N(0,I)$. We are then interested in the quality of this approximation: $$ \nabla V(\theta)\approx \nabla \mathbb{E}V(\theta+\epsilon \xi) $$ Now, add an extra assumption that $V$ is $\beta$-smooth. Then we have enough regularity to interchange differentiation with integration: $$ \nabla \mathbb{E}V(\theta)+\epsilon\xi)= \mathbb{E}\nabla V(\theta+\epsilon \xi) $$

Recall that we assume that we can estimate the above term without access to a gradient oracle for $V$ with the score estimator and Monte Carlo integation. Now, note that by smoothness: $$ \|\nabla V(\theta+\epsilon \xi)-\nabla V\|\le \epsilon_1\beta\|\epsilon_2\xi\| $$ We're going to need the split $\epsilon_1\epsilon_2=\epsilon$. Then for any $r>0$:

$$ \mathbb{E}\nabla V(\theta+\epsilon \xi)=\nabla V(\theta)(1+\varphi_1)(1-\mathbb{P}\{\|\xi\|> r/\epsilon_2\})+\boldsymbol \varphi_2 $$ Where we can characterize all our error terms. $\mathbb{P}\{\|\xi\|> r/\epsilon_2\}\le O(e^{-r/\epsilon_2})$ by a $\chi_n$ tail bound for any $r$ as $\epsilon_2\rightarrow 0$. Next $\left|\varphi_1\right|=O(r\epsilon_1\beta)$. Finally with $\zeta=\|\xi\|\sim\chi_n$: $$ \|\boldsymbol \varphi_2\|=\int_r^\infty d\zeta\, p(\zeta)\sup_{\|{\xi}\|=\zeta}\nabla V(\theta+\epsilon \xi)\le \|\nabla V(\theta)\|\int_r^\infty d\zeta\, p(\zeta)(1+\beta \epsilon \zeta) $$ Re-using the same $\chi_n$ tail bound we get $\|{\boldsymbol\varphi_2}\|=O(e^{-r})$.

There is some tension because increasing $r$ reduces $\boldsymbol \varphi_2$ error at the cost of $\varphi_1$ error, but the epsilon-splitting trick with should save us. E.g., to get $\ell_2$ gradient error below $O(\alpha)$ choose $r = \Theta(-\log\alpha)$ and $\epsilon_1=\Theta(\alpha/(-\log\alpha))$ and finally $\epsilon_2=\Theta(1)$.

This is probably very loose: the analysis was lazy and I dropped a lot of lower order terms. Moreover, I didn't optimize the bounds. But at the very least it seems that we can get $O(\epsilon (-\log \epsilon))$ (relative!) accuracy. This is worse than symmetric finite differences, but we didn't use second order information here. Integrating a first-order Taylor series of $\nabla V$ about $\theta$ would probably make the error absolute rather than relative and explicitly depend on $\beta$.