Near-Optimal Target Learning With Stochastic Binary Signals

Mithun Chakraborty, Sanmay Das, Malik Magdon-Ismail
Proceedings of the 27th Conference on Uncertainty in Artificial Intelligence, PMLR R9:97-104, 2011.

Abstract

We study learning in a noisy bisection model: specifically, Bayesian algorithms to learn a target value V given access only to noisy realizations of whether V is less than or greater than a threshold theta. At step t = 0, 1, 2, ..., the learner sets threshold theta t and observes a noisy realization of sign(V - theta t). After T steps, the goal is to output an estimate V^ which is within an eta-tolerance of V . This problem has been studied, predominantly in environments with a fixed error probability q < 1/2 for the noisy realization of sign(V - theta t). In practice, it is often the case that q can approach 1/2, especially as theta -> V, and there is little known when this happens. We give a pseudo-Bayesian algorithm which provably converges to V. When the true prior matches our algorithm’s Gaussian prior, we show near-optimal expected performance. Our methods extend to the general multiple-threshold setting where the observation noisily indicates which of k >= 2 regions V belongs to.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR9-chakraborty11a, title = {Near-Optimal Target Learning With Stochastic Binary Signals}, author = {Chakraborty, Mithun and Das, Sanmay and Magdon-Ismail, Malik}, booktitle = {Proceedings of the 27th Conference on Uncertainty in Artificial Intelligence}, pages = {97--104}, year = {2011}, editor = {Cozman, Fabio and Pfeffer, Avi}, volume = {R9}, series = {Proceedings of Machine Learning Research}, month = {14--17 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r9/main/assets/chakraborty11a/chakraborty11a.pdf}, url = {https://proceedings.mlr.press/r9/chakraborty11a.html}, abstract = {We study learning in a noisy bisection model: specifically, Bayesian algorithms to learn a target value V given access only to noisy realizations of whether V is less than or greater than a threshold theta. At step t = 0, 1, 2, ..., the learner sets threshold theta t and observes a noisy realization of sign(V - theta t). After T steps, the goal is to output an estimate V^ which is within an eta-tolerance of V . This problem has been studied, predominantly in environments with a fixed error probability q < 1/2 for the noisy realization of sign(V - theta t). In practice, it is often the case that q can approach 1/2, especially as theta -> V, and there is little known when this happens. We give a pseudo-Bayesian algorithm which provably converges to V. When the true prior matches our algorithm’s Gaussian prior, we show near-optimal expected performance. Our methods extend to the general multiple-threshold setting where the observation noisily indicates which of k >= 2 regions V belongs to.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T Near-Optimal Target Learning With Stochastic Binary Signals %A Mithun Chakraborty %A Sanmay Das %A Malik Magdon-Ismail %B Proceedings of the 27th Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2011 %E Fabio Cozman %E Avi Pfeffer %F pmlr-vR9-chakraborty11a %I PMLR %P 97--104 %U https://proceedings.mlr.press/r9/chakraborty11a.html %V R9 %X We study learning in a noisy bisection model: specifically, Bayesian algorithms to learn a target value V given access only to noisy realizations of whether V is less than or greater than a threshold theta. At step t = 0, 1, 2, ..., the learner sets threshold theta t and observes a noisy realization of sign(V - theta t). After T steps, the goal is to output an estimate V^ which is within an eta-tolerance of V . This problem has been studied, predominantly in environments with a fixed error probability q < 1/2 for the noisy realization of sign(V - theta t). In practice, it is often the case that q can approach 1/2, especially as theta -> V, and there is little known when this happens. We give a pseudo-Bayesian algorithm which provably converges to V. When the true prior matches our algorithm’s Gaussian prior, we show near-optimal expected performance. Our methods extend to the general multiple-threshold setting where the observation noisily indicates which of k >= 2 regions V belongs to. %Z Reissued by PMLR on 04 October 2026.
APA
Chakraborty, M., Das, S. & Magdon-Ismail, M.. (2011). Near-Optimal Target Learning With Stochastic Binary Signals. Proceedings of the 27th Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R9:97-104 Available from https://proceedings.mlr.press/r9/chakraborty11a.html. Reissued by PMLR on 04 October 2026.

Related Material