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 + n3) 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τ2) respectively, where m = Ω(n4) 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τ2).

Sampling is a fundamental problem in optimization, machine learning and theoretical computer science. A common region of interest for sampling is the polytope, which is defined by a set of linear inequalities. The algorithm that is sampling from polytopes usually requires heavy matrix algebra, including matrix multiplication, matrix inversion and matrix determinant. In this work, we show how to implement the heavy matrix algebra in the area of sampling in nearly linear time for the polytope that has small treewidth. In particular, given a polytope defined by a matrix A ∈ ℝn×dwith treewidth τ, we improve the running time of each iteration for three typical sampling algorithms for polytopes such as Dikin Walk, Soft-Threshold Dikin Walk and Vaidya Walk from O(nd2) to O(nτ2) by exploiting the small treewidth structures of the matrices.