Unfortunately, the PAC model bound is so loose that it is useless in practice. Deriving tighter bounds for learning algorithms can have a significant impact on the way in which machine learning is done. Ideally, we'd like to calculate a PAC model type bound which was tight enough to use inside the program so as to causing halting before overfitting. The state of the art in PAC model bounds is relatively weak. The PAC bounds are too weak to be quantitatively useful.
Current approaches involve using a hold out set to estimate the amount of overfit.
This approach is unsatisfactory because data which could be used for training is not. From these many runs, an estimate of when overfitting occurs is made, and then the learning algorithm is applied once more to the full dataset stopping at the point where overfitting would occur. Cross validation is unsatisfactory because it is compute intensive and there is not yet a strong theoretical justification for the process. There are two techniques which I employ in reducing the bound. The first is called Microchoice bounds which starte with the observation that many learning algorithms proceed with a sequence of small choices to arrive at a final choice.