Tractability from overparametrization: the example of the negative perceptron

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