# Unbiased estimation of convex function of a sum of random variables

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.

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

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.