Toward Eecient Agnostic Learning

Results include hardness results for the most obvious generalization of the PAC model to an agnostic setting, an e cient and general agnostic learning method based on dynamic programming, relationships between loss functions for agnosticLearning, and an algorithm for a learning problem that involves hidden variables.