Global Convergence of Adaptive Gradient Methods for An Over-parameterized Neural Network

By Xiaoxia Wu, Simon Shaolei Du, Rachel A. Ward. 2019

68 citations recorded by the source corpus.

Adaptive gradient methods like AdaGrad are widely used in optimizing neural networks. Yet, existing convergence guarantees for adaptive gradient methods require either convexity or smoothness, and, in the smooth setting, only guarantee convergence to a stationary point. We propose an adaptive gradient method and show that for two-layer over-parameterized neural networks -- if the width is sufficiently large (polynomially) -- then the proposed method converges \emph{to the global minimum} in polynomial time, and convergence is robust, \emph{ without the need to fine-tune hyper-parameters such as the step-size schedule and with the level of over-parametrization independent of the training error}. Our analysis indicates in particular that over-parametrization is crucial for the harnessing the full potential of adaptive gradient methods in the setting of neural networks.

Subfields: Artificial Intelligence, Computational Mechanics

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Mechanics

Citations in the corpus

Linear Convergence of Adaptive Stochastic Gradient Descent (2019, methodology): “In particular, for the convergence of AdaGrad-Norm in over-parameterization problem, [26] proved the same convergence rate as ours.”
Fast Convergence of Natural Gradient Descent for Overparameterized Neural Networks (2019, methodology): “Following Du et al. [2018b], Oymak and Soltanolkotabi [2019], Wu et al. [2019], we only optimize the weights of the ﬁrst layer 2 , i.e., θ = w .”
Towards Understanding the Spectral Bias of Deep Learning (2019, methodology): “It is also interesting to extend our result to other training algorithms like Adam, where the analysis in Wu et al. (2019); Zhou et al. (2018) might be implemented with a more careful quantiﬁcation on the projection of residual along diﬀerent directions.”
An Improved Analysis of Training Over-parameterized Deep Neural Networks (2019, methodology): “Note that the dimension of the output is k = 1 in Du et al. (2018b,a); Wu et al. (2019); Oymak and Soltanolkotabi (2019).”