The Exact Online Threshold for the Asymmetric Binary Perceptron

Abstract

Let $G\in\mathbb{R}^{M\times N}$ have independent standard Gaussian entries. For a fixed margin $\kappa\in\mathbb{R}$, the asymmetric binary perceptron asks for $\sigma\in\{\pm1\}^N$ such that $G\sigma/\sqrt{N}\ge\kappa\mathbf{1}_M$. We study the online version of this problem, in which the columns of $G$ arrive sequentially and each sign must be chosen irrevocably before future columns are revealed. We determine the exact threshold $\alpha_{\mathrm{on}}(\kappa)$ for every fixed $\kappa$: for $M/N\to\alpha$ with $\alpha<\alpha_{\mathrm{on}}(\kappa)$, there is a deterministic online algorithm, using $O(MN)$ arithmetic operations and polynomial bit complexity, that succeeds with high probability, while for $\alpha>\alpha_{\mathrm{on}}(\kappa)$, no online algorithm succeeds with high probability. The threshold is characterized by a one-dimensional stochastic control problem for Brownian motion. The main difficulty is to upgrade a single-coordinate Brownian limit to simultaneous feasibility of all $M=\Theta(N)$ constraints, which we do with half-line monotonicity and a short final correction block. At zero margin, we give a computer-assisted proof that $0.32747<\alpha_{\mathrm{on}}(0)<0.36664$. In particular, every density below $0.32747$ is achievable online by such an algorithm, more than tripling the best density previously proved attainable by any polynomial-time algorithm, online or offline (the previous bound was $\alpha\le0.1$, due to Li, Schramm, and Zhou). As $\kappa\to+\infty$, the online threshold agrees to first order with the offline storage capacity. As $\kappa\to-\infty$, it has the same asymptotic scale as the best known offline polynomial-time guarantee, while the storage capacity is larger by a factor of order $\kappa^2$.