NDLI: The Sample Complexity of Search Over Multiple Populations

Content Provider	IEEE Xplore Digital Library
Author	Malloy, M.L. Gongguo Tang Nowak, R.D.
Copyright Year	1963
Abstract	This paper studies the sample complexity of searching over multiple populations. We consider a large number of populations, each corresponding to either distribution P₀ or P₁. The goal of the search problem studied here is to find one population corresponding to distribution P₁ with as few samples as possible. The main contribution is to quantify the number of samples needed to correctly find one such population. We consider two general approaches: nonadaptive sampling methods, which sample each population a predetermined number of times until a population following P₁ is found, and adaptive sampling methods, which employ sequential sampling schemes for each population. We first derive a lower bound on the number of samples required by any sampling scheme. We then consider an adaptive procedure consisting of a series of sequential probability ratio tests, and show it comes within a constant factor of the lower bound. We give explicit expressions for this constant when samples of the populations follow Gaussian and Bernoulli distributions. An alternative adaptive scheme is discussed which does not require full knowledge of P₁, and comes within a constant factor of the optimal scheme. For comparison, a lower bound on the sampling requirements of any nonadaptive scheme is presented.
Sponsorship	IEEE Information Theory Society
Starting Page	5039
Ending Page	5050
Page Count	12
File Size	2145392
File Format	PDF
ISSN	00189448
Volume Number	59
Issue Number	8
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2013-01-01
Publisher Place	U.S.A.
Access Restriction	One Nation One Subscription (ONOS)
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Sociology Statistics Indexes Complexity theory Search problems Signal to noise ratio Reliability SPRT Biased coin CUSUM procedure multiarmed bandit quickest search rare events sequential analysis sequential thresholding sparse recovery spectrum sensing
Content Type	Text
Resource Type	Article
Subject	Library and Information Sciences Information Systems Computer Science Applications

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Sequential Testing for Sparse Recovery

Quickest Search Over Multiple Sequences

Optimal Truncated Ordered Sequential Cooperative Spectrum Sensing in Cognitive Radio

Dynamic Sample Complexity for Exact Sparse Recovery using Sequential Iterative Hard Thresholding

Distilled Sensing: Adaptive Sampling for Sparse Detection and Estimation

Information bounds and quickest change detection in decentralized decision systems

Extension of Quickest Spectrum Sensing to Multiple Antennas and Rayleigh Channels

Learning in a Changing World: Restless Multiarmed Bandit With Unknown Dynamics

Two Classes of Improved Quickest Spectrum Sensing Approaches in Cognitive Radio

The Sample Complexity of Search Over Multiple Populations

Similar Documents

Sequential Testing for Sparse Recovery

Quickest Search Over Multiple Sequences

Optimal Truncated Ordered Sequential Cooperative Spectrum Sensing in Cognitive Radio

Dynamic Sample Complexity for Exact Sparse Recovery using Sequential Iterative Hard Thresholding

Distilled Sensing: Adaptive Sampling for Sparse Detection and Estimation

Information bounds and quickest change detection in decentralized decision systems

Extension of Quickest Spectrum Sensing to Multiple Antennas and Rayleigh Channels

Learning in a Changing World: Restless Multiarmed Bandit With Unknown Dynamics

Two Classes of Improved Quickest Spectrum Sensing Approaches in Cognitive Radio

The Sample Complexity of Search Over Multiple Populations