Optimal mass estimation in the conditional sampling model

The conditional sampling model, introduced by Canonne, Ron and Servedio (SODA 2014, SIAM J. Comput. 2015) and independently by Chakraborty, Fischer, Goldhirsh and Matsliah (ITCS 2013, SIAM J. Comput. 2016), is a common framework for a number of studies concerning strengthened models of distribution testing. A core task in these investigations is that of estimating the mass of individual elements. The above mentioned works, and the improvement of Kumar, Meel and Pote (AISTATS 2025), provided polylogarithmic algorithms for this task.

In this work we shatter the polylogarithmic barrier, and provide an estimator for the mass of individual elements that uses only O(log log N ) + O(poly(1/ε)) conditional samples. We complement this result with an Ω(log log N ) lower bound.

We then show that our mass estimator provides an improvement (and in some cases a unifying framework) for a number of related tasks, such as testing by learning of any labelinvariant property, and distance estimation between two (unknown) distributions. In light of some known lower bounds for common restricted models, our results imply that the full power of the conditional model is indeed required for the doubly-logarithmic upper bound.

Finally, we exponentially improve the previous lower bound on testing by learning of labelinvariant properties from double-logarithmic to Ω(log N ) conditional samples, whereas our testing by learning algorithm provides an upper bound of O(poly(1/ε) • log N log log N ).