ECCC-Report TR97-028https://eccc.weizmann.ac.il/report/1997/028Comments and Revisions published for TR97-028en-usTue, 15 Jul 1997 08:12:41 +0300
Paper TR97-028
| Computational Sample Complexity |
Scott E. Decatur,
Oded Goldreich,
Dana Ron
https://eccc.weizmann.ac.il/report/1997/028
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.
Tue, 15 Jul 1997 08:12:41 +0300https://eccc.weizmann.ac.il/report/1997/028