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. 
 A: 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 an unbiased 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.
