Discrete perceptrons

Perceptrons have been known for a long time as a promising tool within the neural networks theory. The analytical treatment for a special class of perceptrons started in seminal work of Gardner citeGar88. Techniques initially employed to characterize perceptrons relied on a statistical mechanics approach. Many of such predictions obtained in citeGar88 (and in a follow-up citeGarDer88) were later on established rigorously as mathematical facts (see, e.g. citeSchTir02,SchTir03,TalBook,StojnicGardGen13,StojnicGardSphNeg13,StojnicGardSphErr13). These typically related to spherical perceptrons. A lot of work has been done related to various other types of perceptrons. Among the most challenging ones are what we will refer to as the discrete perceptrons. An introductory statistical mechanics treatment of such perceptrons was given in citeGutSte90. Relying on results of citeGar88, citeGutSte90 characterized many of the features of several types of discrete perceptrons. We in this paper, consider a similar subclass of discrete perceptrons and provide a mathematically rigorous set of results related to their performance. As it will turn out, many of the statistical mechanics predictions obtained for discrete predictions will in fact appear as mathematically provable bounds. This will in a way emulate a similar type of behavior we observed in citeStojnicGardGen13,StojnicGardSphNeg13,StojnicGardSphErr13 when studying spherical perceptrons.