Learning Constant-Depth Circuits in Malicious Noise Models

Adam Klivans, Konstantinos Stavropoulos, Arsen Vasilyan
Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:3253-3263, 2025.

Abstract

The seminal work of Linial, Mansour, and Nisan gave a quasipolynomial-time algorithm for learning constant-depth circuits ($\mathsf{AC}^0$) with respect to the uniform distribution on the hypercube. Extending their algorithm to the setting of malicious noise, where both covariates and labels can be adversarially corrupted, has remained open. Here we achieve such a result, inspired by recent work on learning with distribution shift. Our running time essentially matches their algorithm, which is known to be optimal assuming various cryptographic primitives. Our proof uses a simple outlier-removal method combined with Braverman’s theorem for fooling constant-depth circuits. We attain the best possible dependence on the noise rate and succeed in the harshest possible noise model (i.e., contamination or so-called “nasty noise").

Cite this Paper

BibTeX
@InProceedings{pmlr-v291-klivans25a, title = {Learning Constant-Depth Circuits in Malicious Noise Models}, author = {Klivans, Adam and Stavropoulos, Konstantinos and Vasilyan, Arsen}, booktitle = {Proceedings of Thirty Eighth Conference on Learning Theory}, pages = {3253--3263}, year = {2025}, editor = {Haghtalab, Nika and Moitra, Ankur}, volume = {291}, series = {Proceedings of Machine Learning Research}, month = {30 Jun--04 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v291/main/assets/klivans25a/klivans25a.pdf}, url = {https://proceedings.mlr.press/v291/klivans25a.html}, abstract = {The seminal work of Linial, Mansour, and Nisan gave a quasipolynomial-time algorithm for learning constant-depth circuits ($\mathsf{AC}^0$) with respect to the uniform distribution on the hypercube. Extending their algorithm to the setting of malicious noise, where both covariates and labels can be adversarially corrupted, has remained open. Here we achieve such a result, inspired by recent work on learning with distribution shift. Our running time essentially matches their algorithm, which is known to be optimal assuming various cryptographic primitives. Our proof uses a simple outlier-removal method combined with Braverman’s theorem for fooling constant-depth circuits. We attain the best possible dependence on the noise rate and succeed in the harshest possible noise model (i.e., contamination or so-called “nasty noise"). } }
Endnote
%0 Conference Paper %T Learning Constant-Depth Circuits in Malicious Noise Models %A Adam Klivans %A Konstantinos Stavropoulos %A Arsen Vasilyan %B Proceedings of Thirty Eighth Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2025 %E Nika Haghtalab %E Ankur Moitra %F pmlr-v291-klivans25a %I PMLR %P 3253--3263 %U https://proceedings.mlr.press/v291/klivans25a.html %V 291 %X The seminal work of Linial, Mansour, and Nisan gave a quasipolynomial-time algorithm for learning constant-depth circuits ($\mathsf{AC}^0$) with respect to the uniform distribution on the hypercube. Extending their algorithm to the setting of malicious noise, where both covariates and labels can be adversarially corrupted, has remained open. Here we achieve such a result, inspired by recent work on learning with distribution shift. Our running time essentially matches their algorithm, which is known to be optimal assuming various cryptographic primitives. Our proof uses a simple outlier-removal method combined with Braverman’s theorem for fooling constant-depth circuits. We attain the best possible dependence on the noise rate and succeed in the harshest possible noise model (i.e., contamination or so-called “nasty noise").
APA
Klivans, A., Stavropoulos, K. & Vasilyan, A.. (2025). Learning Constant-Depth Circuits in Malicious Noise Models. Proceedings of Thirty Eighth Conference on Learning Theory, in Proceedings of Machine Learning Research 291:3253-3263 Available from https://proceedings.mlr.press/v291/klivans25a.html.

Related Material