Discrepancy Algorithms for the Binary Perceptron

Abstract

The binary perceptron problem asks us to find a sign vector in the intersection of independently chosen random halfspaces with intercept $-\hat{I}º$. We analyze the performance of the canonical discrepancy minimization algorithms of Lovett-Meka and Rothvoss/Eldan-Singh for the asymmetric binary perceptron problem. We obtain new algorithmic results in the $\hat{I}º=0$ case and in the large-$|\hat{I}º|$ case. In the $\hat{I}º\to -\infty$ case, we additionally characterize the storage capacity and complement our algorithmic results with an almost-matching overlap-gap lower bound.

64 pages