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?
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
5
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.
answered Mar 12, 2015 at 22:50
-
$\begingroup$ What is the point of the answer on sparse for the second quoted question? $\endgroup$ Mar 13, 2015 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$ Mar 13, 2015 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$– HariAug 26, 2015 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$ Aug 26, 2015 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$– HariAug 27, 2015 at 9:11