  First-order methods such as stochastic gradient descent (SGD) are currently
the standard algorithm for training deep neural networks. Second-order methods,
despite their better convergence rate, are rarely used in practice due to the
prohibitive computational cost in calculating the second-order information. In
this paper, we propose a novel Gram-Gauss-Newton (GGN) algorithm to train deep
neural networks for regression problems with square loss. Our method draws
inspiration from the connection between neural network optimization and kernel
regression of neural tangent kernel (NTK). Different from typical second-order
methods that have heavy computational cost in each iteration, GGN only has
minor overhead compared to first-order methods such as SGD. We also give
theoretical results to show that for sufficiently wide neural networks, the
convergence rate of GGN is \emph{quadratic}. Furthermore, we provide
convergence guarantee for mini-batch GGN algorithm, which is, to our knowledge,
the first convergence result for the mini-batch version of a second-order
method on overparameterized neural networks. Preliminary experiments on
regression tasks demonstrate that for training standard networks, our GGN
algorithm converges much faster and achieves better performance than SGD.
