  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.
