Discrepancy Algorithms for the Binary Perceptron

The binary perceptron problem asks us to find a sign vector in the intersection of independently chosen random halfspaces with intercept −κ. 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 κ = 0 case and in the large-|κ| case. In the κ → −∞ case, we additionally characterize the storage capacity and complement our algorithmic results with an almost-matching overlap-gap lower bound.

Authors

• Shuangping Li
• Tselil Schramm
• Kangjie Zhou

Keywords

• Binary perceptron
• Discrepancy minimization
• Efficient algorithms
• Neural networks