Before revision:  We show how to speed up the algorithm of [CGH+19], achieving an O( Mn )-time backpropagation algorithm for training (mildly overparametrized) ReLU networks, which is near-linear in the dimension ( Mn ) of the full gradient (Jacobian) matrix.
After revision:  We show how to speed up the algorithm of [CGH+19], achieving an O( Mn )-time backpropagation algorithm for training (mildly overparametrized) ReLU networks, which is near-linear in the dimension ( mn ) of the full gradient (Jacobian) matrix.