Data to 7 Oct 2026

Learning Parities with Neural Networks

arXiv 2002.07400 ↗First posted 18 Feb 2020cs.LG stat.MLcited by 77

Not on the map. Why?

Abstract (arXiv)

In recent years we see a rapidly growing line of research which shows learnability of various models via common neural network algorithms. Yet, besides a very few outliers, these results show learnability of models that can be learned using linear methods. Namely, such results show that learning neural-networks with gradient-descent is competitive with learning a linear classifier on top of a data-independent representation of the examples. This leaves much to be desired, as neural networks are far more successful than linear methods. Furthermore, on the more conceptual level, linear models don't seem to capture the "deepness" of deep networks. In this paper we make a step towards showing leanability of models that are inherently non-linear. We show that under certain distributions, sparse parities are learnable via gradient decent on depth-two network. On the other hand, under the same distributions, these parities cannot be learned efficiently by linear methods.

Key facts. Cited by 77 papers in the map (data through 7 Oct 2026). First posted on arXiv 18 Feb 2020.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 11; 2022: 13; 2023: 17; 2024: 10; 2025: 13; 2026: 13.

77 papers.

Sort:

By area:

2022Transformers Learn Shortcuts to Automatacited by 260
2022Hidden Progress in Deep Learning: SGD Learns Parities Near the Computational Limitcited by 184
2022Neural Networks can Learn Representations with Gradient Descentcited by 161
2022High-dimensional Asymptotics of Feature Learning: How One Gradient Step Improves the Representationcited by 146
2023SGD learning on neural networks: leap complexity and saddle-to-saddle dynamicscited by 142
2021Video Super-Resolution Transformercited by 120
2021Quantum machine learning beyond kernel methodscited by 91
2023A Theoretical Understanding of Shallow Vision Transformers: Learning, Generalization, and Sample Complexitycited by 77
2023Generalization on the Unseen, Logic Reasoning and Degree Curriculumcited by 73
2021Classifying high-dimensional Gaussian mixtures: Where kernel methods fail and neural networks succeedcited by 67
2023Auto-Regressive Next-Token Predictors are Universal Learnerscited by 65
2024Why Larger Language Models Do In-context Learning Differently?cited by 44

38 more

2021Quantifying the Benefit of Using Differentiable Learning over Tangent Kernelscited by 41
2023SGD Finds then Tunes Features in Two-Layer Neural Networks with near-Optimal Sample Complexity: A Case Study in the XOR problemcited by 36
2023Patch-level Routing in Mixture-of-Experts is Provably Sample-efficient for Convolutional Neural Networkscited by 35
2024How Do Nonlinear Transformers Learn and Generalize in In-Context Learning?cited by 35
2022Limitations of the NTK for Understanding Generalization in Deep Learningcited by 34
2022Random Feature Amplification: Feature Learning and Generalization in Neural Networkscited by 33
2023Feature emergence via margin maximization: case studies in algebraic taskscited by 33
2022Spectral Evolution and Invariance in Linear-width Neural Networkscited by 30
2024From Sparse Dependence to Sparse Attention: Unveiling How Chain-of-Thought Enhances Transformer Sample Efficiencycited by 28
2021Properties of the After Kernelcited by 27
2021On the Power of Differentiable Learning versus PAC and SQ Learningcited by 27
2021The Eigenlearning Framework: A Conservation Law Perspective on Kernel Regression and Wide Neural Networkscited by 25
2023Provable Advantage of Curriculum Learning on Parity Targets with Mixed Inputscited by 22
2024A Provably Effective Method for Pruning Experts in Fine-tuned Sparse Mixture-of-Expertscited by 21
2021Spectral Analysis of the Neural Tangent Kernel for Deep Residual Networkscited by 20
2022Problem-Dependent Power of Quantum Neural Networks on Multi-Class Classificationcited by 20
2021Towards Understanding Learning in Neural Networks with Linear Teacherscited by 19
2021The Connection Between Approximation, Depth Separation and Learnability in Neural Networkscited by 19
2021Noether: The More Things Change, the More Stay the Samecited by 19
2023A Mathematical Model for Curriculum Learning for Paritiescited by 19
2023Six Lectures on Linearized Neural Networkscited by 19
2023Provable Guarantees for Nonlinear Feature Learning in Three-Layer Neural Networkscited by 18
2023Joint Edge-Model Sparse Learning is Provably Efficient for Graph Neural Networkscited by 16
2023Provable Multi-Task Representation Learning by Two-Layer ReLU Neural Networkscited by 15
2022Identifying good directions to escape the NTK regime and efficiently learn low-degree plus sparse polynomialscited by 13
2022Feature selection with gradient descent on two-layer networks in low-rotation regimescited by 13
2023Pareto Frontiers in Neural Feature Learning: Data, Compute, Width, and Luckcited by 13
2022Intrinsic dimensionality and generalization properties of the R-norm inductive biascited by 5
2024Simulating Weighted Automata over Sequences and Trees with Transformerscited by 4
2024How Does Gradient Descent Learn Features -- A Local Analysis for Regularized Two-Layer Neural Networkscited by 4
2025Unraveling Syntax: Language Modeling and the Substructure of Grammarscited by 4
2025Provable Benefit of Curriculum in Transformer Tree-Reasoning Post-Trainingcited by 4
2022Impartial Games: A Challenge for Reinforcement Learningcited by 3
2023Learning from higher-order statistics, efficiently: hypothesis tests, random features, and neural networkscited by 3
2025LLM Priors for ERM over Programscited by 3
2026Positive Distribution Shift as a Framework for Understanding Tractable Learningcited by 3
2023Most Neural Networks Are Almost Learnablecited by 2
2024Learning with Hidden Factorial Structurecited by 2

50 most cited of 77 All 77 (JSON)