Curriculum learning -- seeing training examples in a curated order -- seems to be a requisite for effective learning in animals and humans. Yet, its application in neural networks yields surprisingly alternating results. In this work, we explore the interplay between over-parameterization and the effectiveness of curriculum. In particular, we investigate a question about the necessity of curriculum strategies when the learning model is already able to achieve good generalization by simply discovering a good solution nestled within its complex structure. In an online setting, we provide a theoretical analysis of the learning dynamics of a two-layer network trained on a XOR-like Gaussian mixture. Taking the signal-to-noise ratio in the Gaussian mixture as a proxy of the hardness of the learning examples, we show that a curriculum effect can be traced only when the degree of parametrization of the model -- the number of hidden units -- is barely sufficient to solve the learning problem. In the over-parameterized regime, this effect vanishes as the "lottery-ticket" phenomenon allows perfect learning regardless of the order of the training examples. Empirically, we show similar results in simple experiments in ML benchmarks and with more complex network structures.