Tractability from overparametrization: The example of the negative perceptron

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.