Timezone: »

 
Poster
Learning to Reason with Neural Networks: Generalization, Unseen Data and Boolean Measures
Emmanuel Abbe · Samy Bengio · Elisabetta Cornacchia · Jon Kleinberg · Aryo Lotfi · Maithra Raghu · Chiyuan Zhang

Tue Nov 29 09:00 AM -- 11:00 AM (PST) @ Hall J #406
in Poster Session 1 »

This paper considers the Pointer Value Retrieval (PVR) benchmark introduced in [ZRKB21], where a `reasoning' function acts on a string of digits to produce the label. More generally, the paper considers the learning of logical functions with gradient descent (GD) on neural networks. It is first shown that in order to learn logical functions with gradient descent on symmetric neural networks, the generalization error can be lower-bounded in terms of the noise-stability of the target function, supporting a conjecture made in [ZRKB21]. It is then shown that in the distribution shift setting, when the data withholding corresponds to freezing a single feature (referred to as canonical holdout), the generalization error of gradient descent admits a tight characterization in terms of the Boolean influence for several relevant architectures. This is shown on linear models and supported experimentally on other models such as MLPs and Transformers. In particular, this puts forward the hypothesis that for such architectures and for learning logical functions such as PVR functions, GD tends to have an implicit bias towards low-degree representations, which in turn gives the Boolean influence for the generalization error under quadratic loss.

Keywords: Deep Learning · Reasoning · generalization · Distribution Shift · implicit bias · Boolean influence · noise sensitivity

Author Information

Emmanuel Abbe (Swiss Federal Institute of Technology Lausanne)
Samy Bengio (Apple)
Elisabetta Cornacchia (EPFL - EPF Lausanne)
Jon Kleinberg (Cornell University)
Aryo Lotfi (EPFL - EPF Lausanne)
Maithra Raghu (Google Brain)
Chiyuan Zhang (Google Research)

More from the Same Authors