Sample complexity of continuous binary search with noisy information

Studies the sample complexity of a continuous binary search problem with probabilistic noise present in the information. The authors derive a general lower bound on the complexity and propose an algorithm that can solve the problem with arbitrary accuracy and confidence. The authors also give the su...

Full description

Saved in:
Bibliographic Details
Main Authors: I-Jeng Wang, Chong, E.K.P., Quong, R.W.
Format: Conference Proceeding
Language:English
Subjects:
Approximation algorithms
Random variables
Search problems
Sufficient conditions
Upper bound
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Studies the sample complexity of a continuous binary search problem with probabilistic noise present in the information. The authors derive a general lower bound on the complexity and propose an algorithm that can solve the problem with arbitrary accuracy and confidence. The authors also give the sufficient condition on the number of samples for the success of the algorithm.< >
DOI:10.1109/CDC.1994.410970