Timezone: »
Poster
A Convergence Analysis of Gradient Descent on Graph Neural Networks
Pranjal Awasthi · Abhimanyu Das · Sreenivas Gollapudi
Graph Neural Networks~(GNNs) are a powerful class of architectures for solving learning problems on graphs. While many variants of GNNs have been proposed in the literature and have achieved strong empirical performance, their theoretical properties are less well understood. In this work we study the convergence properties of the gradient descent algorithm when used to train GNNs. In particular, we consider the realizable setting where the data is generated from a network with unknown weights and our goal is to study conditions under which gradient descent on a GNN architecture can recover near optimal solutions. While such analysis has been performed in recent years for other architectures such as fully connected feedforward networks, the message passing nature of the updates in a GNN poses a new challenge in understanding the nature of the gradient descent updates. We take a step towards overcoming this by proving that for the case of deep linear GNNs gradient descent provably recovers solutions up to error $\epsilon$ in $O(\text{log}(1/\epsilon))$ iterations, under natural assumptions on the data distribution. Furthermore, for the case of oneround GNNs with ReLU activations, we show that gradient descent provably recovers solutions up to error $\epsilon$ in $O(\frac{1}{\epsilon^2} \log(\frac{1}{\epsilon}))$ iterations.
Author Information
Pranjal Awasthi (Google)
Abhimanyu Das (University of Southern California)
Sreenivas Gollapudi (Google Research)
More from the Same Authors

2021 Spotlight: On the Existence of The Adversarial Bayes Classifier »
Pranjal Awasthi · Natalie Frank · Mehryar Mohri 
2021 Spotlight: Calibration and Consistency of Adversarial Surrogate Losses »
Pranjal Awasthi · Natalie Frank · Anqi Mao · Mehryar Mohri · Yutao Zhong 
2022 : A Theory of Learning with Competing Objectives and User Feedback »
Pranjal Awasthi · Corinna Cortes · Yishay Mansour · Mehryar Mohri 
2022 : Theory and Algorithm for Batch Distribution Drift Problems »
Pranjal Awasthi · Corinna Cortes · Christopher Mohri 
2022 : A Theory of Learning with Competing Objectives and User Feedback »
Pranjal Awasthi · Corinna Cortes · Yishay Mansour · Mehryar Mohri 
2022 : "I pick you choose": Joint humanalgorithm decision making in multiarmed bandits »
Kate Donahue · Sreenivas Gollapudi · Kostas Kollias 
2022 : A Theory of Learning with Competing Objectives and User Feedback »
Pranjal Awasthi · Corinna Cortes · Yishay Mansour · Mehryar Mohri 
2022 Poster: On the Adversarial Robustness of Mixture of Experts »
Joan Puigcerver · Rodolphe Jenatton · Carlos Riquelme · Pranjal Awasthi · Srinadh Bhojanapalli 
2022 Poster: Trimmed Maximum Likelihood Estimation for Robust Generalized Linear Model »
Pranjal Awasthi · Abhimanyu Das · Weihao Kong · Rajat Sen 
2022 Poster: MultiClass $H$Consistency Bounds »
Pranjal Awasthi · Anqi Mao · Mehryar Mohri · Yutao Zhong 
2022 Poster: Semisupervised Active Linear Regression »
Nived Rajaraman · Fnu Devvrit · Pranjal Awasthi 
2021 Poster: On the Existence of The Adversarial Bayes Classifier »
Pranjal Awasthi · Natalie Frank · Mehryar Mohri 
2021 Poster: Efficient Algorithms for Learning Depth2 Neural Networks with General ReLU Activations »
Pranjal Awasthi · Alex Tang · Aravindan Vijayaraghavan 
2021 Poster: Contextual Recommendations and LowRegret CuttingPlane Algorithms »
Sreenivas Gollapudi · Guru Guruganesh · Kostas Kollias · Pasin Manurangsi · Renato Leme · Jon Schneider 
2021 Poster: Neural Active Learning with Performance Guarantees »
Zhilei Wang · Pranjal Awasthi · Christoph Dann · Ayush Sekhari · Claudio Gentile 
2021 Poster: Calibration and Consistency of Adversarial Surrogate Losses »
Pranjal Awasthi · Natalie Frank · Anqi Mao · Mehryar Mohri · Yutao Zhong 
2020 Poster: Adaptive Probing Policies for Shortest Path Routing »
Aditya Bhaskara · Sreenivas Gollapudi · Kostas Kollias · Kamesh Munagala