Learning with Comparison Feedback: Online Estimation of Sample Statistics
This work is significant for researchers working on online algorithms and data stream processing, particularly in scenarios with limited access to data and adversarial feedback.
This paper addresses the online estimation of sample statistics like median, CDF, and mean from an adversarial sequence of integers, where each number can only be accessed via a single threshold query. The authors provide robust algorithms for these estimations and nearly matching lower bounds.
We study an online version of the noisy binary search problem where feedback is generated by a non-stochastic adversary rather than perturbed by random noise. We reframe this as maintaining an accurate estimate for the median of an adversarial sequence of integers, $x_1, x_2, \dots$, in a model where each number $x_t$ can only be accessed through a single threshold query of the form ${1(x_t \leq q_t)}$. In this online comparison feedback model, we explore estimation of general sample statistics, providing robust algorithms for median, CDF, and mean estimation with nearly matching lower bounds. We conclude with several high-dimensional generalizations.