Almost Instance Optimal Sum and Moment Estimation Using Weighted Sampling

Anup Bhattacharya, Suryendu Mondal, Pinki Pradhan

We design an almost instance optimal algorithm for the sum estimation problem using weighted sampling. We show that the sample complexity for sum estimation is closely related to t…