Learning with Comparison Feedback: Online Estimation of Sample Statistics

Michela Meister, Sloan Nietert
Proceedings of the 32nd International Conference on Algorithmic Learning Theory, PMLR 132:983-1001, 2021.

Abstract

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, …$, 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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v132-meister21a, title = {Learning with Comparison Feedback: Online Estimation of Sample Statistics}, author = {Meister, Michela and Nietert, Sloan}, booktitle = {Proceedings of the 32nd International Conference on Algorithmic Learning Theory}, pages = {983--1001}, year = {2021}, editor = {Feldman, Vitaly and Ligett, Katrina and Sabato, Sivan}, volume = {132}, series = {Proceedings of Machine Learning Research}, month = {16--19 Mar}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v132/meister21a/meister21a.pdf}, url = {https://proceedings.mlr.press/v132/meister21a.html}, abstract = {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, …$, 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.} }
Endnote
%0 Conference Paper %T Learning with Comparison Feedback: Online Estimation of Sample Statistics %A Michela Meister %A Sloan Nietert %B Proceedings of the 32nd International Conference on Algorithmic Learning Theory %C Proceedings of Machine Learning Research %D 2021 %E Vitaly Feldman %E Katrina Ligett %E Sivan Sabato %F pmlr-v132-meister21a %I PMLR %P 983--1001 %U https://proceedings.mlr.press/v132/meister21a.html %V 132 %X 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, …$, 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.
APA
Meister, M. & Nietert, S.. (2021). Learning with Comparison Feedback: Online Estimation of Sample Statistics. Proceedings of the 32nd International Conference on Algorithmic Learning Theory, in Proceedings of Machine Learning Research 132:983-1001 Available from https://proceedings.mlr.press/v132/meister21a.html.

Related Material