A Mathematical Model for Curriculum Learning for Parities

Elisabetta Cornacchia, Elchanan Mossel
Proceedings of the 40th International Conference on Machine Learning, PMLR 202:6402-6423, 2023.

Abstract

Curriculum learning (CL)- training using samples that are generated and presented in a meaningful order - was introduced in the machine learning context around a decade ago. While CL has been extensively used and analysed empirically, there has been very little mathematical justification for its advantages. We introduce a CL model for learning the class of k-parities on d bits of a binary string with a neural network trained by stochastic gradient descent (SGD). We show that a wise choice of training examples, involving two or more product distributions, allows to reduce significantly the computational cost of learning this class of functions, compared to learning under the uniform distribution. We conduct experiments to support our analysis. Furthermore, we show that for another class of functions - namely the ‘Hamming mixtures’ - CL strategies involving a bounded number of product distributions are not beneficial.

Cite this Paper

BibTeX
@InProceedings{pmlr-v202-cornacchia23a, title = {A Mathematical Model for Curriculum Learning for Parities}, author = {Cornacchia, Elisabetta and Mossel, Elchanan}, booktitle = {Proceedings of the 40th International Conference on Machine Learning}, pages = {6402--6423}, year = {2023}, editor = {Krause, Andreas and Brunskill, Emma and Cho, Kyunghyun and Engelhardt, Barbara and Sabato, Sivan and Scarlett, Jonathan}, volume = {202}, series = {Proceedings of Machine Learning Research}, month = {23--29 Jul}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v202/cornacchia23a/cornacchia23a.pdf}, url = {https://proceedings.mlr.press/v202/cornacchia23a.html}, abstract = {Curriculum learning (CL)- training using samples that are generated and presented in a meaningful order - was introduced in the machine learning context around a decade ago. While CL has been extensively used and analysed empirically, there has been very little mathematical justification for its advantages. We introduce a CL model for learning the class of k-parities on d bits of a binary string with a neural network trained by stochastic gradient descent (SGD). We show that a wise choice of training examples, involving two or more product distributions, allows to reduce significantly the computational cost of learning this class of functions, compared to learning under the uniform distribution. We conduct experiments to support our analysis. Furthermore, we show that for another class of functions - namely the ‘Hamming mixtures’ - CL strategies involving a bounded number of product distributions are not beneficial.} }
Endnote
%0 Conference Paper %T A Mathematical Model for Curriculum Learning for Parities %A Elisabetta Cornacchia %A Elchanan Mossel %B Proceedings of the 40th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2023 %E Andreas Krause %E Emma Brunskill %E Kyunghyun Cho %E Barbara Engelhardt %E Sivan Sabato %E Jonathan Scarlett %F pmlr-v202-cornacchia23a %I PMLR %P 6402--6423 %U https://proceedings.mlr.press/v202/cornacchia23a.html %V 202 %X Curriculum learning (CL)- training using samples that are generated and presented in a meaningful order - was introduced in the machine learning context around a decade ago. While CL has been extensively used and analysed empirically, there has been very little mathematical justification for its advantages. We introduce a CL model for learning the class of k-parities on d bits of a binary string with a neural network trained by stochastic gradient descent (SGD). We show that a wise choice of training examples, involving two or more product distributions, allows to reduce significantly the computational cost of learning this class of functions, compared to learning under the uniform distribution. We conduct experiments to support our analysis. Furthermore, we show that for another class of functions - namely the ‘Hamming mixtures’ - CL strategies involving a bounded number of product distributions are not beneficial.
APA
Cornacchia, E. & Mossel, E.. (2023). A Mathematical Model for Curriculum Learning for Parities. Proceedings of the 40th International Conference on Machine Learning, in Proceedings of Machine Learning Research 202:6402-6423 Available from https://proceedings.mlr.press/v202/cornacchia23a.html.

Related Material