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

Jonathan Niles-Weed; Ilias Zadik

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

Jonathan Niles-Weed, Ilias Zadik

Mathematics

Research output: Contribution to journal › Conference article › peer-review

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.

Original language	English (US)
Pages (from-to)	3546-3547
Number of pages	2
Journal	Proceedings of Machine Learning Research
Volume	134
State	Published - 2021
Event	34th Conference on Learning Theory, COLT 2021 - Boulder, United States Duration: Aug 15 2021 → Aug 19 2021

Keywords

Phase transitions
all-or-nothing
group testing
perceptron
teacher-student

ASJC Scopus subject areas

Artificial Intelligence
Software
Control and Systems Engineering
Statistics and Probability

Cite this

@article{e3b158e732954d77adece71d777c9987,

title = "It was “all” for “nothing”: sharp phase transitions for noiseless discrete channels",

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.",

keywords = "Phase transitions, all-or-nothing, group testing, perceptron, teacher-student",

author = "Jonathan Niles-Weed and Ilias Zadik",

note = "Publisher Copyright: {\textcopyright} 2021 J. Niles-Weed & I. Zadik.; 34th Conference on Learning Theory, COLT 2021 ; Conference date: 15-08-2021 Through 19-08-2021",

year = "2021",

language = "English (US)",

volume = "134",

pages = "3546--3547",

journal = "Proceedings of Machine Learning Research",

issn = "2640-3498",

publisher = "ML Research Press",

}

TY - JOUR

T1 - It was “all” for “nothing”

T2 - 34th Conference on Learning Theory, COLT 2021

AU - Niles-Weed, Jonathan

AU - Zadik, Ilias

PY - 2021

Y1 - 2021

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

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

KW - Phase transitions

KW - all-or-nothing

KW - group testing

KW - perceptron

KW - teacher-student

UR - http://www.scopus.com/inward/record.url?scp=85131747849&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85131747849&partnerID=8YFLogxK

M3 - Conference article

AN - SCOPUS:85131747849

SN - 2640-3498

VL - 134

SP - 3546

EP - 3547

JO - Proceedings of Machine Learning Research

JF - Proceedings of Machine Learning Research

Y2 - 15 August 2021 through 19 August 2021

ER -

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

Abstract

Keywords

ASJC Scopus subject areas

Other files and links

Fingerprint

Cite this