Discrepancy Algorithms for the Binary Perceptron
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866909621578366976 |
|---|---|
| author | Li, Shuangping Schramm, Tselil Zhou, Kangjie |
| author_facet | Li, Shuangping Schramm, Tselil Zhou, Kangjie |
| contents | 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 $κ\to-\infty$ case, we additionally characterize the storage capacity and complement our algorithmic results with an almost-matching overlap-gap lower bound. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2408_00796 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Discrepancy Algorithms for the Binary Perceptron Li, Shuangping Schramm, Tselil Zhou, Kangjie Data Structures and Algorithms Computational Complexity Mathematical Physics Probability 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 $κ\to-\infty$ case, we additionally characterize the storage capacity and complement our algorithmic results with an almost-matching overlap-gap lower bound. |
| title | Discrepancy Algorithms for the Binary Perceptron |
| topic | Data Structures and Algorithms Computational Complexity Mathematical Physics Probability |
| url | https://arxiv.org/abs/2408.00796 |