Tractability from overparametrization: the example of the negative perceptron

DOI10.1007/S00440-023-01248-YMaRDI QIDQ6193766zbMATH OpenWikidataFDO

Authors

Publication date 19 March 2024

Published in Zeitschrift für Wahrscheinlichkeitstheorie und Verwandte Gebiete (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2110.15824

Mathematics Subject Classification ID

Artificial neural networks and deep learning (68T07) Disordered systems (random Ising models, random Schrödinger operators, etc.) in equilibrium statistical mechanics (82B44) Linear programming (90C05)

Abstract: In the negative perceptron problem we are given $n$ data points $$, where $$ 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 $$ that maximizes $$. 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,doinfty$ with $n/dodelta$, and prove upper and lower bounds on the maximum margin $kapp{a}_{exts}(delta)$ or -- equivalently -- on its inverse function $delt{a}_{exts}(kappa)$. In other words, $delt{a}_{exts}(kappa)$ is the overparametrization threshold: for $n/dledelt{a}_{exts}(kappa)-varepsilon$ a classifier achieving vanishing training error exists with high probability, while for $n/dgedelt{a}_{exts}(kappa)+varepsilon$ it does not. Our bounds on $delt{a}_{exts}(kappa)$ match to the leading order as $kappao-infty$. We then analyze a linear programming algorithm to find a solution, and characterize the corresponding threshold $delt{a}_{extlin}(kappa)$. We observe a gap between the interpolation threshold $delt{a}_{exts}(kappa)$ and the linear programming threshold $delt{a}_{extlin}(kappa)$, raising the question of the behavior of other algorithms.

Recommendations

• scientific article; zbMATH DE number 7370646
• On the perceptron learning algorithm on data with high precision
• Learning binary perceptrons perfectly efficiently.
• Gradient methods never overfit on separable data
• On the atypical solutions of the symmetric binary perceptron

Cites work

• A geometric analysis of phase retrieval
• A modern maximum-likelihood theory for high-dimensional logistic regression
• A theory of capacity and sparse neural encoding
• An Inequality for Mill's Ratio
• Approximating Mills ratio
• Broken replica symmetry bounds in the mean field spin glass model
• Capacity lower bound for the Ising perceptron
• Deep learning: a statistical viewpoint
• Enumeration of Seven-Argument Threshold Functions
• Fit without fear: remarkable mathematical phenomena of deep learning through the prism of interpolation
• High-dimensional probability. An introduction with applications in data science
• scientific article; zbMATH DE number 1420699 (Why is no real title available?)
• Information, Physics, and Computation
• Inner and outer \(j\)-radii of convex bodies in finite-dimensional normed spaces
• Just interpolate: kernel ``ridgeless regression can generalize
• Large deviations techniques and applications.
• Matrix Completion From a Few Entries
• On quadratic transportation cost inequalities
• On the capabilities of multilayer perceptrons
• On the robustness of minimum norm interpolators and regularized empirical risk minimizers
• Optimization of mean-field spin glasses
• Optimization of the Sherrington--Kirkpatrick Hamiltonian
• Out-of-equilibrium dynamical mean-field equations for the perceptron model
• Phase retrieval via Wirtinger flow: theory and algorithms
• Precise Error Analysis of Regularized <inline-formula> <tex-math notation="LaTeX">$M$ </tex-math> </inline-formula>-Estimators in High Dimensions
• Proof of the satisfiability conjecture for large \(k\)
• Random k‐SAT: Two Moments Suffice to Cross a Sharp Threshold
• Rigorous solution of the Gardner problem
• Some inequalities for Gaussian processes and applications
• Storage capacity in symmetric binary perceptrons
• The free energy in a multi-species Sherrington-Kirkpatrick model
• The implicit bias of gradient descent on separable data
• The landscape of empirical risk for nonconvex losses
• The phase transition for the existence of the maximum likelihood estimate in high-dimensional logistic regression
• The simplest model of jamming
• The threshold for random k-SAT is 2 ^k (ln 2 - O(k))
• Theory of Simple Glasses
• Understanding machine learning. From theory to algorithms
• Walksat Stalls Well Below Satisfiability

Cited in

(4)

• Gradient methods never overfit on separable data
• Dynamical mean field theory for models of confluent tissues and beyond
• Exact full-RSB SAT/UNSAT transition in infinitely wide two-layer neural networks
• Injectivity of ReLU networks: perspectives from statistical physics

This page was built for publication: Tractability from overparametrization: the example of the negative perceptron

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6193766)