## analysing statistical and computational trade-off of estimation procedures

“The collection of estimates may be determined by questions such as: How much storage isavailable? Can all the data be kept in memory or only a subset? How much processingpower is available? Are there parallel or distributed systems that can be exploited?”

**D**aniel Sussman, Alexander Volfovsky, and Edoardo Airoldi from Harvard wrote a very interesting paper about setting a balance between statistical efficiency and computational efficiency, a theme that resonates with our recent work on ABC and older considerations about the efficiency of Monte Carlo algorithms. While the paper avoids drifting towards computer science even with a notion like *algorithmic complexity*, I like the introduction of a loss function in the comparison game, even though the way to combine both dimensions is unclear. And may limit the exercise to an intellectual game. In an ideal setting one would set the computational time, like *“I have one hour to get this estimate”*, and compare risks under that that computing constraint. Possibly dumping some observations from the sample to satisfy the constraint. Ideally. Which is why this also reminds me of ABC: given an intractable likelihood, one starts by throwing away some data precision by using a tolerance ε and usually more through an insufficient statistic. Hence ABC procedures could also be compared in such terms.

In the current paper, the authors only compare schemes of breaking the sample into bits to handle each observation only once. Meaning it cannot be used in both the empirical mean and the empirical variance. This sounds a bit contrived in that the optimum allocation depends on the value of the parameter the procedure attempts to estimate. Still, it could lead to a new form of bandit problems: given a bandit with as many arms as there are parameters, at each new observation, decide on the allocation towards minimising the overall risk. (There is a missing sentence at the end of Section 4.)

Any direction for turning those considerations into a practical decision machine would be fantastic, although the difficulties are formidable, from deciding between estimators and selecting a class of estimators, to computing costs and risks depending on unknown parameters.

July 9, 2015 at 11:29 pm

You may find Eric Horvitz 1987 UAI paper (available here http://arxiv.org/abs/1304.2759) interesting, where he formalizes the explicit consideration of computation in inference and decision making.

In my view of the current practice of building probabilistic models computation is often an afterthought or only implicit, but I have written down some thoughts here, http://www.nowozin.net/sebastian/blog/becoming-a-bayesian-part-2.html