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

Emmanuel Abbe · Elisabetta Cornacchia · Jan Hazla · Christopher Marquis

Hall E #1222

Keywords: [ DL: Theory ] [ T: Learning Theory ] [ T: Deep Learning ]


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.

Chat is not available.