It was “all” for “nothing”: sharp phase transitions for noiseless discrete channels

Jonathan Niles-Weed, Ilias Zadik
Proceedings of Thirty Fourth Conference on Learning Theory, PMLR 134:3546-3547, 2021.

Abstract

We prove a phase transition known as the “all-or-nothing” phenomenon for noiseless discrete channels. This class of models includes the Bernoulli group testing model and the planted Gaussian perceptron model. Previously, the existence of the all-or-nothing phenomenon for such models was only known in a limited range of parameters. Our work extends the results to all signals with sublinear sparsity. Our main technique is to show that for such models, the “all” half of all-or-nothing implies the “nothing” half, so that a proof of “all” can be turned into a proof of “nothing.” Since the “all” half can often be proven by straightforward means, our equivalence gives a powerful and general approach towards establishing the existence of this phenomenon in other contexts.

Cite this Paper

BibTeX
@InProceedings{pmlr-v134-nilesweed21a, title = {It was “all” for “nothing”: sharp phase transitions for noiseless discrete channels}, author = {Niles-Weed, Jonathan and Zadik, Ilias}, booktitle = {Proceedings of Thirty Fourth Conference on Learning Theory}, pages = {3546--3547}, year = {2021}, editor = {Belkin, Mikhail and Kpotufe, Samory}, volume = {134}, series = {Proceedings of Machine Learning Research}, month = {15--19 Aug}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v134/nilesweed21a/nilesweed21a.pdf}, url = {https://proceedings.mlr.press/v134/nilesweed21a.html}, abstract = {We prove a phase transition known as the “all-or-nothing” phenomenon for noiseless discrete channels. This class of models includes the Bernoulli group testing model and the planted Gaussian perceptron model. Previously, the existence of the all-or-nothing phenomenon for such models was only known in a limited range of parameters. Our work extends the results to all signals with sublinear sparsity. Our main technique is to show that for such models, the “all” half of all-or-nothing implies the “nothing” half, so that a proof of “all” can be turned into a proof of “nothing.” Since the “all” half can often be proven by straightforward means, our equivalence gives a powerful and general approach towards establishing the existence of this phenomenon in other contexts.} }
Endnote
%0 Conference Paper %T It was “all” for “nothing”: sharp phase transitions for noiseless discrete channels %A Jonathan Niles-Weed %A Ilias Zadik %B Proceedings of Thirty Fourth Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2021 %E Mikhail Belkin %E Samory Kpotufe %F pmlr-v134-nilesweed21a %I PMLR %P 3546--3547 %U https://proceedings.mlr.press/v134/nilesweed21a.html %V 134 %X We prove a phase transition known as the “all-or-nothing” phenomenon for noiseless discrete channels. This class of models includes the Bernoulli group testing model and the planted Gaussian perceptron model. Previously, the existence of the all-or-nothing phenomenon for such models was only known in a limited range of parameters. Our work extends the results to all signals with sublinear sparsity. Our main technique is to show that for such models, the “all” half of all-or-nothing implies the “nothing” half, so that a proof of “all” can be turned into a proof of “nothing.” Since the “all” half can often be proven by straightforward means, our equivalence gives a powerful and general approach towards establishing the existence of this phenomenon in other contexts.
APA
Niles-Weed, J. & Zadik, I.. (2021). It was “all” for “nothing”: sharp phase transitions for noiseless discrete channels. Proceedings of Thirty Fourth Conference on Learning Theory, in Proceedings of Machine Learning Research 134:3546-3547 Available from https://proceedings.mlr.press/v134/nilesweed21a.html.

Related Material