Discrepancy Algorithms for the Binary Perceptron
<|reference_start|>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 $-\kappa$. 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 $\kappa = 0$ case and in the large-$|\kappa|$ case. In the $\kappa\to-\infty$ case, we additionally characterize the storage capacity and complement our algorithmic results with an almost-matching overlap-gap lower bound.<|reference_end|>
@article{li2024discrepancy,
    title={Discrepancy Algorithms for the Binary Perceptron},
    author={Shuangping Li, Tselil Schramm, Kangjie Zhou},
    journal={arXiv preprint arXiv:2408.00796},
    year={2024},
    archivePrefix={arXiv},
    eprint={2408.00796},
    primaryClass={cs.DS cs.CC math-ph math.MP math.PR}
}