@tengerye Would the Gauss-Newton matrix work for you? It’s equal to the Hessian for Linear and ReLU networks. For other networks it can be viewed as a positive semidefinite approximation to the Hessian (ie, http://andrew.gibiansky.com/blog/machine-learning/gauss-newton-matrix/ 100)
Generic Hessian is expensive even for a theoretically optimal algorithm while Gauss-Newton is cheap.