Retarded learning: Rigorous results from statistical mechanics

We study learning of probability distributions characterized by an unknown symmetry direction. Based on an entropic performance measure and the variat ional method of statistical mechanics we develop exact upper and lower boun ds on the scaled critical number of examples below which learning of the di rection is impossible. The asymptotic tightness of the bounds suggests an a symptotically optimal method for learning nonsmooth distributions.