Provable Advantage of Curriculum Learning on Parity Targets with Mixed Inputs

Summary

This paper presents a theoretical analysis of curriculum learning, in which a neural network first presented with “easier” examples is able to more efficiently learn a target over more “complex” examples. The authors specifically consider the problem of learning $k$-sparse parities over a distribution which is a mixture of the uniform distribution over the hypercube and a biased distribution over the hypercube (the easy examples). The main positive results study a two-layer neural network trained via a layer-wise curriculum version of SGD (Algorithm 1), where first the first layer weights are trained on samples from the biased distribution, and next the second layer weights are trained on samples from the mixture distribution. Theorems 3 shows that this algorithm learns $k$-sparse parities with respect to the mixture distribution in $\tilde O(d)$ steps of SGD. In contrast, the paper presents a lower bound showing that noisy SGD on the mixture distribution alone requires $\Omega(d^{1+\delta})$ timesteps to learn a $k$-sparse parity up to nontrivial error. The proof for the upper bound relies on the martingale plus drift argument to show that the $k$ relevant coordinates have been learned after the first stage, while the lower bound uses similar techniques to proving SQ lower bounds.

Strengths

- The paper is well written. - I skimmed the proofs in the appendix and they appear to be sound. The experiments section demonstrates that the proposed curriculum strategy is effective in settings beyond those considered in the theory. - Curriculum learning is a common procedure in practice, and yet there is limited theoretical understanding of its behavior. The sparse parity problem presented here is an interesting setting to study curriculum learning, with a clear measure of “easier” samples. The results here adequately show that a neural network can obtain an efficiency improvement from first training on these easier samples, which I find to be a very nice result.

Weaknesses

- The novelty of the paper, in comparison to the prior work [CM23], is a bit difficult to discern. It appears that the main difference is that the current paper uses SGD for multiple steps in the first stage and uses the “drift plus martingale” technique for the proof, while [CM23] considers a single large step of GD with large batch size in the first stage and shows that is sufficient for learning the support. However, Theorem 3 here seems very similar to Theorem 3.4 in [CM23]. Also, Theorem 4 still uses the one-step algorithm. Could you please comment further on the novelty of the current paper in comparison to the prior work? - A minor weakness is that the algorithm is a bit restrictive and has some nonstandard modifications. In particular, during the first stage the biases are chosen to be very large ($\Theta(d)$), and then resampled to different deterministic values before the second stage. Next, there is an $\ell_\infty$ projection on the weights during each step of stage 1. Could you please comment on the necessity of these modifications? I think the paper could benefit from additional discussion of these modifications.

Questions

- It appears that in Theorem 3, the algorithm receives far more samples from the biased distribution than the uniform distribution. In particular, during the first stage the algorithm receives $\tilde O(d)$ biased samples, while in the second stage receives $\tilde O(d)$ uniform samples. In contrast, when running SGD on the entire mixture distribution (like for the lower bounds in Theorem 5), the algorithm receives only $\rho$-times as many biased samples as uniform samples. In the regimes where there is a separation, $\rho$ is very small, in which case curriculum SGD is receiving far more samples from $D_\mu$. It thus seems like the success of curriculum SGD is not necessarily due to viewing the “easy” examples first, but rather from having access to far more “easy” examples than in regular SGD. Is my understanding here correct, and can you please comment on this further? I am open to increasing my score after further clarifications on the above point and my concerns in the weaknesses section. - Minor typos: In Algorithm 1, should line 3 be $\frac12 - \frac{\mu}{4}$ instead?

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

Limitations are adequately addressed.

Summary

The authors present a separation result between curriculum learning and standard learning in the number of noisy-(S)GD training steps for a 2-layer ReLU network for case of learning noiseless k-parity. While the precise training algorithm deviates from the common deep learning setup, experiments verify that learning k-parity can benefit from learning sparse inputs before harder dense inputs - mostly in terms of an improved sample complexity.

Strengths

- Theoretical evidence for benefits of curriculum learning. - Additional positive results for the hinge loss. - Bound on sample complexity for the positive case. - The negative result allows for a comparison with the positive one in some settings. - The experimental results suggest a strong difference between curriculum learning and standard learning (yet, not exactly in the theoretical setup so far) in the context of learning a parity function.

Weaknesses

- The analysis is limited to a single and not very general learning problem (learning k-parity). - The analysis makes assumptions that are quite different from practical deep learning setups: 1) Non-standard neural network initialization. 2) Non-standard loss (covariance loss) that penalizes errors on samples with true negative labels higher than errors on truly positive samples. The hinge loss results rely on an uncommon activation function. 3) The hinge loss results are relatively weak as they just state the existence of an initialization etc. that leads to successful training. Essentially, this is not stronger than an expressiveness results, because the initialization could just correspond to the optimal (potentially learned) parameters. 4) No noise in the data. 5) Curriculum learning and dense learning use learning algorithms that are different also in other aspects than just the order of samples. For instance, the batch size is required to be quite large in case of dense learning. Most importantly, the theorem for curriculum learning assumes a much larger proportion of easy examples $\rho$ than the standard learning. This is important because $\rho$ essentially controls how easy the learning problem is. In the experiments, for large enough $\rho$ dense learning seems to perform better than curriculum learning. (Btw, this observation is not explained by the theory.) 6) The learning algorithm is not standard SGD or GD but learns the layers separately. 7) The bias parameters are not trained (and it is left unclear in the main paper how they are initialized). - Mismatch between experimental validation and theory: 1) different loss (l2 in experiments, mostly covariance loss in theory) 2) k = 5 in most experiments, while theory assumes k >=6 for separation result. 3) MLP with four layers instead of 2. Experiments should also validate the theory and not only study fairly unrelated cases where we can make similar observations. The direct validation would be important to understand how relevant the constants in the theoretical results are, for instance. - The theorem statements are hard to understand because they rely on notation that has not been introduced in the main text. (Examples: $\mu^{k-1}$ or $\Delta$ or P.) - The proof techniques do not appear to be very novel but similar to previous work. - Missing information: How is the generalisation accuracy computed? I assume samples were drawn from the mixed data distribution, which depends on $k$ and $\rho$? How many samples were used in the experiments? This is important because it also influences how hard the learning problem is. - The theoretical and experimental results study the performance with respect to a test distribution that depends on the amount of easy versus hard examples. This is suboptimal because it can therefore make no claims about the question what kind of data would benefit learning the actual parity function (on all possible inputs). In contrast, the central question underlying curriculum learning is what kind of data (and which order) is best for learning a task. **Points of minor critique:** - Literature discussion: Given the literature discussion, the study of the specific problem of learning parities in the context of curriculum learning does not seem to be in its infancy, as claimed. Furthermore, [SMS22] does not really make the difficulty level criterion label dependent but dependent on the (irrelevant features). In some sense, the same holds also true for the submitted work, as the definition depends on the negative coordinates that also inform the label. (Yet, this does not change the fact that [SMS22] and the presented work are sufficiently different.) - More elements of the notation could be explained. For instance, Rad could be introduced as Rademacher distribution; Unit as uniform distribution; neural networks could be defined formally earlier, []_A could be defined mathematically, etc. The bias scale was not defined. How are the biases initialized? The size P of a neural network has not been defined precisely. Does it refer to the number of hidden neurons or number of parameters? Weak learning has not been defined/explained. - The set of sparse inputs does not have size $\rho$ on average according to the definition of $X_1$ on page 3 (different from how it is frequently discussed). Also $D_u$ contributes to $X_1$, while $D_{\mu}$ does not always. Later, $d$ is assumed to be large enough that the statement is approximately correct, but that comes a bit late (and is not very precise). - Only even values of $\mu$ have been studied in the experiments. Uneven averages should also be considered. - Not all curves in Figure 2 (middle and right) are visible.

Questions

- To which degree does the performance actually depend on being exposed to the hard samples? Curriculum learning is based on the hypothesis that it is not only beneficial to learn from easy examples early but that learning from hard samples later also boosts the performance. I am aware the the negative result needs $\rho$ to be small. Yet, I suspect that learning only on "easy" examples would already be sufficient to learn a parity function because the easy examples carry all relevant information about the parity function. To analyze this question in more detail, it would be good to 1) make the generalisation accuracy independent of the mixed distribution and test whether the correct target function has been learned; 2) report how the performance changes during training. - Figure 2 (middle) implies a non-monotonous dependence of the accuracy in $\mu$. It would be good to study this in more detail and show a figure with $\mu$ on the x-axis. What could be an explanation? Does it matter whether $d\mu$ is even or uneven? - To which degree are the experimental results dependent on hyperparameter tuning? Where the standard learning and curriculum learning be tuned independently?

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

2 fair

Contribution

3 good

Limitations

The limitations have been pointed out under weaknesses and were mostly discussed by the authors. I do not foresee a major or immediate societal impact of this work.

Summary

This paper presents provable results showing the efficiency of curriculum learning for a specific problem setting with training data $(x,y)$, where $x\in(\pm1)^d$ is mixed distributed and $y=\Pi_{j\in\mathcal{S}} x_j\in(\pm1)$. What's more, the study utilizes a 2-layer fully connected network and the noisy-SGD training method

Strengths

1. This paper clearly proves the advantages of curriculum learning over standard learning by analyzing a well-defined problem. 2. Numerous results are also provided and highlight the reduced sample and iteration requirements of curriculum learning.

Weaknesses

Please see Questions.

Questions

1. This paper introduces a highly specific data setting. How can this setting be applied to real-world applications or more general settings? 2. Is there a particular significance to the notion of "sparsity"? I am curious about the evidence if the model was trained on dense data instead of sparse data initially. 3. In Theorem 3, why is $T_1$ independent to the first layer model size $Nd$, while $T_2$ is much larger than the second layer size $N$? Additionally, is the result evaluated using training accuracy? 4. In my opinion, a more appropriate point of comparison for standard training would be: **randomly** sample an equivalent dataset size (as in curriculum learning) to train the first layer, followed by training the second layer using the entire dataset. Since the first layer contains significantly more parameters, standard training might introduce overfitting due to the layer-wise training method rather than curriculum learning.

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

1: Your assessment is an educated guess. The submission is not in your area or the submission was difficult to understand. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

Yes

Summary

This paper studies the impact of curriculum learning for the family of parity functions. Compared to previous work, in which their settings have been distanced from a realistic setting, e.g., considering a non-common activation function with a particular initialization, or a non bounded learning rate, this paper solves all of those issues, although still in special case of covariance loss. They have been successful to show how the order of samples given to the model will effect the sample complexity, both in theory and experiments. Besides, to the downsides of the standard SGD algorithm that samples are completely shuffled, they have provided quite tight upper bounds for the final accuracy of a general fully connected neural network with limited total size, when assuming the procedure is noisy to make it resemble SQ-learning setting and use similar proofs.

Strengths

1- Authors' suggested setting has been closest to reality so far. Unlike previous work they use a bounded learning rate throughout the training process, whereas the former algorithm had proceeded by using only one step of sgd with a learning rate that can get arbitrarily large. 2- The combination of a lower bound for test accuracy when using curriculum learning (giving correlated samples at first so that it approximately learns the support) and an upper bound in case of standard random batch sgd, illustrates advantages of the proposed algorithm. 3. Experiments are in fully agreement with results of theories, and they have implemented various settings for this: Comparison on number of samples, dependence on training steps, and different parameters.

Weaknesses

1- Improvements over previous work is not very conspicuous. Essentially there is no new point in the paper but having former arguments in a more rigorous manner. 2- Additionally, they don't give any assuring bounds besides two layer neural network, which is the exact model their reference work has considered. 3- There are many non-free hyper parameters in their training process. Having assumed that the number of training steps for the first part of algorithm (T_1) depends on parity size is questionable. This can be the reason why previous work assumed only one step of SGD on sparse data. 4- When attempting to come up with similar bounds besides the covariance loss, which is not common between experimentalists, they only consider hinge loss. And this causes their advantage over previous work to disappear because learning rates gets unbounded.

Questions

1 - Would you please make a clarification on new points of your paper? It seems like your reference(CM23) has covered most of the claims as in your paper. 2- I suggest to include other tasks that curriculum would come to be handful in your work.

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

5: You are absolutely certain about your assessment. You are very familiar with the related work and checked the math/other details carefully.

Soundness

3 good

Presentation

4 excellent

Contribution

2 fair

Limitations

The main limit of this paper is not to go anywhere else other than the parity task. Many papers have investigated the same object before.

Response to Authors

Thank you to the authors for their response. The contribution of the current submission in comparison to [CM23] is now more clear to me, and so I have increased my score accordingly. I think it is still interesting to understand whether the benefit of curriculum learning shown here is really due to the order of the examples, or rather just having access to more easy samples.

Score update

I thank the authors for the clarifications and pointing me to additional experiments in the appendix. I have increased by score to a weak accept in response.