mlsanityData to 7 Oct 2026

Provable Advantage of Curriculum Learning on Parity Targets with Mixed Inputs

arXiv 2306.16921 ↗First posted 29 Jun 2023cs.LG stat.MLcited by 22

Not on the map. Why?

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.

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

Builds on

35 of 50 references.

References · 35

  1. 2017Attention Is All You Needcited by 59,932
  2. 2014Adam: A Method for Stochastic Optimizationcited by 36,960
  3. 2020An Image is Worth 16x16 Words: Transformers for Image Recognition at Scalecited by 29,915
  4. 2019PyTorch: An Imperative Style, High-Performance Deep Learning Librarycited by 20,160
  5. 2019Exploring the Limits of Transfer Learning with a Unified Text-to-Text Transformercited by 14,491
  6. 2018A Mean Field View of the Landscape of Two-Layers Neural Networkscited by 463
  7. 2020Curriculum Learning for Reinforcement Learning Domains: A Framework and Surveycited by 350
  8. 2019On The Power of Curriculum Learning in Training Deep Networkscited by 285
  9. 2021Curriculum Learning: A Surveycited by 257
  10. 2017Automated Curriculum Learning for Neural Networkscited by 251
  11. 2019Competence-based Curriculum Learning for Neural Machine Translationcited by 201
  12. 2017Reverse Curriculum Generation for Reinforcement Learningcited by 185
23 more
  1. 2022Hidden Progress in Deep Learning: SGD Learns Parities Near the Computational Limitcited by 184
  2. 2023SGD learning on neural networks: leap complexity and saddle-to-saddle dynamicscited by 142
  3. 2022The merged-staircase property: a necessary and nearly sufficient condition for SGD learning of sparse functions on two-layer neural networkscited by 141
  4. 2018CurriculumNet: Weakly Supervised Learning from Large-Scale Web Imagescited by 126
  5. 2020Online stochastic gradient descent on non-convex losses from high-dimensional inferencecited by 119
  6. 2018Curriculum Learning by Transfer Learning: Theory and Experiments with Deep Networkscited by 113
  7. 2014Learning to Executecited by 105
  8. 2015Webly Supervised Learning of Convolutional Networkscited by 95
  9. 2020Learning Parities with Neural Networkscited by 77
  10. 2023Generalization on the Unseen, Logic Reasoning and Degree Curriculumcited by 73
  11. 2014Curriculum Learning of Multiple Taskscited by 65
  12. 2017Curriculum Learning and Minibatch Bucketing in Neural Machine Translationcited by 63
  13. 2018An Empirical Exploration of Curriculum Learning for Neural Machine Translationcited by 58
  14. 2021Quantifying the Benefit of Using Differentiable Learning over Tangent Kernelscited by 41
  15. 2019Online Stochastic Gradient Descent with Arbitrary Initialization Solves Non-smooth, Non-convex Phase Retrievalcited by 34
  16. 2018Theory of Curriculum Learning, with Convex Loss Functionscited by 33
  17. 2021An Analytical Theory of Curriculum Learning in Teacher-Student Networkscited by 27
  18. 2021On the Power of Differentiable Learning versus PAC and SQ Learningcited by 27
  19. 2020Poly-time universality and limitations of deep learningcited by 23
  20. 2020Computational Separation Between Convolutional and Fully-Connected Networkscited by 19
  21. 2023A Mathematical Model for Curriculum Learning for Paritiescited by 19
  22. 2022On the non-universality of deep learning: quantifying the cost of symmetrycited by 17
  23. 2022An initial alignment between neural network and target is needed for gradient descent to learncited by 12

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2023: 1; 2024: 6; 2025: 7; 2026: 8.

22 papers.

Sort:

By area:

  1. 2024How Far Can Transformers Reason? The Globality Barrier and Inductive Scratchpadcited by 35
  2. 2025RL for Reasoning by Adaptively Revealing Rationalescited by 15
  3. 2024Optimal Protocols for Continual Learning via Statistical Physics and Control Theorycited by 14
  4. 2026Replaying pre-training data improves fine-tuningcited by 12
  5. 2024Tilting the Odds at the Lottery: the Interplay of Overparameterisation and Curricula in Neural Networkscited by 9
  6. 2024How Neural Networks Learn the Support is an Implicit Regularization Effect of SGDcited by 8
  7. 2025Low-dimensional Functions are Efficiently Learnable under Randomly Biased Distributionscited by 8
  8. 2025Shift is Good: Mismatched Data Mixing Improves Test Performancecited by 5
  9. 2024Making Hard Problems Easier with Custom Data Distributions and Loss Regularization: A Case Study in Modular Arithmeticcited by 4
  10. 2025Provable Benefit of Curriculum in Transformer Tree-Reasoning Post-Trainingcited by 4
  11. 2025A statistical physics framework for optimal learningcited by 3
  12. 2026Positive Distribution Shift as a Framework for Understanding Tractable Learningcited by 3
10 more
  1. 2023Exploring Parity Challenges in Reinforcement Learning through Curriculum Learning with Noisy Labelscited by 1
  2. 2024A Mechanistic Study of Transformers Training Dynamicscited by 1
  3. 2025Transformers Provably Learn Sparse XOR with Polylogarithmic Parameterscited by 1
  4. 2026Learning through Internalizationcited by 1
  5. 2025Easing Optimization Paths: a Circuit Perspectivecited by 0
  6. 2026The Power of Power Law: Asymmetry Enables Compositional Reasoningcited by 0
  7. 2026Learning Large-Scale Modular Addition with an Auxiliary Moduluscited by 0
  8. 2026The Benefits of Temporal Correlations: SGD Learns k-Juntas from Random Walks Efficientlycited by 0
  9. 2026Less Data, Faster Training: repeating smaller datasets speeds up learning via sampling biasescited by 0
  10. 2026The Information Shadow: Measuring Structural Limits on What Language Models Can Learncited by 0