4
$\begingroup$

There is a real-valued random variable $R$. Define a finite set of random variables ("data points") $$X_i = R + Z_i \; \text{for } i\in\{1,\ldots,n\},$$ where $Z_i$ are identically and independently distributed, mean-zero, and independent of $R$. The prior distributions of $R$ and the $Z_i$ are given; the support of each is the real line.

Define the conditional, or posterior, expectation of $R$ given particular realizations of the data $$\hat{R}(x_1,\ldots,x_n)= \mathbb{E}[R \mid X_1=x_1,\ldots,X_n=x_n]. $$ (This is the expectation of $R$ assessed by someone who sees the data points but not $R$ itself, and is a measurable function $\mathbb{R}^n \to \mathbb{R}$.) The question is: how much can an adversary with a given amount of manipulation power over a single data point move this estimate?

More precisely, fix a number $\Delta$. I am looking for a bound, which is useful as $n$ grows large, on $$M_n(\Delta)=\mathbb{E}[\hat{R}(X_1+\Delta,X_2,\ldots,X_n) - \hat{R}(X_1,X_2,\ldots,X_n)].$$ This expectation is an integral over all uncertainty in the model (i.e. in $R$ and the $X_i$), though I believe it should be possible to give a good bound even conditional on $R$.

We can take all random variables to be square-integrable if necessary, and make any other convenient assumptions.

A conjecture is that the manipulability is small in the sense that $M(\Delta) \to 0 $ as $n \to \infty$ and indeed $M_n'(\Delta) \to 0$ as well.

The conclusion may seem obvious because the posterior distribution of $R$ conditional on the data $X_1,\ldots,X_n$ converges to a point mass whose location is independent of the realization of $X_1$. But this does not readily imply a bound on the $L^1$ norm of the difference between $\hat{R}(X_1+\Delta,\ldots,X_n)$ and $R$, or the difference between $\hat{R}(X_1+\Delta,\ldots,X_n)$ and the unmanipulated estimate $\hat{R}(X_1,\ldots,X_n)$. It could be that the manipulation has a slowly decaying probability of achieving very large deviations in the estimate, so that it messes up the expectation.

$\endgroup$
  • 1
    $\begingroup$ Do we know anything about the dependence between $\theta$ and the $\epsilon_i$? $\endgroup$ – Nate Eldredge Aug 4 at 19:25
  • $\begingroup$ Independent of $\theta$, thanks! $\endgroup$ – Ben Golub Aug 4 at 19:29
  • $\begingroup$ So then, doesn't $\hat{\theta}$ just equal $(X_1+\dots+X_n)/n - \mu$ where $\mu = \mathbb{E}[\epsilon_i]$? Then the quantity you're asking about is exactly equal to $\delta/n$. $\endgroup$ – Nate Eldredge Aug 4 at 19:30
  • $\begingroup$ In general, the posterior mean won't satisfy that formula. Among other things, if you have a very strong prior that $\theta$ is near some value, then you'll have to adjust your estimate in that direction (this is so even when all rv's are Gaussian). More generally such adjustments will take a complicated form. $\endgroup$ – Ben Golub Aug 4 at 19:34
  • $\begingroup$ Do you also assume that the $\epsilon$’s have distributions with mean 0, median 0, or symmetry about the origin? $\endgroup$ – Matt F. Aug 5 at 4:12
0
$\begingroup$

There is no bound independent of $R$.

In what follows, I use my proposed notation, with $Y$ instead of $R$. Take \begin{align} Z &\sim N(0,1) \\ Y &\sim \text{even mix of } N(b,1) \text{ and } N(-b,1) \\ X &\sim \text{even mix of } N(b,\sqrt{2}) \text{ and }N(-b,\sqrt{2}) \end{align} So \begin{align} P(Z=z) &= \frac{1}{\sqrt{2\pi}\ \ }\,e^{-z^2/2} \\ P(Y=y) &= \frac{1}{2\sqrt{2\pi}}\left(e^{-(y-b)^2/2} + e^{-(y+b)^2/2}\right)\\ P(X=x) &= \frac{1}{\ 4\sqrt{\pi}\ }\left(e^{-(x-b)^2/4} + e^{-(x+b)^2/4}\right) \end{align} Suppose we have a single observation, namely $x$. Then \begin{align} P(Y'=y|X=x) &= \frac{P(x|y)P(y)}{P(x)}\\ &= \frac{\frac{1}{\sqrt{2\pi}\ \ }\,e^{-(x-y)^2/2}\frac{1}{2\sqrt{2\pi}}\left(e^{-(y-b)^2/2} + e^{-(y+b)^2/2}\right)} {\frac{1}{\ 4\sqrt{\pi}\ }\left(e^{-(x-b)^2/4} + e^{-(x+b)^2/4}\right)}\\ &= \frac{e^{-(x^2+b^2)/2}\left(e^{-y^2+by+xy} + e^{-y^2-by+xy}\right)} {\sqrt{\pi}\left(e^{-(x-b)^2/4} + e^{-(x+b)^2/4}\right)} \\ \\ E[Y'|X=x] &= \int_{y=-\infty}^\infty y\,P(Y'=y|X=x)\,dy\\ &= \frac{e^{-(x^2+b^2)/2}\left((x+b)e^{(x+b)^2/4} + (x-b)e^{(x-b)^2/4}\right)} {2\left(e^{-(x-b)^2/4} + e^{-(x+b)^2/4}\right)} \\ &= \frac{(x+b)e^{bx/2} + (x-b)e^{-bx/2}} {2\left(e^{bx/2} + e^{-bx/2}\right)} \\ \\ \frac{dE[Y'|X=x]}{dx}{\Large|}_{x=0} &= \frac{b^2+2}{4} \end{align} So the expectation of $Y'$ can be made to depend on $x$ with arbitrarily large sensitivity. Any bound on this sensitivity would likely be of the order of the variance of $Y$.

$\endgroup$
  • $\begingroup$ Where is $n$ in this answer? It's obvious you can't give a good bound fixing $n=1$ or 2. The question is whether the manipulation power over one data point grows small as one accumulates many other unmanipulated data points. See comments at the end the question. $\endgroup$ – Ben Golub Aug 5 at 17:37
  • $\begingroup$ If there are $n$ observations, can't we just repeat the analysis where $Y'$ incorporates the first $n-1$, and then $Y''$ incorporates the one new observation? Meanwhile I expect a direct formula for the sensitivity would be roughly $b^2/4n$. $\endgroup$ – Matt F. Aug 5 at 17:48
  • $\begingroup$ So in your example, the conjecture that sensitivity decays with n would be satisfied, for a given distribution of R and upper bound on the manipulation. But the question is whether this holds for all distributions. $\endgroup$ – Ben Golub Aug 5 at 19:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.