arXiv preprint ·
State Evolution and Universality of Iterated Linear Programs for the Binary Perceptron
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
The binary perceptron is a random constraint satisfaction problem that asks for a sign vector satisfying a system of random linear inequalities. Its solution space has a strikingly extreme geometry: at every positive constraint density, all but a vanishing fraction of the solutions are isolated. Yet polynomial-time algorithms find solutions at small enough constraint density, which raises the question of how efficient algorithms navigate such a landscape. Linear programming is a natural algorithm to study here, but its analysis has so far been limited to a single round. Li, Schramm, and Zhou (STOC 2025) analyzed one linear program followed by iterative rounding. In this work, we overcome this limitation and give a precise analysis of iterated linear programming for the binary perceptron. (1) For Gaussian matrices and any fixed number of rounds, we characterize the iterated linear programs exactly through a deterministic state-evolution recursion. (2) Adding a final rounding step, we obtain a randomized polynomial-time algorithm for the binary perceptron. Numerical evaluations of the recursion provide evidence that it succeeds at constraint density $α=0.60$ with zero margin, well beyond the range $α\le0.1$ guaranteed by the single-LP analysis and $α\approx0.327$ (Jo and Lee, 2026), the best guarantee so far. (3) We establish universality, showing that the same characterization holds for matrices with i.i.d. entries drawn from any centered, unit-variance subgaussian law. The key idea of our proof is that, although conditioning on earlier rounds makes the matrix non-Gaussian, its conditional law can be computed explicitly and remains close to a Gaussian law, so the convex Gaussian min-max theorem applies in every round. For universality, we compare Gaussian and subgaussian matrices through the Lindeberg principle, using a regularized version of each linear program.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
Near linear mixing of random-cluster Glauber dynamics on random regular graphs
A Bayesian-Geometric Reading of Classical Model-Based Optimal Design
Functional inequalities from the fundamental limits of Bayesian estimation
Glauber Dynamics for Sampling Colorings: Rapid Mixing above $(1+1/\mathrm{e})Δ$ via Hidden Hard-Core Models
Can a self-sustaining chemical network emerge due to just a few catalysts?
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.