Generalized Binary Search For Split-Neighborly Problems

Stephen Mussmann, Percy Liang
Proceedings of the Twenty-First International Conference on Artificial Intelligence and Statistics, PMLR 84:1561-1569, 2018.

Abstract

In sequential hypothesis testing, Generalized Binary Search (GBS) greedily chooses the test with the highest information gain at each step. It is known that GBS obtains the gold standard query cost of O(log n) for problems satisfying the k-neighborly condition, which requires any two tests to be connected by a sequence of tests where neighboring tests disagree on at most k hypotheses. In this paper, we introduce a weaker condition, split-neighborly, which requires that for the set of hypotheses two neighbors disagree on, any subset is splittable by some test. For four problems that are not k-neighborly for any constant k, we prove that they are split-neighborly, which allows us to obtain the optimal O(log n) worst-case query cost.

Cite this Paper

BibTeX
@InProceedings{pmlr-v84-mussmann18a, title = {Generalized Binary Search For Split-Neighborly Problems}, author = {Mussmann, Stephen and Liang, Percy}, booktitle = {Proceedings of the Twenty-First International Conference on Artificial Intelligence and Statistics}, pages = {1561--1569}, year = {2018}, editor = {Storkey, Amos and Perez-Cruz, Fernando}, volume = {84}, series = {Proceedings of Machine Learning Research}, month = {09--11 Apr}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v84/mussmann18a/mussmann18a.pdf}, url = {https://proceedings.mlr.press/v84/mussmann18a.html}, abstract = {In sequential hypothesis testing, Generalized Binary Search (GBS) greedily chooses the test with the highest information gain at each step. It is known that GBS obtains the gold standard query cost of O(log n) for problems satisfying the k-neighborly condition, which requires any two tests to be connected by a sequence of tests where neighboring tests disagree on at most k hypotheses. In this paper, we introduce a weaker condition, split-neighborly, which requires that for the set of hypotheses two neighbors disagree on, any subset is splittable by some test. For four problems that are not k-neighborly for any constant k, we prove that they are split-neighborly, which allows us to obtain the optimal O(log n) worst-case query cost.} }
Endnote
%0 Conference Paper %T Generalized Binary Search For Split-Neighborly Problems %A Stephen Mussmann %A Percy Liang %B Proceedings of the Twenty-First International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2018 %E Amos Storkey %E Fernando Perez-Cruz %F pmlr-v84-mussmann18a %I PMLR %P 1561--1569 %U https://proceedings.mlr.press/v84/mussmann18a.html %V 84 %X In sequential hypothesis testing, Generalized Binary Search (GBS) greedily chooses the test with the highest information gain at each step. It is known that GBS obtains the gold standard query cost of O(log n) for problems satisfying the k-neighborly condition, which requires any two tests to be connected by a sequence of tests where neighboring tests disagree on at most k hypotheses. In this paper, we introduce a weaker condition, split-neighborly, which requires that for the set of hypotheses two neighbors disagree on, any subset is splittable by some test. For four problems that are not k-neighborly for any constant k, we prove that they are split-neighborly, which allows us to obtain the optimal O(log n) worst-case query cost.
APA
Mussmann, S. & Liang, P.. (2018). Generalized Binary Search For Split-Neighborly Problems. Proceedings of the Twenty-First International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 84:1561-1569 Available from https://proceedings.mlr.press/v84/mussmann18a.html.

Related Material