Spherical perceptron as a storage memory with limited errors

It has been known for a long time that the classical spherical perceptrons can be used as storage memories. Seminal work of Gardner, citeGar88, started an analytical study of perceptrons storage abilities. Many of the Gardner's predictions obtained through statistical mechanics tools have been rigorously justified. Among the most important ones are of course the storage capacities. The first rigorous confirmations were obtained in citeSchTir02,SchTir03 for the storage capacity of the so-called positive spherical perceptron. These were later reestablished in citeTalBook and a bit more recently in citeStojnicGardGen13. In this paper we consider a variant of the spherical perceptron that operates as a storage memory but allows for a certain fraction of errors. In Gardner's original work the statistical mechanics predictions in this directions were presented sa well. Here, through a mathematically rigorous analysis, we confirm that the Gardner's predictions in this direction are in fact provable upper bounds on the true values of the storage capacity. Moreover, we then present a mechanism that can be used to lower these bounds. Numerical results that we present indicate that the Garnder's storage capacity predictions may, in a fairly wide range of parameters, be not that far away from the true values.