From average case complexity to improper learning complexity
Amit Daniely, Nati Linial, Shai Shalev‐Shwartz · 2014
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.