Graph explorer

Negative spherical perceptron

In this paper we consider the classical spherical perceptron problem. This problem and its variants have been studied in a great detail in a broad literature ranging from statistical physics and neural networks to computer science and pure geometry. Among the most well known results are those created using the machinery of statistical physics in \cite{Gar88}. They typically relate to various features ranging from the storage capacity to typical overlap of the optimal configurations and the number of incorrectly stored patterns. In \cite{SchTir02,SchTir03,TalBook} many of the predictions of the statistical mechanics were rigorously shown to be correct. In our own work \cite{StojnicGardGen13} we then presented an alternative way that can be used to study the spherical perceptrons as well. Among other things we reaffirmed many of the results obtained in \cite{SchTir02,SchTir03,TalBook} and thereby confirmed many of the predictions established by the statistical mechanics. Those mostly relate to spherical perceptrons with positive thresholds (which we will typically refer to as the positive spherical perceptrons). In this paper we go a step further and attack the negative counterpart,