State Evolution and Universality of Iterated Linear Programs for the Binary Perceptron
cs.DS, cs.CC, math.PR
Submitted: 2026-11-03
Updated: 2026-11-03
Code: https://github.com/fifalsp/iterated-lp-perceptron
Terminology
Sources
- Free-Probabilistic State Evolution and Random Matrix Discrepancy
- State evolution beyond first-order methods I: Rigorous predictions and finite-sample guarantees
- Phase Retrieval via Linear Programming: Fundamental Limits and Algorithmic Improvements
- The Mean-Field Limit of Online Stochastic Vector Balancing
- Vector Balancing in Polynomial Time
- Stable algorithms cannot reliably find isolated perceptron solutions
- Strong freezing in binary perceptron models
- Some easy optimization problems have the overlap-gap property
- Discrepancy Algorithms for the Binary Perceptron
- Deriving Approximate Message Passing from the Convex Gaussian Min-Max Theorem
- Universality of max-margin classifiers
- Universality of empirical risk minimization
Related papers
- Exploiting Low Scanwidth to Resolve Soft Polytomies
- PHastR: Faster Minimal Perfect Hashing with Rotated Layouts
- Fine-Grained Complexity of Approximating Vector Knapsack: A Faster Algorithm and Equivalence with k-SUM in 2D
- Polynomial-time computation of p-contraction fixed points for even p
- Separations Between Submodular-Like Graph Widths
- Bounded Integer Programming in Almost N 2d Time