I have a function of many variables (~200-2000) which I am optimizing with some success using L-BFGS. While the function is expensive to evaluate, the gradient can be computed with not much additional effort.

I would like to know if there are any techniques which could allow this optimization to be sped up by parallel evaluation of the function. On this problem, L-BFGS averages ~1.1-1.3 evaluations per iteration, so I think to a good approximation, I can ignore the line search component of the algorithm. From this perspective then, on every iteration, L-BFGS chooses a tentative input evaluates the function and its gradient, updates its estimation of the inverse Hessian and repeats.

I imagine it is possible to enhance this approach by choosing multiple tentative inputs and using the multiple resulting gradients to form a better estimation of the Hessian. I imagine there is diminishing returns of some sort, the point selected by L-BFGS probably has the highest expected information, but surely there is some additional information about the Hessian that one can infer by using more function evaluations per iteration.

Has this type of approach been investigated? I know there are many resources for parallel gradient-free optimization, as well as parallel gradient estimation, but I have not come across anything like this yet.

  • $\begingroup$ Have you considered the alternative of parallelizing the evaluation of the function and gradient? $\endgroup$ – Brian Borchers Sep 1 '16 at 20:44
  • $\begingroup$ Yes, I have done this with a modicum of success. I believe I have saturated the available parallelization at the single function evaluation level and still have idle computational resources which could be put to use evaluating the function multiple times. $\endgroup$ – Phil Reinhold Sep 1 '16 at 20:57
  • 1
    $\begingroup$ In general there's been very little progress in parallel algorithms for nonlinear programming- you can typically parallelize function/gradient evaluations and for large scale problems you might be able to parallelize linear algebra operations, but the inherent sequential nature of the algorithms makes it hard to do more than that. $\endgroup$ – Brian Borchers Sep 2 '16 at 0:32
  • $\begingroup$ Would you give us more information about your function ? 2000 variables is not a very large number, maybe fine grained parallelism (vector instruction sets) could be used to parallelize a single evaluation as suggested in previous comments (but it depends on the function...) $\endgroup$ – BrunoLevy Sep 2 '16 at 11:46
  • 1
    $\begingroup$ I think you want to look into block BFGS methods, e.g., arxiv.org/abs/1609.00318. $\endgroup$ – Christian Clason Sep 3 '16 at 8:32

Your Answer

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

Browse other questions tagged or ask your own question.