# Sensitivity of BFGS to the accuracy of the gradient

I am studying how to speed-up the BFGS method using quantum computing techniques.

I have used a method of speeding up the gradient of the function, but it sacrifices the precision value of the gradient. More specifically, the gradient is calculated using $$O(\sqrt{n} / \epsilon)$$ function calls, where $$n$$ is the dimension. $$\epsilon$$ is a precision parameter that assures $$| \tilde \nabla f - \nabla f | < \epsilon$$. So, if it is possible for the error to be strictly lower than $$\frac{1}{\sqrt{n}}$$ (say $$\frac{1}{\sqrt[3]{n}}$$) that would be perfect.

So, my question is, how precise does the gradient need to be in order for BFGS to work properly?

Edit: I have tried to do an analysis myself in the meantime and I have got an error for the k-th iteration supposing all the previous iterations are completely accurate. $$||B_k^{-1} (\tilde{\nabla f} - \nabla f)|| \le \frac{\epsilon}{\lambda_k}$$, where $$B_k$$ is the k-th approximation of the Hessian and $$\lambda_k$$ is the smallest eigenvalue of $$B_k$$.

The only question remains how he smallest eigenvalue of the approximation changes with the number of iterations.

• How are you implementing quantum algorithms? Something like Q#? Aug 21, 2019 at 15:43
• Great question, in my opinion. In a way, that probably is asking for the conditioning of the BFGS. I would be also very interested to see what kind of ideas are there for this piece. Aug 21, 2019 at 16:08
• I am not implementing the quantum algorithm on any language. I am just doing a theoretical analysis of its complexity. Aug 22, 2019 at 14:30
• might be relevant Aug 23, 2019 at 1:42
• Thank you for the link. I have looked at that question, but unfortunately, it assumes no error to the process. But, I believe it shows that if the error is small enough, then convergence is assured. In the meantime, I have tried to get an upper bound of the error after one iteration. Aug 23, 2019 at 13:14

In your case, $$p_k$$ results from applying your inexact BFGS method. As long as you can show that the Wolfe conditions (3.6) are satisfied, you're not consistently orthogonal to the actual gradient (3.12), and the problem is well-behaved (3.13), then the norm of the gradient of the original problem must go to zero for the series (3.14) to converge. Of course, this says nothing about performance, which is tricky to define. Even Newton's method doesn't converge quadratically if you're too far from the optimal solution. Funny enough, you can implement a terrible optimization method by finding a random search direction, flipping it to be a descent direction, and then bound it away being orthogonal to the gradient and it will still converge as long as the above criteria holds. Mostly, that's a way to say globalization fixes even bad algorithms, at least theoretically.