From average case complexity to improper learning complexity

The basic problem in the PAC model of computational learning theory is to determine which hypothesis classes are effficiently learnable. There is presently a dearth of results showing hardness of learning problems. Moreover, the existing lower bounds fall short of the best known algorithms.

Authors

• Amit Daniely
• Nati Linial
• Shai Shalev-Shwartz

Keywords

No keywords are indexed for this paper.