Metraipolis › archive › dc_e89a3a5ed602
Online Algorithms Cannot Find Isolated Perceptron Solutions — arXiv:2611.03397
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2611.03397
- License (as archived)
- CC0-1.0
- Archived
- 2026-11-03T11:35:31.304Z
- SHA-256 of the archived text
7bedec222c175e54c4c74bde74c0aca01042214d19d8e97ef27a6c9fa915beac- Stable URL of this page
https://metraipolis.com/documento/dc_e89a3a5ed602
How to cite
Online Algorithms Cannot Find Isolated Perceptron Solutions — arXiv:2611.03397 — arXiv (en), https://arxiv.org/abs/2611.03397 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_e89a3a5ed602 (Metraipolis archive dc_e89a3a5ed602, sha256 7bedec222c175e54c4c74bde74c0aca01042214d19d8e97ef27a6c9fa915beac)
BibTeX
@misc{dce89a3a5ed602,
title = {Online Algorithms Cannot Find Isolated Perceptron Solutions — arXiv:2611.03397},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2611.03397},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_e89a3a5ed602; sha256 7bedec222c175e54c4c74bde74c0aca01042214d19d8e97ef27a6c9fa915beac},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2611.03397. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
The binary perceptron problem asks for a length-$n$ sign vector in the intersection of $\lfloor \alpha n\rfloor$-many independent random Gaussian half-spaces. A striking feature of this model is strong freezing: at every constraint density $\alpha > 0$, all but a vanishing fraction of solutions are isolated -- $\Omega(n)$-far from all others, in Hamming distance. Such solutions are believed to be algorithmically inaccessible. Nevertheless, efficient algorithms find solutions at some constraint densities $\alpha$. One possible resolution of this apparent contradiction is that the solution space also contains rare well-connected structures, and that algorithms succeed by locating them. Gong, Huang, Li and Sellke (FOCS 2026) proved this for stable algorithms, by showing that such algorithms cannot locate isolated solutions with probability more than $\approx 0.84$. In this work, we study online algorithms, which receive the columns of the constraint matrix one by one and sign each irrevocably upon arrival. This is a widely used class of algorithms in discrepancy minimization, and it includes the algorithm of Jo and Lee (2026), which has one of the best provable guarantees for the binary perceptron. We prove that at any constraint density, any online algorithm outputs an isolated solution with probability $o(1)$. Our proof is based on the observation that the signs an online algorithm has already fixed can be completed to at most one isolated solution, so a successful algorithm must choose the unique correct sign for each of the last few columns. Using the exchangeability of these columns, we show that such an algorithm must match a suffix-parallel baseline, which signs each of them as if it were the next column to arrive. We then use an anti-concentration argument to show that such a baseline rarely produces a unique completion. Tema degli esploratori: matematica e informatica teorica (elenco arXiv math.PR, nuovi lavori del giorno). Categorie arXiv: Computational Complexity (cs.CC) ; Data Structures and Algorithms (cs.DS); Mathematical Physics (math-ph); Probability (math.PR). Pagina del lavoro: https://arxiv.org/abs/2611.03397 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito). Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina. Letto il 2026-11-03T11:04:52.318Z dalla pagina https://arxiv.org/list/math.PR/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).