Increasing Efficiency of Solve when Interfacing with an External Library

[Adam Hartshorne]

I am trying to increase the efficiency the solve of a particular problem I am working on. A particularly inefficient aspect of the problem relates to the interfacing with an external library. 

As per the instructions detailed in http://ceres-solver.org/interfacing_with_autodiff.html?highlight=external%20function I currently have ComputeDistortionValueAndJacobian type function to query a 3rd party library and return the relevant values / jacobians. Given the way the problem is structured I potentially have 10000s of parameter blocks, and thus for each iteration, there are of 10000s of individual calls to this 3rd party library. The 3rd party library provides the functionality to calculate all the required function values / jacobians of all parameters blocks with a single call and due to specifics of the library this is computationally much more efficient. 

Thus, I wonder if it would be a legitimate approach to do the following (if I use Levenberg-Marquardt with inner iterations off) :

When initializing the problem, all required values from the 3rd party library would be calculated with a single function call to the library and the data stored in a intermediate data structure. Then, rather than ComputeDistortionValueAndJacobian function calling the 3rd party library each time, it instead queries the intermediate data structure. The stored values would then be updated using IterationCallback function, via a new single call to this 3rd party library using the updated parameters in the parameters blocks.

Are there any potential issues with this approach?

[Sameer Agarwal]

Adam,

I understand your pain, but I do not completely understand your solution. Currently the way iterationcallback is structured, it does not know when parameter blocks are updated, so external code has no way of knowing if and when parameter blocks have been updated.

This is something we will have to add to ceres explicitly. This has come up enough number of times, that it is likely time to do something about it. I am open to design suggestions from you and others. 

Sameer

--
You received this message because you are subscribed to the Google Groups "Ceres Solver" group.
To unsubscribe from this group and stop receiving emails from it, send an email to ceres-solver...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/ceres-solver/ca7a1891-0e85-4184-ae60-87df91e3c7ae%40googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Adam Hartshorne]

Would it still not be more efficient, to make one single function call per iteration (even if many of the parameter blocks haven't changed during an iteration and so no update is actually required), than the many individual calls per iteration? The way my external library works, it is incredibly efficient at calculating the required value / jacobians as a whole, as it computes them in parallel and on the GPU. 

Or are you hypothesizing that as the optimization reaches convergence such a large proportion of the parameter blocks are remaining unchanged, and thus there won't be as many individual calls to the external library? Or is there some fundamental issue with the way ceres works that it would cause crashing / incorrect results if I took this approach?

[Keir Mierle]

Hi Adam,

On Wed, Jan 10, 2018 at 6:21 AM, Adam Hartshorne <adam.ha...@gmail.com> wrote:

Would it still not be more efficient, to make one single function call per iteration (even if many of the parameter blocks haven't changed during an iteration and so no update is actually required), than the many individual calls per iteration? 

It depends. The current design of Ceres takes the approach that the user provides small parts of the overall cost function, and leaves evaluation of the overall problem to Ceres. The precondition of the cost functions is that they are pure functions with no side effects; Ceres exploits this in a number of ways:

- Built-in support for parallelization of residual/cost function evaluation, across OpenMP, Intel TBB, and soon C++11 threading (with no work from the user)

- Support for evaluating the cost functions in any order, to exploit data locality

- Support for evaluating some cost functions more than others - e.g. see inner iterations, where subsets of parameters are adjusted and only their dependent cost functions evaluated (not the entire problem)

- Support for evaluating the jacobian or not, independently for each cost function, and for each parameter (e.g. only getting jacobian for some parameters)

There were several motivations behind the design of Ceres, but two key ones were (1) modeling simplicity and (2) solving efficiency. The modeling approach in Ceres makes it flexible, fast, and easy to iterate on your overall cost function without having to stress about the exact sparsity structure of your problem. That's the real secret in Ceres-- enabling users to experiment with different cost structures, while still having (mostly) state of the art solving speed.

However, in some cases this structure doesn't work well since there may be a large amount of shared computation that could be exploited between cost function evaluations. This has come up a few times; we're not opposed to supporting it, but it triggers a fundamental change in the contract between Ceres and Ceres users. That's the reason we haven't added support for this yet.

Other reasons:

- It opens an API can of worms. If we allow the users to provide the jacobians directly, then suddenly we must expose the sparse matrix structures. Currently they are all private in Ceres.

- If we maintain the current API but extend it with e.g. a start/stop iteration call, it adds constraints on the rest of Ceres that we'd have to support going forward.

- It increases the chances that users will trigger issues simply because the API surface will become more complicated.

So, despite the discussion above, we are open to investigate potential APIs to support this use case. Here's some ideas:

Idea #1: EvaluationCallback type

- Have a new "EvaluationCallback" interface like IterationCallback

- This would have methods for start/stop evaluation

- Users would be responsible for bookkeeping -- they would have to map from the pure-function cost functions into any intermediate data required (that would be generated by PrepareEvaluation())

- API change to Ceres is tiny and should be easy to implement (good!)

- This would limit what solvers could be used (e.g. no inner iterations).

- TBD would be whether this would support subsets or not

- Potential API (rough!)

interface EvaluationCallback {

  void PrepareEvaluation()

  void CompleteEvaluation()

  void PrepareEvaluation(vector<ResidualBlock*> blocks_to_evaluate();

}

Idea #2

- Expose the Evaluator interface entirely, as well as sparse matrix types

- Users are 100% responsible for forming the sparse matrix that Ceres will consume directly

- CostFunction interface won't be used at all

- Huge API surface expansion

- Maximal user flexibility

Cheers,

Keir

The way my external library works, it is incredibly efficient at calculating the required value / jacobians as a whole, as it computes them in parallel and on the GPU. 

Or are you hypothesizing that as the optimization reaches convergence such a large proportion of the parameter blocks are remaining unchanged, and thus there won't be as many individual calls to the external library?

Yes, this happens today with inner iterations.

 

On Wednesday, 10 January 2018 12:30:58 UTC, Sameer Agarwal wrote:

To unsubscribe from this group and stop receiving emails from it, send an email to ceres-solver+unsubscribe@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/ceres-solver/73b4f9d4-9e08-461c-b601-cbf3da5e3fbe%40googlegroups.com.

[Adam Hartshorne]

Thanks for the response. My initial thoughts are listed below.

Idea #1

This is much more suited to my current use case, since the value / jacobian data I can get from the 3rd party library is of a form which could easily be dropped into EvaluationCallback type API with minimal extra work. 

On a more general user level, the current design of Ceres, which takes the approach that the user provides small parts of the overall cost function, is very straightforward and simple. It is what attracted me to using Ceres in the first place and has allowed me to quickly prototype different cost structures. In my opinion keeping this consistent across the framework seems the most sensible approach. 

Idea #2

The second suggestion, whereby the CostFunction interface is dropped and the evaluator interface / spare matrix types is exposed, would more than likely lead to very complex bookkeeping for the user. 

Making the user responsible for of all this increases the potential for hard to identify mistakes and would negate the attractiveness of the current simple Ceres design philosophy. Personally, it is not something I would really want to have to do, even if it did open the potential for more flexibility.

In summary, Idea #1 would be my preferred of the two solutions.

Regards,

Adam

Hi Adam,

[Sameer Agarwal]

I am also in favor of proposal #1, but I do not completely agree with/understand the API proposal. Keir since you have already started with it, want to flesh it out?

Sameer

To view this discussion on the web visit https://groups.google.com/d/msgid/ceres-solver/a62eedb1-2188-4dd6-99af-e76e7ea9289f%40googlegroups.com.

[Keir Mierle]

Here's a non-compiling sketch that shows what I'm thinking:

https://ceres-solver-review.googlesource.com/c/ceres-solver/+/11600

To unsubscribe from this group and stop receiving emails from it, send an email to ceres-solver+unsubscribe@googlegroups.com.

To view this discussion on the web visit https://groups.google.com/d/msgid/ceres-solver/a62eedb1-2188-4dd6-99af-e76e7ea9289f%40googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

--

You received this message because you are subscribed to the Google Groups "Ceres Solver" group.

To unsubscribe from this group and stop receiving emails from it, send an email to ceres-solver+unsubscribe@googlegroups.com.

To view this discussion on the web visit https://groups.google.com/d/msgid/ceres-solver/CABqdRUBzRULTo5y%2Bv69xp3wv5ekpDfT0qSKt62q9au7VxdM6cg%40mail.gmail.com.

[Adam Hartshorne]

This suggestion seems great - once this implemented into the API, I will be happy to test it for you using a particular problem I am working on that would benefit greatly from this functionality.

To view this discussion on the web visit https://groups.google.com/d/msgid/ceres-solver/a62eedb1-2188-4dd6-99af-e76e7ea9289f%40googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

--
You received this message because you are subscribed to the Google Groups "Ceres Solver" group.

To unsubscribe from this group and stop receiving emails from it, send an email to ceres-solver...@googlegroups.com.

[Keir Mierle]

Hi Adam,

Glad to hear this would work. Do you have any feedback on the proposed interface before we go implement it? It's easiest to change before the code is written :)

Happy optimizing,

Keir

To unsubscribe from this group and stop receiving emails from it, send an email to ceres-solver+unsubscribe@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/ceres-solver/92803f54-cabe-460f-8b37-45daab587b6b%40googlegroups.com.

[Francesco Callari]

Hi Keir,

Coming late to this party, but I think there is a simpler way to implement #1 that also has the advantage of not locking the client code into a sequential workflow.

Add an API that returns an integer "cookie" that gets zeroed at the beginning of the solve, and incremented by Ceres at the end of each evaluation (i.e. when the CompleteEvaluation of your proposal would be called). Use a conventional value (or just throw up) if user calls it

for non-supported solvers (e.g. inner iterations). Client code may need only keep track of previous cookie value, compare it with current at the beginning of a residual block evaluation, and stub to "special initialization" value upon noticing a change.

Use could be as simple as

...

if (solver->EvaluationCount() == 1) mydata->PrepareEvaluation()  

Advantages: 

• Residual block evaluators responsible for different "pieces" of he oveall cost function could stub to different initialization code on demand.
• Not all initializations need be one-shot. Some may depend on where one is during the solution, and may need to be occasionally repeated (e.g. periodical restarts based on where the state vector is).

if (solver->EvaluationCount() % 10 == 0) mydata->DoResetIfNecessary()

• Minimal additional state to be kept by Ceres, simpler change to API (only one extra call).

Disadvantages:

• Client code may need to keep one extra piece of state during evaluation that is shared among all residual block evaluators. This may be a problem if they reside on different threads, but they can be written as relatively cheap compare-and-swap operations on atomic integers, and arguably their impact compared to actually evaluating a residual would ordinarily be mimimal.

To view this discussion on the web visit https://groups.google.com/d/msgid/ceres-solver/CADpYijHkA9EeScQP2PApTpGkYZMvkFKBvr4wisQGZUK08xqE5Q%40mail.gmail.com.

For more options, visit https://groups.google.com/d/optout.

--

Franco Callari <fgca...@gmail.com>

            EC67 BEBE 62AC 8415 7591  2B12 A6CD D5EE D8CB D0ED

I am not bound to win, but I am bound to be true. I am not bound to succeed, but I am bound to live by the light that I have. (Abraham Lincoln)

[Keir Mierle]

Hi Francesco,

I've thought about this approach, but I'm less excited about it since it would require a bunch of plumbing, and could potentially introduce issues around API complexity. In particular, users would have to understand the contract around the tickets; my spidey sense is that it would be error prone, or users would do unnecessary things like caching all previous evaluations and so on.

Perhaps I'm unclear on the specifics of your proposal; can you make it more detailed by showing a sketch of what methods/classes would get added? And how they would be invoked?

Here's a followup proposal based on more discussion:

// Guarantee is that between EvaluationStart() and EvaluationStop() the

// values passed as parameters to the cost functions will not change.

struct EvaluationCallback() {

  void EvaluationStart()

  void PrepareForResidualEvaluation()

  void PrepareForJacobianEvaluation()

  void EvaluationComplete()

}

To address a separate comment about the reason to have EvaluationComplete() -- it's to enable users to free resources (e.g. GPU or memory) that might be held to enable caching.

Thoughts?

Keir

To view this discussion on the web visit https://groups.google.com/d/msgid/ceres-solver/CADyG_0%2Bpit-5iUFF9Q65WJjvET2ZtmTV9J_U5pDME5Se8%2B4aJQ%40mail.gmail.com.

[Keir Mierle]

To add some details to my proposal, Ceres would guarantees the following flow to users:

• Ceres calls evaluation_callback->EvaluationStart()
• Ceres repeats an arbitrary number of times (0 to N, usually 1)
• Ceres optionally calls evaluation_callback->PrepareForResidualEvaluation()
• Ceres optionally calls evaluation_callback->PrepareForJacobianEvaluation()
• Ceres calls evaluation_callback->EvaluationComplete()

As mentioned before, between the start() and complete() calls, the cost functions will be passed the same parameters.

[Sameer Agarwal]

Franco,

I do not understand your proposal either.

Your proposal would require, I think that the CostFunction objects be aware of the Solver object.. which I do not think is a good idea.

Sameer

Hi Adam,

To view this discussion on the web visit https://groups.google.com/d/msgid/ceres-solver/73b4f9d4-9e08-461c-b601-cbf3da5e3fbe%40googlegroups.com.

For more options, visit https://groups.google.com/d/optout.

--
You received this message because you are subscribed to the Google Groups "Ceres Solver" group.

To unsubscribe from this group and stop receiving emails from it, send an email to ceres-solver...@googlegroups.com.

To view this discussion on the web visit https://groups.google.com/d/msgid/ceres-solver/CADpYijHkA9EeScQP2PApTpGkYZMvkFKBvr4wisQGZUK08xqE5Q%40mail.gmail.com.

For more options, visit https://groups.google.com/d/optout.

--

Franco Callari <fgca...@gmail.com>

            EC67 BEBE 62AC 8415 7591  2B12 A6CD D5EE D8CB D0ED

I am not bound to win, but I am bound to be true. I am not bound to succeed, but I am bound to live by the light that I have. (Abraham Lincoln)

--
You received this message because you are subscribed to the Google Groups "Ceres Solver" group.

To unsubscribe from this group and stop receiving emails from it, send an email to ceres-solver...@googlegroups.com.

To view this discussion on the web visit https://groups.google.com/d/msgid/ceres-solver/CADyG_0%2Bpit-5iUFF9Q65WJjvET2ZtmTV9J_U5pDME5Se8%2B4aJQ%40mail.gmail.com.

For more options, visit https://groups.google.com/d/optout.

--
You received this message because you are subscribed to the Google Groups "Ceres Solver" group.
To unsubscribe from this group and stop receiving emails from it, send an email to ceres-solver...@googlegroups.com.

To view this discussion on the web visit https://groups.google.com/d/msgid/ceres-solver/CADpYijEu7SbbTJyunNS%2BUHQSijHrFVQ-hK5j2R-zsuxg9RG%3DZA%40mail.gmail.com.

[Adam Hartshorne]

I can only comment from a fairly novice perspective of large scale non-linear optimization, but the proposed interface looks applicable for my needs. 

As long within one of the proposed methods of EvaluationCallback allows / provides the following functionality; That I can establish which parameter blocks changed during the last iteration of the optimizer, make a call to a 3rd party library with those and update a local data structure with the return values (to be used by my cost functions).

I am presuming that I would simply put this code in EvaluationComplete() method, such that my local data structure can be updated ready for the next iteration.

Regards,

Adam

[Keir Mierle]

I spent some time today looking at an actual implementation of this interface. Unfortunately this is not trivial to do in a clean way. I'm concerned the result will make adding new solvers or changing the current ones buggy, since it will be easy to violate preconditions.

I updated the patch; please take a look. The new alternate interface is simpler.

https://ceres-solver-review.googlesource.com/c/ceres-solver/+/11600

To view this discussion on the web visit https://groups.google.com/d/msgid/ceres-solver/3d163e66-d6a2-47ce-9cbc-9c46c82678e8%40googlegroups.com.

[Sameer Agarwal]

and an updated version of this API has now been submitted to head!

Sameer

To view this discussion on the web visit https://groups.google.com/d/msgid/ceres-solver/CADpYijGbjqxzjVb0Fsubi6KP2-Mkweu9Q6tsaLOOpnr7%2BUd%3D%3Dw%40mail.gmail.com.

[Keir Mierle]

Yes; it's now in! Please take a look and see if it will work, and mail the list of there are any questions or if this interface isn't sufficient.

To view this discussion on the web visit https://groups.google.com/d/msgid/ceres-solver/CABqdRUAfGhz5FJTH7_o0sz%3DtwKnBwKCxy5HWZrJ779pxacuRrw%40mail.gmail.com.

[Adam Hartshorne]

Oh brilliant. I need to finish up something else I am working on and then I will be back to doing optimization via Ceres. 

I shall try and adapt my code / test it in the next week or so.

[Adam Hartshorne]

After converting my problem to use this new functionality, all seems to work correctly.

One thing thing that does come to mind. I seemed to remember in the original idea for this functionality, a list of parameter blocks which will be evaluated / remain constant would have been exposed. Is there a reason why this wasn't exposed in the end?

[Keir Mierle]

Hi Adam,

Glad to hear the new evaluation callback functionality is working for you!

The reason we don't expose the set of evaluated blocks is that currently, all blocks are evaluated every time, so there wouldn't be any savings. That might change later but there are no concrete plans for that currently.

Happy optimizing,

Keir

To view this discussion on the web visit https://groups.google.com/d/msgid/ceres-solver/caab0996-3d6f-48a9-b9e1-22ef79701e33%40googlegroups.com.