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

Computing Higher Order Derivatives of Matrix and Tensor Expressions [pdf]

matrixcalculus.org

Post reply on HN
Print view View original

11–20 of 22 posts

Re: Computing Higher Order Derivatives of Matrix and Tensor Expressions [pdf]

#11

Post by SoerenL »

woggy wrote: post #10
SoerenL wrote: post #5

Earlier quoted context omitted.

As one of the authors: Yes, it is true, 3 orders of magnitude (so about a factor of 1000 on GPUs). But please be careful, this holds only for higher order derivatives (like Hessians, or Jacobians), as stated in the paper and as the title says. For gradients, the speedup is rather limited.

Can you briefly explain what the approach is? I’ve briefly skimmed the paper and I feel like I am missing something. Is it auto diff on the component wise expressions, then somehow figuring out a way to evaluate those expressions using matrices?

That's what is usually done, autodiff on the component wise expression. We don't do it here. Instead, we really compute on the matrix and tensor level and compute derivatives here directly. Let me give you a simple example to illustrate it: Consider the function f(x)=x'Ax. Then, its Hessian is A+A'. This expression is what we compute. And evaluating this expression is orders of magnitude faster than what TF, PyTorch, etc. do, namely autodiff on the components. Hope this helps, if not, please let me know.

Re: Computing Higher Order Derivatives of Matrix and Tensor Expressions [pdf]

#12

Post by p1esk »

SoerenL wrote: post #5
bmc7505 wrote: post #4

Earlier quoted context omitted.

Not 3X. Three orders of magnitude faster. If true, this is indeed, an exciting result. Maybe as exciting as Strassen’s algorithm was for matrix multiplication - this enables a bunch of powerful optimization methods that were previously thought intractable for modern DNNs.

As one of the authors: Yes, it is true, 3 orders of magnitude (so about a factor of 1000 on GPUs). But please be careful, this holds only for higher order derivatives (like Hessians, or Jacobians), as stated in the paper and as the title says. For gradients, the speedup is rather limited.

Wait, isn’t Jacobian is just a bunch of gradients?

Re: Computing Higher Order Derivatives of Matrix and Tensor Expressions [pdf]

#13

Post by goolulusaurs »

SoerenL wrote: post #11
woggy wrote: post #10

Earlier quoted context omitted.

Can you briefly explain what the approach is? I’ve briefly skimmed the paper and I feel like I am missing something. Is it auto diff on the component wise expressions, then somehow figuring out a way to evaluate those expressions using matrices?

That's what is usually done, autodiff on the component wise expression. We don't do it here. Instead, we really compute on the matrix and tensor level and compute derivatives here directly. Let me give you a simple example to illustrate it: Consider the function f(x)=x' A x. Then, its Hessian is A+A'. This expression is what we compute. And evaluating this expression is orders of magnitude faster than what TF, PyTorc…

Do you think this could end up being implemented in TF and Pytorch?

Re: Computing Higher Order Derivatives of Matrix and Tensor Expressions [pdf]

#14

Post by SoerenL »

goolulusaurs wrote: post #13
SoerenL wrote: post #11

Earlier quoted context omitted.

That's what is usually done, autodiff on the component wise expression. We don't do it here. Instead, we really compute on the matrix and tensor level and compute derivatives here directly. Let me give you a simple example to illustrate it: Consider the function f(x)=x' A x. Then, its Hessian is A+A'. This expression is what we compute. And evaluating this expression is orders of magnitude faster than what TF, PyTorc…

Do you think this could end up being implemented in TF and Pytorch?

Not in its current formulation. It uses a different representation of the tensors. However, a new version/algorithm that will be available in a few months can be used in TF and PyTorch.

Re: Computing Higher Order Derivatives of Matrix and Tensor Expressions [pdf]

#15

Post by mjw »

This is very neat. That said the reason these methods haven't received much attention so far is that relatively few people actually need to compute Jacobeans or Hessians directly.

Often only Hessian-vector products or Jacobean-vector products are required, and these can be computed via more standard autodiff techniques, usually a lot more efficiently than if you were to compute the Hessian or Jacobean directly.

Also for models with lots of parameters, the Jacobean and Hessian are usually impractically large to realise in memory (N^2 in the number of parameters).

Nevertheless the symbolic tensor calculus approach is very appealing to me. For one thing it could make it a lot easier to see in a more readable symbolic notation what the gradient computations look like in standard backprop, and could perhaps make it easier to implement powerful symbolic optimizations.

Re: Computing Higher Order Derivatives of Matrix and Tensor Expressions [pdf]

#16

Post by SoerenL »

mjw wrote: post #15

This is very neat. That said the reason these methods haven't received much attention so far is that relatively few people actually need to compute Jacobeans or Hessians directly. Often only Hessian-vector products or Jacobean-vector products are required, and these can be computed via more standard autodiff techniques, usually a lot more efficiently than if you were to compute the Hessian or Jacobean directly. Also…

True, for large-scale problems Hessian-vector products are often the way to go (or completely ignoring second order information). However, computing first an expression for the Hessian symbolically and then taking the product with a vector is still more efficient than using autodiff for Hessian-vector products. It is not in the paper though. But the gain is rather small (just a factor of two or so). But true, only for problems involving up to a few thousand parameters computing Hessians or Jacobians is useful.

Re: Computing Higher Order Derivatives of Matrix and Tensor Expressions [pdf]

#17

Post by bmc7505 »

Would be interesting to explore whether evaluating ∇²f(x) for higher-order SGD methods directly is now feasible for smaller DNNs and whether this leads to faster convergence during training. Most methods like Newton or Gauss-newton were thought intractable for DNNs. Also curious if the angle descent prescribed by quasi-Newton methods is empirically closer to the true 2nd order gradient and whether these approximations are useful in wall-clock time.

Re: Computing Higher Order Derivatives of Matrix and Tensor Expressions [pdf]

#18

Post by jkam »

SoerenL wrote: post #14
goolulusaurs wrote: post #13

Earlier quoted context omitted.

Do you think this could end up being implemented in TF and Pytorch?

Not in its current formulation. It uses a different representation of the tensors. However, a new version/algorithm that will be available in a few months can be used in TF and PyTorch.

Are you referring to the Ricci notation when you are saying it uses a different representation of the tensors? Do you also plan to add non-differentiable functions like relu?

Re: Computing Higher Order Derivatives of Matrix and Tensor Expressions [pdf]

#19

Post by jkam »

bmc7505 wrote: post #17

Would be interesting to explore whether evaluating ∇²f(x) for higher-order SGD methods directly is now feasible for smaller DNNs and whether this leads to faster convergence during training. Most methods like Newton or Gauss-newton were thought intractable for DNNs. Also curious if the angle descent prescribed by quasi-Newton methods is empirically closer to the true 2nd order gradient and whether these approximation…

What kind of work are you referring to when you say higher-order SGD may _now_ be feasible for deep learning? I only find results that try to approximate second order information.
Post reply on HN