Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Show HN: The Hessian of tall-skinny networks is easy to invert

github.com

Post reply on HN
Print view View original

1–10 of 25 posts

Show HN: The Hessian of tall-skinny networks is easy to invert

#1

Post by rahimiali »

It turns out the inverse of the Hessian of a deep net is easy to apply to a vector. Doing this naively takes cubically many operations in the number of layers (so impractical), but it's possible to do this in time linear in the number of layers (so very practical)!

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?

Show HN: The Hessian of tall-skinny networks is easy to invert
github.com

Re: Show HN: The Hessian of tall-skinny networks is easy to invert

#2

Post by MontyCarloHall »

>If the Hessian-vector product is Hv for some fixed vector v, we're interested in solving Hx=v for x. The hope is to soon use this as a preconditioner to speed up stochastic gradient descent.

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?

Re: Show HN: The Hessian of tall-skinny networks is easy to invert

#5

Post by rahimiali »

MontyCarloHall wrote: post #2

>If the Hessian-vector product is Hv for some fixed vector v, we're interested in solving Hx=v for x. The hope is to soon use this as a preconditioner to speed up stochastic gradient descent. 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?

Good q. The method computes Hessian-inverse on a batch. When people say "Newton's method" they're often thinking H^{-1} g, where both the Hessian and the gradient g are on the full dataset. I thought saying "preconditioner" instead of "Newton's method" would make it clear this is solving H^{-1} g on a batch, not on the full dataset.

Re: Show HN: The Hessian of tall-skinny networks is easy to invert

#6

Post by MontyCarloHall »

rahimiali wrote: post #5
MontyCarloHall wrote: post #2

>If the Hessian-vector product is Hv for some fixed vector v, we're interested in solving Hx=v for x. The hope is to soon use this as a preconditioner to speed up stochastic gradient descent. 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?

Good q. The method computes Hessian-inverse on a batch. When people say "Newton's method" they're often thinking H^{-1} g, where both the Hessian and the gradient g are on the full dataset. I thought saying "preconditioner" instead of "Newton's method" would make it clear this is solving H^{-1} g on a batch, not on the full dataset.

I'd call it "Stochastic Newton's Method" then. :-)

Re: Show HN: The Hessian of tall-skinny networks is easy to invert

#7

Post by rahimiali »

jeffjeffbear wrote: post #4

I haven't looked into it in years, but would the inverse of a block bi-diagonal matrix have some semiseperable structure? Maybe that would be good to look into?

just to be clear, semiseparate in this context means H = D + CC', where D is block diagonal and C is tall & skinny?

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.

Re: Show HN: The Hessian of tall-skinny networks is easy to invert

#8

Post by rahimiali »

MontyCarloHall wrote: post #6
rahimiali wrote: post #5

Earlier quoted context omitted.

Good q. The method computes Hessian-inverse on a batch. When people say "Newton's method" they're often thinking H^{-1} g, where both the Hessian and the gradient g are on the full dataset. I thought saying "preconditioner" instead of "Newton's method" would make it clear this is solving H^{-1} g on a batch, not on the full dataset.

I'd call it "Stochastic Newton's Method" then. :-)

fair. thanks. i'll sleep on it and update the paper if it still sounds right tomorrow.

probably my nomenclature bias is that i started this project as a way to find new preconditioners on deep nets.

Re: Show HN: The Hessian of tall-skinny networks is easy to invert

#9

Post by jeffjeffbear »

rahimiali wrote: post #7
jeffjeffbear wrote: post #4

I haven't looked into it in years, but would the inverse of a block bi-diagonal matrix have some semiseperable structure? Maybe that would be good to look into?

just to be clear, semiseparate in this context means H = D + CC', where D is block diagonal and C is tall & skinny? 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…

> just to be clear, semiseparate in this context means H = D + CC', where D is block diagonal and C is tall & skinny?

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...

Re: Show HN: The Hessian of tall-skinny networks is easy to invert

#10

Post by rahimiali »

jeffjeffbear wrote: post #9
rahimiali wrote: post #7

Earlier quoted context omitted.

just to be clear, semiseparate in this context means H = D + CC', where D is block diagonal and C is tall & skinny? 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…

> just to be clear, semiseparate in this context means H = D + CC', where D is block diagonal and C is tall & skinny? 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 a…

thanks for the explanation! sorry i had misread the AI summary on "semiseparable".

i need to firm my intuition on this first before i can say anything clever, but i agree it's worth thinking about!

Post reply on HN