Fluctuations of The Symmetric Perceptron

We study the fluctuations in the storage capacity of the symmetric binary perceptron, or equivalently, the fluctuations in the combinatorial discrepancy of a Gaussian matrix. Perkins and Xu, and Abbe, Li, and Sly recently established a sharp threshold: for some explicit constant $K_c$, the discrepancy of a Gaussian matrix is $K_c + o(1)$ with probability tending to one, but without a quantitative rate. We sharpen these results significantly. We show the fluctuations around $K_c$ of the discrepancy are at most of order $\log(n)/n$, and provide exponential tail bounds. Up to a logarithmic factor, this yields a tight characterization for the fluctuations of the symmetric perceptron and combinatorial discrepancy.