2021/10/09 by Zhao Song, Shuo Yang, Song, Zhao +3
Computer Science · Engineering · #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Neural Networks and Applications #Sparse and Compressive Sensing Techniques #Stochastic Gradient Optimization Techniques
paper · pdf · doi:10.48550/arxiv.2110.04622
openalex publication_date 2021/10/09 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Deep neural networks have achieved impressive performance in many areas. Designing a fast and provable method for training neural networks is a fundamental question in machine learning. The classical training method requires paying Ω(mnd) cost for both forward computation and backward computation, where m is the width of the neural network, and we are given n training points in d-dimensional space. In this paper, we propose two novel preprocessing ideas to bypass this Ω(mnd) barrier: \bullet First, by preprocessing the initial weights of the neural networks, we can train the neural network in \widetildeO(m1-Θ(1/d) n d) cost per iteration. \bullet Second, by preprocessing the input data points, we can train the neural network in \widetildeO (m4/5 nd ) cost per iteration. From the technical perspective, our result is a sophisticated combination of tools in different fields, greedy-type convergence analysis in optimization, sparsity observation in practical work, high-dimensional geometric search in data structure, concentration and anti-concentration in probability. Our results also provide theoretical insights for a large number of previously established fast training methods. In addition, our classical algorithm can be generalized to the Quantum computation model. Interestingly, we can get a similar sublinear cost per iteration but avoid preprocessing initial weights or input data points.