TR97-028 Authors: Scott E. Decatur, Oded Goldreich, Dana Ron

Publication: 15th July 1997 08:12

Downloads: 1542

Keywords:

In a variety of PAC learning models, a tradeoff between time and

information seems to exist: with unlimited time, a small amount of

information suffices, but with time restrictions, more information

sometimes seems to be required.

In addition, it has long been known that there are

concept classes that can be learned in the absence of computational

restrictions, but (under standard cryptographic assumptions) cannot be

learned in polynomial time regardless of sample size. Yet,

these results do not answer the question of whether there are classes

for which learning from a small set of examples is infeasible, but

becomes feasible when the learner has access to (polynomially) more

examples.

To address this question, we introduce a new measure of learning

complexity called computational sample complexity which

represents the number of examples sufficient for polynomial time

learning with respect to a fixed distribution. We then show

concept classes that (under similar cryptographic assumptions) possess

arbitrary sized gaps between their standard (information-theoretic)

sample complexity and their computational sample complexity. We also

demonstrate such gaps for learning from membership queries and

learning from noisy examples.