1
$\begingroup$

I've seen quite a lot of work to do with approximating the Hessian such as the Hessian Vector Product but I'm not entirely sure how knowing the Hessian helps us evaluate the gradient step to take.

Newton's method utilizes the inverse Hessian such that

$$ f(\mathbf{x + \Delta x}) \approx f(\mathbf{x}) + \mathbf{g}^T \mathbf{\Delta x} + \frac{1}{2}\mathbf{\Delta x^T H \Delta x} $$

so if we want to solve for when the gradient is zero,

$$ \frac{d f(\mathbf{x} + \mathbf{\Delta x)}}{d \mathbf{\Delta x}} = \mathbf{g + H \Delta x} $$

$$ 0 = \mathbf{g} + \mathbf{H} \mathbf{\Delta x} $$

then $$ \Delta \mathbf{x} = - \mathbf{H}^{-1} \mathbf{g} $$

where $\mathbf{g}$ is the gradient of $f$ and $\mathbf{H}$ is the Hessian.

but, isn't the main difficulty to do with the amount of computation required to invert the Hessian?

Specifically in the Hessian-Vector Product they use the following trick: $$ {\bf g}({\bf x}+{\bf \Delta x}) \approx {\bf g}({\bf x}) + \mathbf{H}({\bf x}){\bf \Delta x}$$

then for small $r$ $$ {\bf g}({\bf x}+r{\bf v}) \approx {\bf g}({\bf x}) + r \mathbf{H}({\bf x}){\bf v}$$

and this lets them compute $\mathbf{Hv}$ $$\mathbf{H}({\bf x}){\bf v}\approx\frac{{\bf g}({\bf x}+r{\bf v}) - {\bf g}({\bf x})}{r}$$

But... again, if what's important is the inverse Hessian, then what use is $\mathbf{H}v$ assuming it's too computationally expensive to invert?

$\endgroup$
  • $\begingroup$ With reference to your last sentence - note that you aren't inverting $Hv$, you are using it directly. That is the point of the Hessian-vector product; you are avoiding calculating $H^{-1}$. It is an approximation, however. justindomke.wordpress.com/2009/01/17/hessian-vector-products spells this out as well. $\endgroup$ – jbowman Sep 24 '18 at 19:27
  • $\begingroup$ @jbowman Hm, I checked but it doesn't seem to state how it's used? I tried to follow the link to Stochastic Meta Descent but the pdf was forbidden. It's not able to be used directly in Newton's method or SGD is it? $\endgroup$ – tryingtolearn Sep 24 '18 at 19:35
  • 1
    $\begingroup$ No, no, the point is to approximate a Newton step w/o having to calculate the Hessian and inverse thereof, not find a clever way of actually doing a Newton step w/o using the Hessian. This link might help out more: andrew.gibiansky.com/blog/machine-learning/… especially the section on "Hessian-free optimzation." $\endgroup$ – jbowman Sep 24 '18 at 19:44
  • $\begingroup$ @jbowman Sorry, I'm not entirely sure I understand what you mean still. Could you expand on your first sentence? In the blog he just seems to go through the derivation I wrote in my post. How is $v$ chosen and what's it's relationship with the conjugate gradient algorithm that is being discussed in the blog? $\endgroup$ – tryingtolearn Sep 24 '18 at 20:01
  • $\begingroup$ $Hv$ is useful for iterative solvers that don't require explicit resolution of the Hessian but only products with arbitrary vectors. This is because we actually don't need to inverse; that is simply one means to the solution to the linear system. Note CG is one such iterative solver for SPD matrices specifically. $\endgroup$ – deasmhumnha Sep 25 '18 at 2:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.