Separating Models of Learning from Correlated and Uncorrelated Data.
A. Elbaz and H. Lee and R. Servedio and A. Wan.
Journal of Machine Learning Research, 8(Feb):277--290, 2007.
Preliminary version in Eighteenth Annual Conference on Computational Learning Theory (COLT), 2005, pp. 637--651.


We consider a natural framework of learning from correlated data, in which successive examples used for learning are generated according to a random walk over the space of possible examples. Previous research has suggested that the Random Walk model is more powerful than comparable standard models of learning from independent examples, by exhibiting learning algorithms in the Random Walk framework that have no known counterparts in the standard model. We give strong evidence that the Random Walk model is indeed more powerful than the standard model, by showing that if any cryptographic one-way function exists (a universally held belief in public key cryptography), then there is a class of functions that can be learned efficiently in the Random Walk setting but not in the standard setting where all examples are independent.

pdf of conference paper

Click here for the open-access article at the JMLR website.

Back to main papers page