%0 Journal Article %1 song2020nonlinear %A Song, Yang %A Meng, Chenlin %A Liao, Renjie %A Ermon, Stefano %D 2020 %K computation non-linear optimization readings sampling %T Nonlinear Equation Solving: A Faster Alternative to Feedforward Computation %U http://arxiv.org/abs/2002.03629 %X Feedforward computations, such as evaluating a neural network or sampling from an autoregressive model, are ubiquitous in machine learning. The sequential nature of feedforward computation, however, requires a strict order of execution and cannot be easily accelerated with parallel computing. To enable parrallelization, we frame the task of feedforward computation as solving a system of nonlinear equations. We then propose to find the solution using a Jacobi or Gauss-Seidel fixed-point iteration method, as well as hybrid methods of both. Crucially, Jacobi updates operate independently on each equation and can be executed in parallel. Our method is guaranteed to give exactly the same values as the original feedforward computation with a reduced (or equal) number of parallel iterations. Experimentally, we demonstrate the effectiveness of our approach in accelerating 1) the evaluation of DenseNets on ImageNet and 2) autoregressive sampling of MADE and PixelCNN. We are able to achieve between 1.2 and 33 speedup factors under various conditions and computation models.

@article{song2020nonlinear, abstract = {Feedforward computations, such as evaluating a neural network or sampling from an autoregressive model, are ubiquitous in machine learning. The sequential nature of feedforward computation, however, requires a strict order of execution and cannot be easily accelerated with parallel computing. To enable parrallelization, we frame the task of feedforward computation as solving a system of nonlinear equations. We then propose to find the solution using a Jacobi or Gauss-Seidel fixed-point iteration method, as well as hybrid methods of both. Crucially, Jacobi updates operate independently on each equation and can be executed in parallel. Our method is guaranteed to give exactly the same values as the original feedforward computation with a reduced (or equal) number of parallel iterations. Experimentally, we demonstrate the effectiveness of our approach in accelerating 1) the evaluation of DenseNets on ImageNet and 2) autoregressive sampling of MADE and PixelCNN. We are able to achieve between 1.2 and 33 speedup factors under various conditions and computation models.}, added-at = {2020-02-13T16:32:36.000+0100}, author = {Song, Yang and Meng, Chenlin and Liao, Renjie and Ermon, Stefano}, biburl = {https://www.bibsonomy.org/bibtex/232e2a2ec74751a953795d1ed656d8445/kirk86}, description = {[2002.03629] Nonlinear Equation Solving: A Faster Alternative to Feedforward Computation}, interhash = {fb19cdcdb95cc4316f2554333f28ebf4}, intrahash = {32e2a2ec74751a953795d1ed656d8445}, keywords = {computation non-linear optimization readings sampling}, note = {cite arxiv:2002.03629}, timestamp = {2020-02-13T16:32:36.000+0100}, title = {Nonlinear Equation Solving: A Faster Alternative to Feedforward Computation}, url = {http://arxiv.org/abs/2002.03629}, year = 2020 }