This is possible because the Hessian of a deep net has a matrix polynomial structure that factorizes nicely. The Hessian-inverse-product algorithm that takes advantage of this is similar to running backprop on a dual version of the deep net. It echoes an old idea of Pearlmutter's for computing Hessian-vector products.
Maybe this idea is useful as a preconditioner for stochastic gradient descent?
If so, it would be nice if this were the case, because you could then just use the Woodbury formula to invert H. But I don't think such a decomposition exists. I tried to exhaustively search through all the decompositions of H that involved one dummy variable (of which the above is a special case) and I couldn't find one. I ended up having to introduce two dummy variables instead.
Not quite, it means any submatrix taken from the upper(lower) part of the matrix has some low rank. Like a matrix is {3,4}-semiseperable if any sub matrix taken from the lower triangular part has at most rank 3 and any submatrix taken from the upper triangular part has at most rank 4.
The inverse of an upper bidiagonal matrix is {0,1}-semiseperable.
There are a lot of fast algorithms if you know a matrix is semiseperable.
edit: link https://people.cs.kuleuven.be/~raf.vandebril/homepage/public...
MontyCarloHall•31m ago
Silly question, but if you have some clever way to compute the inverse Hessian, why not go all the way and use it for Newton's method, rather than as a preconditioner for SGD?
rahimiali•17m ago
MontyCarloHall•16m ago
rahimiali•11m ago
probably my nomenclature bias is that i started this project as a way to find new preconditioners on deep nets.