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.