Learning Constant-Depth Circuits in Malicious Noise Models
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").
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Noise-tolerant learnability of shallow quantum circuits from statistics and the cost of quantum pseudorandomness
In this work, we study the learnability of quantum circuits in the near term. We demonstrate the natural robustness of quantum statistical queries for learning quantum processes, motivating their use as a theoretical too…
Quantum-Classical Separations in Shallow-Circuit-Based Learning with and without Noises
We study quantum-classical separations between classical and quantum supervised learning models based on constant depth (i.e., shallow) circuits, in scenarios with and without noises. We construct a classification proble…
Average-Hard Attention Transformers are Constant-Depth Uniform Threshold Circuits
Transformers have emerged as a widely used neural network model for various natural language processing tasks. Previous research explored their relationship with constant-depth threshold circuits, making two assumptions:…
Hard AttentionReconstruction Algorithms for Low-Rank Tensors and Depth-3 Multilinear Circuits
We give new and efficient black-box reconstruction algorithms for some classes of depth-$3$ arithmetic circuits. As a consequence, we obtain the first efficient algorithm for computing the tensor rank and for finding the…
Tensor DecompositionConstant-Depth and Subcubic-Size Threshold Circuits for Matrix Multiplication
Boolean circuits of McCulloch-Pitts threshold gates are a classic model of neural computation studied heavily in the late 20th century as a model of general computation. Recent advances in large-scale neural computing ha…
GPU