Sequential Information Maximization: When is Greedy Near-optimal?

Yuxin Chen, S. Hamed Hassani, Amin Karbasi, Andreas Krause
; Proceedings of The 28th Conference on Learning Theory, PMLR 40:338-363, 2015.

Abstract

Optimal information gathering is a central challenge in machine learning and science in general. A common objective that quantifies the usefulness of observations is Shannon’s mutual information, defined w.r.t. a probabilistic model. Greedily selecting observations that maximize the mutual information is the method of choice in numerous applications, ranging from Bayesian experimental design to automated diagnosis, to active learning in Bayesian models. Despite its importance and widespread use in applications, little is known about the theoretical properties of sequential information maximization, in particular under noisy observations. In this paper, we analyze the widely used greedy policy for this task, and identify problem instances where it provides provably near-maximal utility, even in the challenging setting of persistent noise. Our results depend on a natural separability condition associated with a channel injecting noise into the observations. We also identify examples where this separability parameter is necessary in the bound: if it is too small, then the greedy policy fails to select informative tests.

Cite this Paper


BibTeX
@InProceedings{pmlr-v40-Chen15b, title = {Sequential Information Maximization: When is Greedy Near-optimal?}, author = {Yuxin Chen and S. Hamed Hassani and Amin Karbasi and Andreas Krause}, booktitle = {Proceedings of The 28th Conference on Learning Theory}, pages = {338--363}, year = {2015}, editor = {Peter Grünwald and Elad Hazan and Satyen Kale}, volume = {40}, series = {Proceedings of Machine Learning Research}, address = {Paris, France}, month = {03--06 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v40/Chen15b.pdf}, url = {http://proceedings.mlr.press/v40/Chen15b.html}, abstract = {Optimal information gathering is a central challenge in machine learning and science in general. A common objective that quantifies the usefulness of observations is Shannon’s mutual information, defined w.r.t. a probabilistic model. Greedily selecting observations that maximize the mutual information is the method of choice in numerous applications, ranging from Bayesian experimental design to automated diagnosis, to active learning in Bayesian models. Despite its importance and widespread use in applications, little is known about the theoretical properties of sequential information maximization, in particular under noisy observations. In this paper, we analyze the widely used greedy policy for this task, and identify problem instances where it provides provably near-maximal utility, even in the challenging setting of persistent noise. Our results depend on a natural separability condition associated with a channel injecting noise into the observations. We also identify examples where this separability parameter is necessary in the bound: if it is too small, then the greedy policy fails to select informative tests.} }
Endnote
%0 Conference Paper %T Sequential Information Maximization: When is Greedy Near-optimal? %A Yuxin Chen %A S. Hamed Hassani %A Amin Karbasi %A Andreas Krause %B Proceedings of The 28th Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2015 %E Peter Grünwald %E Elad Hazan %E Satyen Kale %F pmlr-v40-Chen15b %I PMLR %J Proceedings of Machine Learning Research %P 338--363 %U http://proceedings.mlr.press %V 40 %W PMLR %X Optimal information gathering is a central challenge in machine learning and science in general. A common objective that quantifies the usefulness of observations is Shannon’s mutual information, defined w.r.t. a probabilistic model. Greedily selecting observations that maximize the mutual information is the method of choice in numerous applications, ranging from Bayesian experimental design to automated diagnosis, to active learning in Bayesian models. Despite its importance and widespread use in applications, little is known about the theoretical properties of sequential information maximization, in particular under noisy observations. In this paper, we analyze the widely used greedy policy for this task, and identify problem instances where it provides provably near-maximal utility, even in the challenging setting of persistent noise. Our results depend on a natural separability condition associated with a channel injecting noise into the observations. We also identify examples where this separability parameter is necessary in the bound: if it is too small, then the greedy policy fails to select informative tests.
RIS
TY - CPAPER TI - Sequential Information Maximization: When is Greedy Near-optimal? AU - Yuxin Chen AU - S. Hamed Hassani AU - Amin Karbasi AU - Andreas Krause BT - Proceedings of The 28th Conference on Learning Theory PY - 2015/06/26 DA - 2015/06/26 ED - Peter Grünwald ED - Elad Hazan ED - Satyen Kale ID - pmlr-v40-Chen15b PB - PMLR SP - 338 DP - PMLR EP - 363 L1 - http://proceedings.mlr.press/v40/Chen15b.pdf UR - http://proceedings.mlr.press/v40/Chen15b.html AB - Optimal information gathering is a central challenge in machine learning and science in general. A common objective that quantifies the usefulness of observations is Shannon’s mutual information, defined w.r.t. a probabilistic model. Greedily selecting observations that maximize the mutual information is the method of choice in numerous applications, ranging from Bayesian experimental design to automated diagnosis, to active learning in Bayesian models. Despite its importance and widespread use in applications, little is known about the theoretical properties of sequential information maximization, in particular under noisy observations. In this paper, we analyze the widely used greedy policy for this task, and identify problem instances where it provides provably near-maximal utility, even in the challenging setting of persistent noise. Our results depend on a natural separability condition associated with a channel injecting noise into the observations. We also identify examples where this separability parameter is necessary in the bound: if it is too small, then the greedy policy fails to select informative tests. ER -
APA
Chen, Y., Hassani, S.H., Karbasi, A. & Krause, A.. (2015). Sequential Information Maximization: When is Greedy Near-optimal?. Proceedings of The 28th Conference on Learning Theory, in PMLR 40:338-363

Related Material