# Provable Advantage of Curriculum Learning on Parity Targets with Mixed Inputs

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

## Key facts

- Cited by 22 papers in the map (data through 14 Oct 2026).
- Builds on 35 of its 50 references that are in the map.
- First posted on arXiv 29 Jun 2023.

## Builds on (most cited first, 30 of 35)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [An Image is Worth 16x16 Words: Transformers for Image Recognition at Scale](https://mlsanity.com/paper/2010.11929/) (2020)
- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [Exploring the Limits of Transfer Learning with a Unified Text-to-Text Transformer](https://mlsanity.com/paper/1910.10683/) (2019)
- [A Mean Field View of the Landscape of Two-Layers Neural Networks](https://mlsanity.com/paper/1804.06561/) (2018)
- [Curriculum Learning for Reinforcement Learning Domains: A Framework and Survey](https://mlsanity.com/paper/2003.04960/) (2020)
- [On The Power of Curriculum Learning in Training Deep Networks](https://mlsanity.com/paper/1904.03626/) (2019)
- [Curriculum Learning: A Survey](https://mlsanity.com/paper/2101.10382/) (2021)
- [Automated Curriculum Learning for Neural Networks](https://mlsanity.com/paper/1704.03003/) (2017)
- [Competence-based Curriculum Learning for Neural Machine Translation](https://mlsanity.com/paper/1903.09848/) (2019)
- [Reverse Curriculum Generation for Reinforcement Learning](https://mlsanity.com/paper/1707.05300/) (2017)
- [Hidden Progress in Deep Learning: SGD Learns Parities Near the Computational Limit](https://mlsanity.com/paper/2207.08799/) (2022)
- [SGD learning on neural networks: leap complexity and saddle-to-saddle dynamics](https://mlsanity.com/paper/2302.11055/) (2023)
- [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)
- [CurriculumNet: Weakly Supervised Learning from Large-Scale Web Images](https://mlsanity.com/paper/1808.01097/) (2018)
- [Online stochastic gradient descent on non-convex losses from high-dimensional inference](https://mlsanity.com/paper/2003.10409/) (2020)
- [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)
- [Webly Supervised Learning of Convolutional Networks](https://mlsanity.com/paper/1505.01554/) (2015)
- [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)
- [Curriculum Learning of Multiple Tasks](https://mlsanity.com/paper/1412.1353/) (2014)
- [Curriculum Learning and Minibatch Bucketing in Neural Machine Translation](https://mlsanity.com/paper/1707.09533/) (2017)
- [An Empirical Exploration of Curriculum Learning for Neural Machine Translation](https://mlsanity.com/paper/1811.00739/) (2018)
- [Quantifying the Benefit of Using Differentiable Learning over Tangent Kernels](https://mlsanity.com/paper/2103.01210/) (2021)
- [Online Stochastic Gradient Descent with Arbitrary Initialization Solves Non-smooth, Non-convex Phase Retrieval](https://mlsanity.com/paper/1910.12837/) (2019)
- [Theory of Curriculum Learning, with Convex Loss Functions](https://mlsanity.com/paper/1812.03472/) (2018)
- [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)

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

- [How Far Can Transformers Reason? The Globality Barrier and Inductive Scratchpad](https://mlsanity.com/paper/2406.06467/) (2024)
- [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)
- [Replaying pre-training data improves fine-tuning](https://mlsanity.com/paper/2603.04964/) (2026)
- [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)
- [Shift is Good: Mismatched Data Mixing Improves Test Performance](https://mlsanity.com/paper/2510.25108/) (2025)
- [Making Hard Problems Easier with Custom Data Distributions and Loss Regularization: A Case Study in Modular Arithmetic](https://mlsanity.com/paper/2410.03569/) (2024)
- [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)
- [Exploring Parity Challenges in Reinforcement Learning through Curriculum Learning with Noisy Labels](https://mlsanity.com/paper/2312.05379/) (2023)
- [A Mechanistic Study of Transformers Training Dynamics](https://mlsanity.com/paper/2410.24050/) (2024)
- [The Benefits of Temporal Correlations: SGD Learns k-Juntas from Random Walks Efficiently](https://mlsanity.com/paper/2605.10237/) (2026)
- [Learning through Internalization](https://mlsanity.com/paper/2606.20937/) (2026)
- [Easing Optimization Paths: a Circuit Perspective](https://mlsanity.com/paper/2501.02362/) (2025)
- [The Power of Power Law: Asymmetry Enables Compositional Reasoning](https://mlsanity.com/paper/2604.22951/) (2026)
- [Learning Large-Scale Modular Addition with an Auxiliary Modulus](https://mlsanity.com/paper/2605.07648/) (2026)
- [Less Data, Faster Training: repeating smaller datasets speeds up learning via sampling biases](https://mlsanity.com/paper/2605.20314/) (2026)
- [The Information Shadow: Measuring Structural Limits on What Language Models Can Learn](https://mlsanity.com/paper/2607.18305/) (2026)

## Abstract (arXiv)

Experimental results have shown that curriculum learning, i.e., presenting simpler examples before more complex ones, can improve the efficiency of learning. Some recent theoretical results also showed that changing the sampling distribution can help neural networks learn parities, with formal results only for large learning rates and one-step arguments. Here we show a separation result in the number of training steps with standard (bounded) learning rates on a common sample distribution: if the data distribution is a mixture of sparse and dense inputs, there exists a regime in which a 2-layer ReLU neural network trained by a curriculum noisy-GD (or SGD) algorithm that uses sparse examples first, can learn parities of sufficiently large degree, while any fully connected neural network of possibly larger width or depth trained by noisy-GD on the unordered samples cannot learn without additional steps. We also provide experimental results supporting the qualitative separation beyond the specific regime of the theoretical results.