We propose a fast second-order method that can be used as a drop-in replacement for current deep learning solvers. Compared to stochastic gradient descent (SGD), it only requires two additional forward-mode automatic differentiation operations per iteration, which has a computational cost comparable to two standard forward passes and is easy to implement. Our method addresses long-standing issues with current second-order solvers, which invert an approximate Hessian matrix every iteration exactly or by conjugate-gradient methods, procedures that are much slower than a SGD step. Instead, we propose to keep a single estimate of the gradient projected by the inverse Hessian matrix, and update it once per iteration with just two passes over the network. This estimate has the same size and is similar to the momentum variable that is commonly used in SGD. No estimate of the Hessian is maintained. We first validate our method, called CURVEBALL, on small problems with known solutions (noisy Rosenbrock function and degenerate 2-layer linear networks), where current deep learning solvers struggle. We then train several large models on CIFAR and ImageNet, including ResNet and VGG-f networks, where we demonstrate faster convergence with no hyperparameter tuning. We also show our optimiser's generality by testing on a large set of randomly-generated architectures.
This paper proposes an approximate second-order method with low computational cost. A common pitfall of second-order methods is the computation (and perhaps inversion) of the Hessian matrix. While this can be avoided by instead relying on Hessian-vector products as done in CG, it typically still requires several iterations. Instead, the authors suggest a simpler approach that relies on one single gradient step and a warm start strategy. The authors points out that the resulting algorithm resembles a momentum method. They also provide some simple convergence proofs on quadratics and benchmark their method to train deep neural networks.
While I find the research direction interesting, the execution is rather clumsy and many details are not sufficiently motivated. Finally, there is a lot of relevant work in the optimization community that is not discussed in this paper, see detailed comments and references below.
1) Method
The derivation of the method is very much driven on a set of heuristics without theoretical guarantees. In order to derive the update of the proposed method, the authors rely on three heuristics:
a) The first is to reuse the previous search direction z as a warm-start. The authors argue that this might be beneficial if If z does not change abruptly. In the early phase, the gradient norm is likely to be large and thus z will change significantly. One might also encounter regions of high curvature where the direction of z might change quickly from one iteration to the next.
The "warm start" at s_{t-1} is also what yields the momentum term, what interpretation can you give to this choice?
b) The second step interleaves the updates of z and w instead of first finding the optimum z. This amounts to just running one iteration of CG but it is rather unclear why one iteration is an appropriate number. It seems one could instead some adaptive strategy where CG with a fixed accuracy. One could potentially see if allowing larger errors at the beginning of the optimization process might still allow for the method to converge. This is for instance commonly done with the batch-size of first-order method. Gradually increasing the batch-size and therefore reducing the error as one gets close to the optimum can still yield to a converging algorithm, see e.g. 
Friedlander, M. P., & Schmidt, M. (2012). Hybrid deterministic-stochastic methods for data fitting. SIAM Journal on Scientific Computing, 34(3), A1380-A1405.
c) The third step consists in replacing CG with gradient descent.
"If CG takes N steps on average, then Algorithm 2 will be slower than SGD by a factor of at least N, which can easily be an order of magnitude".
First, the number of outer iterations may be a lot less for the Hessian-free method than for SGD so this does not seem to be a valid argument. Please comment.
Second, I would like to see a discussion of the convergence rate of solving (12) inexactly with krylov subspace methods. Note that Lanczos yields an accelerated rate while GD does not. So the motivation for switching to GD should be made clearer.
d) The fourth step introduces a factor rho that decays z at each step. I’m not really sure this makes sense even heuristically. The full update of the algorithm developed by the author is:
w_{t+1} = w_t - beta nabla f + (rho I - beta H) (w_t - w_{t-1}).
The momentum term therefore gets weighted by (rho I - beta H). What is the meaning of this term? The -beta H term weights the momentum according to the curvature of the objective function. Given the lack of theoretical support for this idea, I would at least expect a practical reason back up by some empirical evidence that this is a sensible thing to do.
This is especially important given that you claim to decay rho therefore giving more importance to the curvature term.
Finally, why would this be better than simply using CG on a trust-region model? (Recall that Lanczos yields an accelerated linear rate while GD does not).
2) Convergence analysis
a) The analysis is only performed on a quadratic while the author clearly target non-convex functions, this should be made clear in the main text. Also see references below (comment #3) regarding a possible extension to non-convex functions.
b) The authors should check the range of allowed values for alpha and beta. It appears the rate would scale with the square root of the condition number, please confirm, this is an important detail. I also think that the constant is not as good as Heavy-ball on a quadratic (see e.g. http://pages.cs.wisc.edu/~brecht/cs726docs/HeavyBallLinear.pdf), please comment.
c) Sub-sampling of the Hessian and gradients is not discussed at all (but used in the experiments). Please add a discussion and consider extending the proof (again, see references given below).
3) Convergence Heavy-ball
The authors emphasize the similarity of their approach to Heavy-ball. They cite the results of Loizou & Richtarik 2017. Note that they are earlier results for quadratic functions such as 
Lessard, L., Recht, B., & Packard, A. (2016). Analysis and design of optimization algorithms via integral quadratic constraints. SIAM Journal on Optimization, 26(1), 57-95.
Flammarion, N., & Bach, F. (2015, June). From averaging to acceleration, there is only a step-size. In Conference on Learning Theory (pp. 658-695).
The novelty of the bounds derived in Loizou & Richtarik 2017 is that they apply in stochastic settings.
Finally, there are results for non-convex functions such convergence to a stationary point, see
Zavriev, S. K., & Kostyuk, F. V. (1993). Heavy-ball method in nonconvex optimization problems. Computational Mathematics and Modeling, 4(4), 336-341.
Also on page 2, "Momentum GD ... can be shown to have faster convergence than GD". It should be mentioned that this only hold for (strongly) convex functions!
4) Experiments
a) Consider showing the gradient norms. 
b) it looks like the methods have not yet converged in Fig 2 and 3.
c) Second order benchmark:
It would be nice to compare to a method that does not use the GN matrix but the true or subsampled Hessian (like Trust Region/Cubic Regularization) methods given below.
Why is BFGS in Rosenbrock but not in NN plots?
d) "Batch normalization (which is known to improve optimization)" 
This statement requires a reference such as
Towards a Theoretical Understanding of Batch Normalization
Kohler et al… - arXiv preprint arXiv:1805.10694, 2018
5) Related Work
The related work should include Cubic Regularization and Trust Region methods since they are among the most prominent second order algorithms. Consider citing Conn et al. 2000 Trust Region,  Nesterov 2006 Cubic regularization, Cartis et al. 2011 ARC.
Regarding sub-sampling: Kohler&Lucchi 2017: Stochastic Cubic Regularization for non-convex optimization and Xu et al.: Newton-type methods for non-convex optimization under inexact hessian information.
6) More comments
Page 2
Polyak 1964 should be cited  where momentum is discussed.
"Perhaps the simplest algorithm to optimize Eq. 1 is Gradient Descent". This is technically not correct since GD is not a global optimization algorithm. Maybe mention that you try to find a stationary point
rho (Eq. 2) and lambda (Eq. 4) are not defined
Page 4: 
Algorithm 1 and 2 and related equations in the main text: it should be H_hat instead of H.
Background
“Momemtum GD exhibits somewhat better resistance to poor scaling of the objective function”
To be precise the improvement is quadratic for convex functions. Note that Goh might not be the best reference to cite as the article focuses on quadratic function. Consider citing the lecture notes from Nesterov.
Section 2.2
This section is perhaps a bit confusing at first as the authors discuss the general case of a multivalue loss function. Consider moving your last comment to the beginning of the section.
Section 2.3
As a side remark, the work of Dauphin does not rely on the Gauss-Newton approximation but a different PSD matrix, this is probably worth mentioning.
Minor comment: The title is rather bold and not necessarily precise since the stepsize of curveball is not particularly small e.g. in Fig 1.