6
$\begingroup$

Hessian free iterative optimization techniques like Newton-CG, do not explicitly compute the Hessian but instead approximate the product of the Hessian with a vector through finite difference. The approximation error is $\mathcal{O}(\varepsilon)$, where $\varepsilon$ is the parameter in the finite difference calculation. It will be good to know how this approximation affects the number of CG iterations compared to having the complete Hessian? Are there theoretical/empirical understandings about this? Can the product of a more sparse Hessian with a vector be better approximated with finite difference?

$\endgroup$
6
$\begingroup$

The approximation error is $\mathcal{O}(\varepsilon)$, where $\varepsilon$ is the parameter in the finite difference calculation. It will be good to know how this approximation affects the number of CG iterations compared to having the complete Hessian? Are there theoretical/empirical understandings about this?

Yes. In short, there are problems where CG iterations will fail on a finite-difference approximation of the Hessian, but succeed when given an analytical Hessian. These situations tend to occur when the analytical Hessian is ill-conditioned; then the finite-difference Hessian tends to be even more so. The finite-difference Hessian is derived from the Jacobian of the objective function and the Jacobian of the constraints; attempting to calculate these Jacobians via finite-differences is likely to lead to catastrophic loss of precision, since you're apt to lose at least half of your digits of precision every time you take finite differences. There's a detailed discussion with references in Jacobian-free Newton-Krylov methods: a survey of approaches and applications.

Can the product of a sparse Hessian with a vector be better approximated with finite difference?

Yes. If your function is analytic, and you're willing to use intrusive approaches that modify your code base, you could use complex-step differentiation. Basically, you have to rewrite your functions to take complex-valued arguments, and then you can use complex step differentiation to calculate derivatives with much less error.

$\endgroup$
  • $\begingroup$ What is the point of the answer on sparse for the second quoted question? $\endgroup$ – Hui Zhang Mar 13 '15 at 18:49
  • $\begingroup$ I think the OP wants to use finite-differences in a matrix-free JFNK-type approach, but is concerned about the error? If complex step differentiation works for scalars, it should work for a matrix-vector product. $\endgroup$ – Geoff Oxberry Mar 13 '15 at 19:39
  • $\begingroup$ @GeoffOxberry I suppose complex-step differentiation can also be affected by an ill-conditioned Hessian. I am noticing that effect in my experiments. What are your thoughts on this? $\endgroup$ – haripkannan Aug 26 '15 at 8:37
  • $\begingroup$ If the analytical Hessian is ill-conditioned, this can hamper the convergence rate of iterative linear solvers like CG. In that case, you would be advised to either use a preconditioner in conjunction with your iterative solver or to use direct methods, if you have access to the Hessian matrix. $\endgroup$ – Geoff Oxberry Aug 26 '15 at 8:53
  • $\begingroup$ @GeoffOxberry The accuracy of complex step differentiation is reducing if the analytical Hessian is ill-conditioned. Maybe, I can try complex step differentiation with the transformed gradient and see whether I get accurate matrix vector products but this will involve computing the transformed gradient. $\endgroup$ – haripkannan Aug 27 '15 at 9:11

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.