Taekyun Lee

The Exact Online Threshold for the Asymmetric Binary Perceptron

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 sequen...