The Complexity of Learning Verification

Informally, one branch of learning theory focuses on making statements of the form 'this learned classifier is at least X good'. A common intuition underlying many bounds of this form is that some for