Learning with Comparison Feedback: Online Estimation of Sample
  Statistics
  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.
