Improved Sublinear-time Moment Estimation using Weighted Sampling
Anup Bhattacharya, Pinki Pradhan · 2025
Read Improved Sublinear-time Moment Estimation using Weighted Sampling by Anup Bhattacharya, Pinki Pradhan (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2502-15333.txt.
Introduction
Anup Bhattacharya and Pinki Pradhan present a 2025 theory paper on estimating a summary value of a large weighted set by sampling only a small part of it. The value, called a moment, raises each weight to a chosen power and adds the results. For some powers, how many samples are truly needed was still unknown.
The authors give a sampling method that works for powers above one half and prove that no fast method exists at or below one half. For powers of two and above, their sample counts match the proven lower bound exactly. They also add a new input measure that pins down sample needs beyond worst-case inputs.
Catalog record
| CREATOR | Anup Bhattacharya, Pinki Pradhan |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 45 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2502-15333
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Improved Sublinear-time Moment Estimation using Weighted Sampling Anup Bhattacharya, Pinki Pradhan Abstract In this work we study the moment estimation problem using weighted sampling. Given sample access to a set A A with n n weighted elements, and a parameter t > 0 t>0 , we estimate the t t -th moment of A A given as S t = ∑ a ∈ A w ( a ) t S_{t}=\sum_{a\in A}w(a)^{t} . For t = 1 t=1 , this is the sum estimation problem for which sublinear time algorithms are known. The moment estimation problem along with a number of its variants have been extensively studied in streaming, sublinear and distributed communication models. Despite being well studied, we don’t yet have a complete understanding of the sample complexity of the moment estimation problem in the sublinear model and in this work, we make progress on this front. On the algorithmic side, our upper bounds match the known upper bounds for the problem for t > 1 t>1 . To the best of our knowledge, no sublinear algorithms were known for this problem for 0 < t < 1 0<t<1 . We design a sublinear algorithm for this problem for t > 1 / 2 t>1/2 and show that no sublinear algorithms exist for t ≤ 1 / 2 t\leq 1/2 . We prove a Ω ( n 1 − 1 / t ln 1 / δ ϵ 2 ) \Omega(\frac{n^{1-1/t}\ln 1/\delta}{\epsilon^{2}}) lower bound for moment estimation for t > 1 t>1 , and show optimal sample complexity bound Θ ( n 1 − 1 / t ln 1 / δ ϵ 2 ) \Theta(\frac{n^{1-1/t}\ln 1/\delta}{\epsilon^{2}}) for moment estimation for t ≥ 2 t\geq 2 . Hence, we obtain a complete understanding of the sample complexity for moment estimation using proportional sampling for t ≥ 2 t\geq 2 . We also study the moment estimation problem in the beyond worst-case analysis paradigm and identify a new moment-density parameter of the input that characterizes the sample complexity of the problem using proportional sampling and derive tight sample complexity bounds with respect to that parameter. We also study the moment estimation problem in the hybrid sampling framework in which one is given additional access to a uniform sampling oracle. We show access to a hybrid sampling framework does not provide any additional gain for this problem over a proportional sampling oracle in the worst case. 1 Introduction Let A be any weighted set of n elements. Each element in A is associated with a weight using the function w:A\rightarrow[0,\infty) . Given an input parameter t>0 , the problem of estimating the t -th moment of A , expressed as S_{t}=\sum_{a\in A}w(a)^{t} , is called the moment estimation problem 1 1 1 The t -th moment of A is also defined as S_{t}=1/n\cdot\sum_{a\in A}w(a)^{t} . We follow S_{t}=\sum_{a\in A}w(a)^{t} for simplicity of calculations [ 7 ] . . In this work we study the moment estimation problem in a model in which we don’t have direct access to the weights of the elements in A , instead we get indirect access to the weights using samples from an oracle. Our objective is to obtain a good approximation of the t th moment S_{t} of A while making a small number of queries to the oracle. Estimation tasks on very large datasets are often performed using samples from the dataset. One common objective in these settings is to compute an approximate answer using only a small number of samples. Sublinear algorithms are algorithms that access only a tiny portion of the data (sublinear in the input size) and compute an approximate answer. For many problems of interest, uniform sampling-based algorithms require a lot of samples, and hence might not be very useful in designing sublinear algorithms where as weighted sampling-based algorithms often give better performance guarantees. This is the case, for example, for the sum estimation problem. Uniform sampling-based approaches require \Omega(n) samples for the sum estimation problem in the worst-case where as weighted sampling-based algorithms require only O(\sqrt{n}/\epsilon) samples [ 14 , 5 ] . This, however, uses the assumption of access to a stronger query oracle that returns samples according to a weighted distribution. In applications where access to such a stronger query oracle is available, one might use the above algorithms with better performance guarantees. One such use case is the parameter estimation problems on graphs where one is given access to a random edge sampling oracle. Details about using weighted sampling for graph parameter estimation problems and other application areas can be found in [ 14 , 2 , 5 ] . In this work we study the sample complexity of estimators for the moment estimation problem assuming access to a proportional sampling oracle on the set A . Proportional sampling on set A returns an element a\in A with probability proportional to w(a) . Let W=\sum_{a\in A}w(a) . Using proportional sampling an element a\in A is chosen with probability w(a)/W . Next, we formally define the moment estimation problem that we study in this work. Definition 1.1 . ((\epsilon,\delta)-\text{Moment Estimation}) Given sample access to a set A of n weighted elements and input parameters \epsilon,\delta\in(0,1) , t>0 , design an algorithm ALG that returns ALG(A,t,\epsilon,\delta) such that \Pr[(1-\epsilon)S_{t}\leq ALG(A,t,\epsilon,\delta)\leq(1+\epsilon)S_{t}]\geq 1-\delta The moment estimation problem is one of the fundamental problems with a number of variants that are studied in the literature of sublinear algorithms. For t=1 , this is the sum estimation problem. Motwani et al. [ 14 ] initiated the study of designing sublinear algorithms for the sum estimation problem assuming access to a proportional sampling oracle. Recently, Beretta and Tětek [ 5 ] have improved the sample complexity of the sum estimation problem to O(\sqrt{n}/\epsilon) using proportional sampling. Estimating frequency moments in streams is one of the most well-studied problems in the streaming literature [ 3 ] . Moment estimation is also well studied in the distributed communication models [ 12 ] . This problem can also be thought of as the vector norm estimation problem where the weights correspond to the entries of a vector. When the set of elements corresponds to the set of vertices in a graph and the weights correspond to the degrees of the vertices in the graph, this problem is known as the degree distribution moment estimation problem. For t=1 , this is the edge estimation problem in graphs for which Feige [ 8 ] and Goldreich and Ron [ 10 ] designed sublinear algorithms. For the related degree distribution moment estimation problem in graphs, the authors in [ 6 , 7 , 11 ] designed sublinear time algorithms in the sparse graph model in which one is allowed to make uniform vertex, degree and neighbour queries. Aliakbarpour et al. [ 2 ] designed a sublinear algorithm for estimating \sum_{a\in A}{w(a)\choose t} using O(\frac{n^{1-1/t}\ln 1/\delta}{\epsilon^{2}}) queries in the sparse graph model with additional access to a random edge oracle, where w(a) denotes the degree of vertex a . Various applications of the moment estimation problem including its variants are discussed in [ 6 , 2 , 5 ] . A number of recent works [