Before revision:  Very recently, this computational overhead was mitigated by the works of [ZMG19,CGH+19 , yielding an O( Mn ^2)-time second-order algorithm for training  overparametrized neural networks with M parameters .
After revision:  Very recently, this computational overhead was mitigated by the works of [ZMG19,CGH+19 , yielding an O( Mn ^2)-time second-order algorithm for training two-layer overparametrized neural networks with M parameters .