Online Algorithms Cannot Find Isolated Perceptron Solutions
Abstract
The binary perceptron problem asks for a length-n sign vector in the intersection of ⌊ αn⌋-many independent random Gaussian half-spaces. A striking feature of this model is strong freezing: at every constraint density α> 0, all but a vanishing fraction of solutions are isolated -- Ω(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 α. 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 ≈ 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.
Related
- Poisson Exchange Beyond Submodularity: Effective Approximation Algorithms for Offline and Online Subset Selection over Matroids
- Topping's conjecture for solutions of harmonic map flow with isolated bubbles
- High-Probability Nash Regret for Decentralized Learning in Markov α-Potential Games: Episodic and Fully Online Asynchronous Algorithms with Applications to Markov Congestion Games
- Stable and Online Algorithms for Random Matrix Discrepancy
- Isolated singularities of solutions to the Yamabe equation in higher dimensions I
BibTeX
@misc{li2026online,
title = {{Online Algorithms Cannot Find Isolated Perceptron Solutions}},
author = {Shuangping Li and Gabe Schoenbach},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2611.03397},
eprint = {2611.03397},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2611.03397},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Online Algorithms Cannot Find Isolated Perceptron Solutions
AU - Shuangping Li
AU - Gabe Schoenbach
PY - 2026
DA - 2026/11/02
PB - arXiv
DO - 10.48550/arxiv.2611.03397
UR - https://arxiv.org/abs/2611.03397
AB - The binary perceptron problem asks for a length-n sign vector in the intersection of ⌊ αn⌋-many independent random Gaussian half-spaces. A striking feature of this model is strong freezing: at every constraint density α> 0, all but a vanishing fraction of solutions are isolated -- Ω(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 α. 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 ≈ 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.
ER -