Sample complexity of continuous binary search with noisy information
作者： I-Jeng Wang , E.K.P. Chong , R.W. Quong
关键词: Binary search algorithm 、 Worst-case complexity 、 Probabilistic logic 、 Algorithm 、 Mathematical optimization 、 Average-case complexity 、 Dynamic problem 、 Iterative deepening depth-first search 、 Probabilistic analysis of algorithms 、 Mathematics 、 Time complexity
摘要: Studies the sample complexity of a continuous binary search problem with probabilistic noise present in information. The authors derive general lower bound on and propose an algorithm that can solve arbitrary accuracy confidence. also give sufficient condition number samples for success algorithm. >
sci-hub.se 参考文章(4)
S.R. Kulkarni, S.K. Mitter, J.N. Tsitsiklis, Active Learning Using Arbitrary Binary Valued Queries Machine Learning. ,vol. 11, pp. 23- 35 ,(1993) , 10.1023/A:1022627018023
R.L. Rivest, A.R. Meyer, D.J. Kleitman, K. Winklmann, J. Spencer, Coping with errors in binary search procedures Journal of Computer and System Sciences. ,vol. 20, pp. 396- 404 ,(1980) , 10.1016/0022-0000(80)90014-8
Wassily Hoeffding, Probability Inequalities for sums of Bounded Random Variables Journal of the American Statistical Association. ,vol. 58, pp. 13- 30 ,(1963) , 10.1007/978-1-4612-0865-5_26
Dana Angluin, Philip Laird, Learning From Noisy Examples Machine Learning. ,vol. 2, pp. 343- 370 ,(1988) , 10.1023/A:1022873112823