# Tractability from overparametrization: The example of the negative perceptron

arXiv: https://arxiv.org/abs/2110.15824 · HTML: https://mlsanity.com/paper/2110.15824/

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- Builds on 5 of its 22 references that are in the map.
- First posted on arXiv 28 Oct 2021.

## Builds on (most cited first, 5 of 5)

- [Reconciling modern machine learning practice and the bias-variance trade-off](https://mlsanity.com/paper/1812.11118/) (2018)
- [Benign Overfitting in Linear Regression](https://mlsanity.com/paper/1906.11300/) (2019)
- [A Geometric Analysis of Phase Retrieval](https://mlsanity.com/paper/1602.06664/) (2016)
- [A modern maximum-likelihood theory for high-dimensional logistic regression](https://mlsanity.com/paper/1803.06964/) (2018)
- [A theory of capacity and sparse neural encoding](https://mlsanity.com/paper/2102.10148/) (2021)

## Built on by (most cited first, 12 of 12)

- [Gaussian Universality of Perceptrons with Random Labels](https://mlsanity.com/paper/2205.13303/) (2022)
- [Typical and atypical solutions in non-convex neural networks with discrete and continuous weights](https://mlsanity.com/paper/2304.13871/) (2023)
- [Fl RDT based ultimate lowering of the negative spherical perceptron capacity](https://mlsanity.com/paper/2312.16531/) (2023)
- [Injectivity of ReLU networks: perspectives from statistical physics](https://mlsanity.com/paper/2302.14112/) (2023)
- [No Free Prune: Information-Theoretic Barriers to Pruning at Initialization](https://mlsanity.com/paper/2402.01089/) (2024)
- [Unraveling Projection Heads in Contrastive Learning: Insights from Expansion and Shrinkage](https://mlsanity.com/paper/2306.03335/) (2023)
- [Exact full-RSB SAT/UNSAT transition in infinitely wide two-layer neural networks](https://mlsanity.com/paper/2410.06717/) (2024)
- [High-dimensional manifold of solutions in neural networks: insights from statistical physics](https://mlsanity.com/paper/2309.09240/) (2023)
- [Implicit bias produces neural scaling laws in learning curves, from perceptrons to deep networks](https://mlsanity.com/paper/2505.13230/) (2025)
- [Pseudo-likelihood produces associative memories able to generalize, even for asymmetric couplings](https://mlsanity.com/paper/2507.05147/) (2025)
- [Factual recall in linear associative memories: sharp asymptotics and mechanistic insights](https://mlsanity.com/paper/2605.10795/) (2026)
- [Language Diffusion Models are Associative Memories Capable of Retrieving Unseen Data](https://mlsanity.com/paper/2604.26841/) (2026)

## Abstract (arXiv)

In the negative perceptron problem we are given n data points (boldsymbol xi,yi), where boldsymbol xi is a d-dimensional vector and yi∈+1,-1 is a binary label. The data are not linearly separable and hence we content ourselves to find a linear classifier with the largest possible negative margin. In other words, we want to find a unit norm vector boldsymbol θ that maximizes mini≤ nyilangle boldsymbol θ,boldsymbol xirangle. This is a non-convex optimization problem (it is equivalent to finding a maximum norm vector in a polytope), and we study its typical properties under two random models for the data. We consider the proportional asymptotics in which n,d→ ∞ with n/d→δ, and prove upper and lower bounds on the maximum margin kappas(δ) or -- equivalently -- on its inverse function δs(kappa). In other words, δs(kappa) is the overparametrization threshold: for n/d≤ δs(kappa)-varepsilon a classifier achieving vanishing training error exists with high probability, while for n/d≥ δs(kappa)+varepsilon it does not. Our bounds on δs(kappa) match to the leading order as kappa→ -∞. We then analyze a linear programming algorithm to find a solution, and characterize the corresponding threshold δlin(kappa). We observe a gap between the interpolation threshold δs(kappa) and the linear programming threshold δlin(kappa), raising the question of the behavior of other algorithms.