Metraipolis › archive › dc_489a5faac24c

The Exact Online Threshold for the Asymmetric Binary Perceptron — arXiv:2609.02124

Source
arXiv (en)
Original
https://arxiv.org/abs/2609.02124
License (as archived)
CC0-1.0
Archived
2026-10-17T05:54:21.168Z
SHA-256 of the archived text
8ab14ff63ec9feec719f5eea21e05379daa6fea1f48058f0f916a1d75bc79e26
Stable URL of this page
https://metraipolis.com/documento/dc_489a5faac24c

How to cite

The Exact Online Threshold for the Asymmetric Binary Perceptron — arXiv:2609.02124 — arXiv (en), https://arxiv.org/abs/2609.02124 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_489a5faac24c (Metraipolis archive dc_489a5faac24c, sha256 8ab14ff63ec9feec719f5eea21e05379daa6fea1f48058f0f916a1d75bc79e26)
BibTeX
@misc{dc489a5faac24c,
  title = {The Exact Online Threshold for the Asymmetric Binary Perceptron — arXiv:2609.02124},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.02124},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_489a5faac24c; sha256 8ab14ff63ec9feec719f5eea21e05379daa6fea1f48058f0f916a1d75bc79e26},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.02124. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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

Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-03 in cs.DS).
Categorie arXiv: Data Structures and Algorithms (cs.DS).
Pagina del lavoro: https://arxiv.org/abs/2609.02124 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-17T05:46:54.681Z dalla pagina https://arxiv.org/catchup/cs.DS/2026-09-03?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).