Discrepancy Algorithms for the Binary Perceptron
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _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 |