arXiv preprint ·
Almost Instance Optimal Sum and Moment Estimation Using Weighted Sampling
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
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 the $\ell_2$ norm of the weighted sampling distribution. We show an almost instance optimal lower bound for this problem as well. We also study the moment estimation problem and design an algorithm that has better instance-wise sample complexity bounds.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
Explicit Asymptotic Bounds for Sequential Calibration Beyond $T^{2/3}$
Generating cyclic pivot Gray codes for well-ordered $k$-degenerate graphs in constant amortized time
How to Fix a Broken Metric: A Linear Kernel, Tight Bounds, and Tree Metrics
Envy-free Allocations with Individual Payments
When Can Stateless Recovery Defeat Byzantine Quorum Safety? A Tight Normal Form for Single-Step BFT
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.