Unsupervised learning by examples: On-line versus off-line

Abstract

We study both on-line and off-line learning in the following unsupervised learning scheme: p patterns are sampled independently from a distribution on the N-sphere with a single symmetry breaking orientation. Exact results are obtained in the limit p --> infinity and N --> infinity with finite ratio p/N. One finds that for smooth pattern distributions, the asymptotic behavior of the optimal off-line and on-line learning are identical, and saturate the Cramer-Rao inequality from statistics. For discontinuous pattern distributions on the other hand, the optimal online algorithm needs (at least) twice as many examples asymptotically to reach the optimal off-line performance.