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/\epsilon$ samples to learn to error $\epsilon$ (and more, if the…