Tractability from overparametrization: The example of the negative perceptron

Abstract

In the negative perceptron problem we are given $n$ data points $({\mathbf{x}}_i,y_i)$, where ${\mathbf{x}}_i$ is a $d$-dimensional vector and $y_i\in \{+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 \emph{negative} margin. In other words, we want to find a unit norm vector $\mathbf{\theta }$ that maximizes ${\min }_{i\le n}{y}_i⟨\mathbf{\theta },{\mathbf{x}}_i⟩$. 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\to \infty$ with $n/d\to \delta$, and prove upper and lower bounds on the maximum margin ${\kappa }_{\text{s}}(\delta )$ or -- equivalently -- on its inverse function ${\delta }_{\text{s}}(\kappa )$. In other words, ${\delta }_{\text{s}}(\kappa )$ is the overparametrization threshold: for $n/d\le {\delta }_{\text{s}}(\kappa )-\epsilon$ a classifier achieving vanishing training error exists with high probability, while for $n/d\ge {\delta }_{\text{s}}(\kappa )+\epsilon$ it does not. Our bounds on ${\delta }_{\text{s}}(\kappa )$ match to the leading order as $\kappa \to -\infty$. We then analyze a linear programming algorithm to find a solution, and characterize the corresponding threshold ${\delta }_{\text{lin}}(\kappa )$. We observe a gap between the interpolation threshold ${\delta }_{\text{s}}(\kappa )$ and the linear programming threshold ${\delta }_{\text{lin}}(\kappa )$, raising the question of the behavior of other algorithms.

arXiv comment107 pages; 7 pdf figures

References in corpus (17)

• Reconciling modern machine learning practice and the bias-variance trade-off
• Phase Retrieval via Wirtinger Flow: Theory and Algorithms
• Broken Replica Symmetry Bounds in the Mean Field Spin Glass Model
• Benign Overfitting in Linear Regression
• A modern maximum-likelihood theory for high-dimensional logistic regression
• A Geometric Analysis of Phase Retrieval
• Algorithmic barriers from phase transitions
• The simplest model of jamming
• Universality of the SAT-UNSAT (jamming) threshold in non-convex continuous constraint satisfaction problems
• Just Interpolate: Kernel "Ridgeless" Regression Can Generalize
• The free energy in a multi-species Sherrington-Kirkpatrick model
• Out-of-equilibrium dynamical mean-field equations for the perceptron model
• Jamming in multilayer supervised learning models
• Storage capacity in symmetric binary perceptrons
• Critical jammed phase of the linear perceptron
• Walksat stalls well below the satisfiability threshold
• High dimensional optimization under non-convex excluded volume constraints

Cited by in corpus (2)

• Exact full-RSB SAT/UNSAT transition in infinitely wide two-layer neural networks
• Pseudo-likelihood produces associative memories able to generalize, even for asymmetric couplings