Polynomial Time Prediction Strategy with Almost Optimal Mistake Probability

Bshouty, Nader H.

doi:10.1007/978-3-540-27819-1_5

Polynomial Time Prediction Strategy with Almost Optimal Mistake Probability

Nader H. Bshouty

COLT 2004 pp. 64-76

doi:10.1007/978-3-540-27819-1_5 /colt/2004/bshouty2004colt-polynomial/

Abstract

We give the first polynomial time prediction strategy for any PAC-learnable class C that probabilistically predicts the target with mistake probability $\frac{poly(log(t))}{t}=\widetilde{O}\frac{1}{t}$ where t is the number of trials. The lower bound for the mistake probability is [HLW94] Ω(1/ t ) so our algorithm is almost optimal.

PDF COLT Semantic Scholar

Cite

Text

Bshouty. "Polynomial Time Prediction Strategy with Almost Optimal Mistake Probability." Annual Conference on Computational Learning Theory, 2004. doi:10.1007/978-3-540-27819-1_5

Markdown

[Bshouty. "Polynomial Time Prediction Strategy with Almost Optimal Mistake Probability." Annual Conference on Computational Learning Theory, 2004.](https://mlanthology.org/colt/2004/bshouty2004colt-polynomial/) doi:10.1007/978-3-540-27819-1_5

BibTeX

@inproceedings{bshouty2004colt-polynomial,
  title     = {{Polynomial Time Prediction Strategy with Almost Optimal Mistake Probability}},
  author    = {Bshouty, Nader H.},
  booktitle = {Annual Conference on Computational Learning Theory},
  year      = {2004},
  pages     = {64-76},
  doi       = {10.1007/978-3-540-27819-1_5},
  url       = {https://mlanthology.org/colt/2004/bshouty2004colt-polynomial/}
}