5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ How are you implementing quantum algorithms? Something like Q#? $\endgroup$ – Zach Favakeh Aug 21 '19 at 15:43
  • $\begingroup$ 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. $\endgroup$ – Anton Menshov Aug 21 '19 at 16:08
  • $\begingroup$ I am not implementing the quantum algorithm on any language. I am just doing a theoretical analysis of its complexity. $\endgroup$ – Cezar98 Aug 22 '19 at 14:30
  • 1
    $\begingroup$ might be relevant $\endgroup$ – Anton Menshov Aug 23 '19 at 1:42
  • $\begingroup$ 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. $\endgroup$ – Cezar98 Aug 23 '19 at 13:14
1
$\begingroup$

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:

convergence theorem 1 convergence theorem 2 convergence theorem 3 convergence theorem 4

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.

| cite | improve this answer | |
$\endgroup$

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.