How Neural Networks Extrapolate: From Feedforward to Graph Neural Networks

arxiv:2009.11848

Original source · Paper JSON

Data, training, optimization · 2020-09-24

Cites (0) · Cited by (0)

Complete cleaned Markdown · Source Markdown including bibliography

Read in parts

1. Part 1
2. Part 2
3. Part 3
4. Part 4
5. Part 5
6. Part 6
7. Part 7
8. Part 8
9. Part 9
10. Part 10
11. Part 11

Contents

• How Neural Networks Extrapolate: From Feedforward to Graph Neural Networks
• Abstract
• 1 Introduction
• 1.1 Related work
• 2 Preliminaries
• Definition 1 .
• 3 How Feedforward Neural Networks Extrapolate
• 3.1 Linear Extrapolation Behavior of ReLU MLPs
• Definition 2 .
• Theorem 1 .
• 3.2 When ReLU MLPs Provably Extrapolate Well
• Lemma 1 .
• Theorem 2 .
• 3.3 MLPs with Other Activation Functions
• 4 How Graph Neural Networks Extrapolate
• 4.1 Hypothesis: Linear Algorithmic Alignment Helps Extrapolation
• Definition 3 .
• Hypothesis 1 .
• 4.2 Theoretical and Empirical Support
• Corollary 1 .
• Theorem 3 .
• 5 Connections to Other Out-of-Distribution Settings
• 6 Conclusion
• Acknowledgments
• Appendix A Theoretical Background
• Lemma 2 .
• Lemma 3 .
• Appendix B Proofs
• B.1 Proof of Theorem 1
• B.2 Proof of Lemma 1
• Setup and preparation.
• Constrained optimization in NTK feature space.
• Claim 1 .
• Global optimum via the geometry of training data.
• B.3 Proof of Theorem 2
• Asymptotic convergence of data sets.
• Asymptotic convergence of predictions.
• B.4 Proof of Corollary 1
• B.5 Proof of Theorem 3
• B.6 Proof of Lemma 2
• B.7 Proof of Lemma 3
• Appendix C Experimental Details
• Overview.
• C.1 Learning Simple Non-Linear Functions
• Model and hyperparameter settings.
• Test error and model selection.
• C.2 R-squared for Out-of-distribution Directions
• Definition.
• Datasets and models.
• Computation.
• Results.
• C.3 Learning Linear Functions
• Model and hyperparameter settings.
• Exact computation with neural tangent kernel
• C.4 MLPs with cosine, quadratic, and tanh Activation
• Dataset details.
• Model and hyperparameter settings.
• C.5 Max Degree
• Model and hyperparameter settings.
• Test error and model selection.
• C.6 Shortest Path
• Model and hyperparameter settings.
• C.7 N-Body Problem
• Dataset details.
• Model and hyperparameter settings.
• Appendix D Visualization and Additional Experimental Results
• D.1 Visualization Results
• D.2 Extra Experimental Results
• Instructions for reporting errors