An Initial Alignment between Neural Network and Target is Needed for Gradient Descent to Learn

Emmanuel Abbe; Elisabetta Cornacchia; Jan Hazla; Christopher Marquis

ICML 2022spotlight15 citations

An Initial Alignment between Neural Network and Target is Needed for Gradient Descent to Learn

Emmanuel Abbe, Elisabetta Cornacchia, Jan Hazla, Christopher Marquis

Abstract

This paper introduces the notion of “Initial Alignment” (INAL) between a neural network at initialization and a target function. It is proved that if a network and a Boolean target function do not have a noticeable INAL, then noisy gradient descent with normalized i.i.d. initialization will not learn in polynomial time. Thus a certain amount of knowledge about the target (measured by the INAL) is needed in the architecture design. This also provides an answer to an open problem posed in (AS-NeurIPS’20). The results are based on deriving lower-bounds for descent algorithms on symmetric neural networks without explicit knowledge of the target function beyond its INAL.

BibTeX

@InProceedings{pmlr-v162-abbe22a,
  title = 	 {An Initial Alignment between Neural Network and Target is Needed for Gradient Descent to Learn},
  author =       {Abbe, Emmanuel and Cornacchia, Elisabetta and Hazla, Jan and Marquis, Christopher},
  booktitle = 	 {Proceedings of the 39th International Conference on Machine Learning},
  pages = 	 {33--52},
  year = 	 {2022},
  editor = 	 {Chaudhuri, Kamalika and Jegelka, Stefanie and Song, Le and Szepesvari, Csaba and Niu, Gang and Sabato, Sivan},
  volume = 	 {162},
  series = 	 {Proceedings of Machine Learning Research},
  month = 	 {17--23 Jul},
  publisher =    {PMLR},
  pdf = 	 {https://proceedings.mlr.press/v162/abbe22a/abbe22a.pdf},
  url = 	 {https://proceedings.mlr.press/v162/abbe22a.html},
  abstract = 	 {This paper introduces the notion of “Initial Alignment” (INAL) between a neural network at initialization and a target function. It is proved that if a network and a Boolean target function do not have a noticeable INAL, then noisy gradient descent with normalized i.i.d. initialization will not learn in polynomial time. Thus a certain amount of knowledge about the target (measured by the INAL) is needed in the architecture design. This also provides an answer to an open problem posed in (AS-NeurIPS’20). The results are based on deriving lower-bounds for descent algorithms on symmetric neural networks without explicit knowledge of the target function beyond its INAL.}
}