# A Mathematical Model for Curriculum Learning for Parities

arXiv: https://arxiv.org/abs/2301.13833 · HTML: https://mlsanity.com/paper/2301.13833/

## Key facts

- Cited by 19 papers in the map (data through 14 Oct 2026).
- Builds on 24 of its 46 references that are in the map.
- First posted on arXiv 31 Jan 2023.

## Builds on (most cited first, 24 of 24)

- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [An Empirical Study of Example Forgetting during Deep Neural Network Learning](https://mlsanity.com/paper/1812.05159/) (2018)
- [Curriculum Learning: A Survey](https://mlsanity.com/paper/2101.10382/) (2021)
- [Automated Curriculum Learning for Neural Networks](https://mlsanity.com/paper/1704.03003/) (2017)
- [SGD on Neural Networks Learns Functions of Increasing Complexity](https://mlsanity.com/paper/1905.11604/) (2019)
- [Hidden Progress in Deep Learning: SGD Learns Parities Near the Computational Limit](https://mlsanity.com/paper/2207.08799/) (2022)
- [The merged-staircase property: a necessary and nearly sufficient condition for SGD learning of sparse functions on two-layer neural networks](https://mlsanity.com/paper/2202.08658/) (2022)
- [Curriculum Learning by Transfer Learning: Theory and Experiments with Deep Networks](https://mlsanity.com/paper/1802.03796/) (2018)
- [Learning to Execute](https://mlsanity.com/paper/1410.4615/) (2014)
- [Failures of Gradient-Based Deep Learning](https://mlsanity.com/paper/1703.07950/) (2017)
- [Learning Parities with Neural Networks](https://mlsanity.com/paper/2002.07400/) (2020)
- [Generalization on the Unseen, Logic Reasoning and Degree Curriculum](https://mlsanity.com/paper/2301.13105/) (2023)
- [The staircase property: How hierarchical structure can guide deep learning](https://mlsanity.com/paper/2108.10573/) (2021)
- [Neural networks trained with SGD learn distributions of increasing complexity](https://mlsanity.com/paper/2211.11567/) (2022)
- [Quantifying the Benefit of Using Differentiable Learning over Tangent Kernels](https://mlsanity.com/paper/2103.01210/) (2021)
- [Theory of Curriculum Learning, with Convex Loss Functions](https://mlsanity.com/paper/1812.03472/) (2018)
- [Curriculum learning for language modeling](https://mlsanity.com/paper/2108.02170/) (2021)
- [On the Power of Differentiable Learning versus PAC and SQ Learning](https://mlsanity.com/paper/2108.04190/) (2021)
- [An Analytical Theory of Curriculum Learning in Teacher-Student Networks](https://mlsanity.com/paper/2106.08068/) (2021)
- [Computational Separation Between Convolutional and Fully-Connected Networks](https://mlsanity.com/paper/2010.01369/) (2020)
- [Multi-Task Curriculum Transfer Deep Learning of Clothing Attributes](https://mlsanity.com/paper/1610.03670/) (2016)
- [On the non-universality of deep learning: quantifying the cost of symmetry](https://mlsanity.com/paper/2208.03113/) (2022)
- [Curriculum Learning for Multi-Task Classification of Visual Attributes](https://mlsanity.com/paper/1708.08728/) (2017)
- [An initial alignment between neural network and target is needed for gradient descent to learn](https://mlsanity.com/paper/2202.12846/) (2022)

## Built on by (most cited first, 19 of 19)

- [How Far Can Transformers Reason? The Globality Barrier and Inductive Scratchpad](https://mlsanity.com/paper/2406.06467/) (2024)
- [Provable Advantage of Curriculum Learning on Parity Targets with Mixed Inputs](https://mlsanity.com/paper/2306.16921/) (2023)
- [RL for Reasoning by Adaptively Revealing Rationales](https://mlsanity.com/paper/2506.18110/) (2025)
- [Optimal Protocols for Continual Learning via Statistical Physics and Control Theory](https://mlsanity.com/paper/2409.18061/) (2024)
- [Tilting the Odds at the Lottery: the Interplay of Overparameterisation and Curricula in Neural Networks](https://mlsanity.com/paper/2406.01589/) (2024)
- [How Neural Networks Learn the Support is an Implicit Regularization Effect of SGD](https://mlsanity.com/paper/2406.11110/) (2024)
- [Low-dimensional Functions are Efficiently Learnable under Randomly Biased Distributions](https://mlsanity.com/paper/2502.06443/) (2025)
- [Curriculum Learning for LLM Pretraining: An Analysis of Learning Dynamics](https://mlsanity.com/paper/2601.21698/) (2026)
- [Provable Benefit of Curriculum in Transformer Tree-Reasoning Post-Training](https://mlsanity.com/paper/2511.07372/) (2025)
- [Transformers Provably Learn Sparse XOR with Polylogarithmic Parameters](https://mlsanity.com/paper/2502.07553/) (2025)
- [A statistical physics framework for optimal learning](https://mlsanity.com/paper/2507.07907/) (2025)
- [Positive Distribution Shift as a Framework for Understanding Tractable Learning](https://mlsanity.com/paper/2602.08907/) (2026)
- [Deep Networks Learn Deep Hierarchical Models](https://mlsanity.com/paper/2601.00455/) (2026)
- [Exploring Parity Challenges in Reinforcement Learning through Curriculum Learning with Noisy Labels](https://mlsanity.com/paper/2312.05379/) (2023)
- [Statistical curriculum learning: An elimination algorithm achieving an oracle risk](https://mlsanity.com/paper/2402.13366/) (2024)
- [The Benefits of Temporal Correlations: SGD Learns k-Juntas from Random Walks Efficiently](https://mlsanity.com/paper/2605.10237/) (2026)
- [Learning with Shallow Neural Networks on Cluster-Structured Features](https://mlsanity.com/paper/2605.14927/) (2026)
- [Learning through Internalization](https://mlsanity.com/paper/2606.20937/) (2026)
- [The Power of Power Law: Asymmetry Enables Compositional Reasoning](https://mlsanity.com/paper/2604.22951/) (2026)

## Abstract (arXiv)

Curriculum learning (CL) - training using samples that are generated and presented in a meaningful order - was introduced in the machine learning context around a decade ago. While CL has been extensively used and analysed empirically, there has been very little mathematical justification for its advantages. We introduce a CL model for learning the class of k-parities on d bits of a binary string with a neural network trained by stochastic gradient descent (SGD). We show that a wise choice of training examples involving two or more product distributions, allows to reduce significantly the computational cost of learning this class of functions, compared to learning under the uniform distribution. Furthermore, we show that for another class of functions - namely the `Hamming mixtures' - CL strategies involving a bounded number of product distributions are not beneficial.