Breaking the Probability 1/2 Barrier in FIN-Type Learning
Abstract
We show that for every probabilistic FIN-type learner with success ratio greater than 24/49, there is another probabilistic FIN-type learner with success ratio 1/2 that simulates the former. We will also show that this simulation result is tight. We obtain as a consequence of this work a characterization of FIN-type team learning with success ratio between 24/49 and 1/2. We conjecture that the learning capabilities of probabilistic FIN-type learners for probabilities beginning at probability 1/2 are delimited by the sequence 8n/17n-2 for n > 2, which has an accumulation point at 8/17.
Cite
Text
Daley et al. "Breaking the Probability 1/2 Barrier in FIN-Type Learning." Annual Conference on Computational Learning Theory, 1992. doi:10.1145/130385.130408Markdown
[Daley et al. "Breaking the Probability 1/2 Barrier in FIN-Type Learning." Annual Conference on Computational Learning Theory, 1992.](https://mlanthology.org/colt/1992/daley1992colt-breaking/) doi:10.1145/130385.130408BibTeX
@inproceedings{daley1992colt-breaking,
title = {{Breaking the Probability 1/2 Barrier in FIN-Type Learning}},
author = {Daley, Robert P. and Kalyanasundaram, Bala and Velauthapillai, Mahendran},
booktitle = {Annual Conference on Computational Learning Theory},
year = {1992},
pages = {203-217},
doi = {10.1145/130385.130408},
url = {https://mlanthology.org/colt/1992/daley1992colt-breaking/}
}