The Query Complexity of Estimating Weighted Averages

Google Tech Talk February 4, 2010 ABSTRACT Presented by Tony Wirth. The query complexity of estimating the mean of some [0, 1] variables is well known to the theory community. Inspired by some work by Carterette et al. [SIGIR 2006, pp 26875] on evaluating retrieval systems, and by Moffat and Zobel's new proposal for such evaluation [under review], we decided to examine the query complexity of weighted average calculation. In general, the problem requires the same number of queries as estimating the mean, as the latter is a special case. In fact, there is a matching upper bound for the weighted mean. This result remains true for any set of weights that is the normalized prefix of a divergent series. However, if the weights follow a geometric sequence, a much smaller sample is sufficient. Finally, we investigate power-law sequences of weights and show matching lower and upper bounds. This is joint work with Amit Chakrabarti and Venkatesan Guruswami and Andrew Wirth. Tony Wirth joined the faculty of the University of Melbourne's Computer Science department in 2005. Prior to that, he completed a PhD, as a Gordon Wu Fellow, at Princeton University in 2004 on approximation algorithms for clustering problems. Tony completed his undergraduate degree at the University of Melbourne, majoring in statistics. His research interests also include sequence problems in bioinformatics and adaptive sampling.