Sensitivity of BFGS to the accuracy of the gradient

Question

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.

Answer 1

From a pure convergence point of view, I believe the only thing that's necessary is to satisfy the convergence criteria from a globalization method such as a line-search or trust-region. This is generally required for convergence even if you used the exact gradient when determining your search direction. Meaning, BFGS will not generally converge by itself unless it is also combined with a line search method. As such, your analysis likely needs to focus on Theorem 3.2 from Nocedal and Wright's Numerical Optimization:

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.