Online algorithms rarely find isolated solutions in binary perceptron problems
Online Algorithms Cannot Find Isolated Perceptron Solutions
Computational ComplexityData Structures and Algorithms
Summary
The binary perceptron problem involves finding patterns that fit many constraints, but most solutions are isolated and hard to find. The authors show that online algorithms—which decide answers step-by-step without reconsidering earlier choices—almost never find these isolated solutions. This suggests that such algorithms only find more connected, easier-to-reach solutions. The work helps explain why some solutions appear unreachable by popular methods.
What this means in practice
- •For discrepancy minimization teams: Identify limits of online methods in finding solutions isolated in complex constraint systems to refine algorithm choices for optimization problems.
- •For machine learning engineers: Recognize that stepwise algorithms may fail to reach certain isolated solutions, guiding better design of learning approaches in high-dimensional classification.
A theory result. No direct application yet.
Authors
Shuangping Li, Gabe Schoenbach
Abstract
The binary perceptron problem asks for a length-$n$ sign vector in the intersection of $\lfloor αn\rfloor$-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 $\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.