Tractability from overparametrization: The example of the negative perceptron

In the negative perceptron problem we are given $n$ data points $({\mathit{x}}_i,y_i)$, where ${\mathit{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 $\mathit{\theta }$ that maximizes $\min_{i\le n}y_i\langle {\boldsymbol \theta},{\boldsymbol x}i\rangle$. 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 \mathrm{\infty }$ with $n\mathrm{/}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)-\varepsilon$ a classifier achieving vanishing training error exists with high probability, while for $n/d\ge \delta_{$\text{s}$}(\kappa)+\varepsilon$itdoesnot\mathrm{.}Ourboundson$\delta_{$\text{s}$}(\kappa)$matchtotheleadingorderas$\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.