PAC Learning with Improvements

Idan Attias, Avrim Blum, Keziah Naggita +3

One of the most basic lower bounds in machine learning is that in nearly any nontrivial setting, it takes $\text{at least}$ $1/\hat{I}\mu$ samples to learn to error $\hat{I}\mu$ (and more, if th…