Fast Second-order Method for Neural Networks under Small Treewidth Setting

Training neural networks is a fundamental problem in theoretical machine learning. Second-order methods are rarely used in practice due to their high computational cost, even they converge much faster than first-order methods. The state-of-the-art result for the second-order method to train an over-parameterized neural network can run in O(log(1/ϵ)) iterations and each iteration has O(mnd + n<sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">3</sup>) running time, where n represent the number of data points, d is the dimension of the feature space of each data and m is the width of the neural network [Brand, Peng, Song and Weinstein ITCS 2021]. In this work, we further improve the convergence rate and the running time for each iteration to O(loglog(1/ϵ)) and O(mdτ<sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup>) respectively, where m = Ω(n<sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">4</sup>) and τ is the treewidth of the data matrix and usually very small. Our algorithm has a quadratic convergence rate, so it can be regarded as a truly second-order algorithm. To the best of our knowledge, our algorithm is the first to achieve a quadratic convergence rate for neural network training, with a per-iteration running time of O(mdτ<sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup>).