  We derive a sound positive semi-definite approximation of the Hessian of deep
models for which Hessian-vector products are easily computable. This enables us
to provide an adaptive SGD learning rate strategy based on the minimization of
the local quadratic approximation, which requires just twice the computation of
a single SGD run, but performs comparably with grid search on SGD learning
rates on different model architectures (CNN with and without residual
connections) on classification tasks. We also compare the novel approximation
with the Gauss-Newton approximation.
