2
$\begingroup$

Let $X_1, \ldots, X_N $ be $N$ fixed numbers. If we want an unbiased estimate of $M = (X_1 + \ldots + X_N)/N$ without actually doing an $O(n)$ sum then we can just sample a point uniformly at random, say the $i$th point, and return $X_i$. This gives us an unbiased estimate of $M$ in $O(1)$ time. This is basically the idea behind the application of Stochastic gradient descent for optimization.

Now say that we want an unbiased estimate of $f(M)$ for some concave or convex function $f$ without doing an $O(n)$ sum. For example, say that we want an unbiased estimator for $\log(1 + M)$. Because of jensen's inequality we know that if we just return $\log(1 + X_i)$ for a randomly chosen point $X_i$ then $E[\log(1 + X_i)] \le \log(1 + E[X_i]) = \log(1 + M)$ so the naive procedure is biased :(

I am trying to find literature / examples where people have tried to solve this problem or related problems.

$\endgroup$
1
  • $\begingroup$ By sgd i meant stochastic gradient descent. I have edited the question. $\endgroup$ – Pushpendre Apr 8 '18 at 19:44
1
$\begingroup$

A sequence of biased estimators $\hat{\mu}_n$ of a quantity $\mu$ a.s. converging to the value $\mu$ as $n$ goes to infinity can be turned into a biased estimator by the debiasing technique of Glynn & Rhee (2014), inspired from an earlier paper by McLeish (2012). The notion is that $$\mu=\hat{\mu}_1+\sum_{n=1}^\infty \{\hat{\mu}_{n+1}-\hat{\mu}_n\}$$ which can be replaced by the unbiased version $$\mu=\hat{\mu}_1+\sum_{n=1}^N \{\hat{\mu}_{n+1}-\hat{\mu}_n\}\frac{1}{\mathbb{P}(N\ge n)}$$ whatever the distribution on the random integer $N$.

In the current setting, a sequence of biased estimators $\hat{\mu}_n$ is given by $$\hat{\mu}_n=f(\{Y_1+...+Y_n\}/n)$$ when the $Y_i$'s are drawn at random and without replacement from the population $\{x_1,\ldots,x_N\}$. The debiased estimator is thus \begin{align*} \mu &=\hat{\mu}_1+\sum_{n=1}^N \frac{\{\hat{\mu}_{n+1}-\hat{\mu}_n\}}{\mathbb{P}(N\ge n)}\\ &=f(Y_1)+\sum_{n=1}^N \dfrac{f(\{Y_1+...+Y_{n+1}\}/n)-f(\{Y_1+...+Y_n\}/n)}{\mathbb{P}(N\ge n)}\\ &=f(Y_1)+\sum_{n=1}^N \dfrac{f(\{Y_1+...+Y_{n+1}\}/n)-f(\{Y_1+...+Y_n\}/n)}{\sum_{k=0}^n \exp\{-\lambda\}\lambda^k/k!} \end{align*} if the random variable $N$ is a Poisson $\cal{P}(\lambda)$ variable.

$\endgroup$

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.