Fl RDT based ultimate lowering of the negative spherical perceptron
  capacity
Mihailo Stojnic
We consider the classical \emph{spherical} perceptrons and study their
capacities. The famous zero-threshold case was solved in the sixties of the
last century (see, \cite{Wendel62,Winder,Cover65}) through the high-dimensional
combinatorial considerations. The general threshold, $\kappa$, case though
turned out to be much harder and stayed out of reach for the following several
decades. A substantial progress was then made in \cite{SchTir02} and
\cite{StojnicGardGen13} where the \emph{positive} threshold ($\kappa\geq 0$)
scenario was finally fully settled. While the negative counterpart ($\kappa\leq
0$) remained out of reach, \cite{StojnicGardGen13} did show that the random
duality theory (RDT) is still powerful enough to provide excellent upper
bounds. Moreover, in \cite{StojnicGardSphNeg13}, a \emph{partially lifted} RDT
variant was considered and it was shown that the upper bounds of
\cite{StojnicGardGen13} can be lowered. After recent breakthroughs in studying
bilinearly indexed (bli) random processes in
\cite{Stojnicsflgscompyx23,Stojnicnflgscompyx23}, \emph{fully lifted} random
duality theory (fl RDT) was developed in \cite{Stojnicflrdt23}. We here first
show that the \emph{negative spherical perceptrons} can be fitted into the
frame of the fl RDT and then employ the whole fl RDT machinery to characterize
the capacity. To be fully practically operational, the fl RDT requires a
substantial numerical work. We, however, uncover remarkable closed form
analytical relations among key lifting parameters. Such a discovery enables
performing the needed numerical calculations to obtain concrete capacity
values. We also observe that an excellent convergence (with the relative
improvement $\sim 0.1\%$) is achieved already on the third (second non-trivial)
level of the \emph{stationarized} full lifting.