Bounds and domain validity

[Kenneth V]

Hello,

I'm modeling a problem using Ceres 1.13.0: thanks for this amazing tool !

For my problem I am minimizing a cost function of 6 dimensions, which are a 2D position, and two 2D vectors. The loss function involving this 6D parameters is quite intricate and calls an external library.

The problem I'm facing is in the validity domain of this space:
- I have bounds: e.g., positions and vector lengths should be strictly bounded,
- And invalid parameter combinations: e.g., the position coordinates should be smaller than the vector lengths, and the vectors have a certain relationship regarding their inner angle.

I have problems with both:
- on bounds: the CostFunctor seems to evaluate at parameter values out of the bounds I set using setParameter<Upper/Lower>Bound. This is not accepted by the external library I'm using.
- on invalid combinations. I read about two strategies in the manual and tried them both (http://ceres-solver.org/modeling_faqs.html):
i) returning false when outside of the valid manifold. This regularly results in a "FAILURE (Residual and Jacobian evaluation failed.)". Can this be avoided or should I simply not proceed this way ?
ii) projecting or clipping to the domain of validity. In the CostFunctor, I clip values to the validity domain before calling my external library. This gives convergence issues: I tried clipping and wrapping around the unit circle in case of angles ... none really bring satisfying results.

A more general observation is: my 6D space is not homogeneous. Imagine that 4 dimensions range from 0 to 1000, and the two others from 0 to Pi (angles). I see that "moving out of bounds" happens on the latter with a higher probability than on the former. Can this be handled somehow, e.g., with an parameterblock-adaptive step size ?

Additional info regarding my implementation:
- Trust Region method (as I'm working with bounds) with the defaults: LEVENBERG_MARQUARDT and SPARSE_NORMAL_CHOLESKY.
- Numerical differentiation (because incompatibility with external library) wrapped in an AutoDiffCostFunction (following http://ceres-solver.org/interfacing_with_autodiff.html)
- I'm tuning numeric_diff_options_.relative_step_size to (try to) get it to converge.

Thank you for your input.

Kind regards,

Kenneth

[Sameer Agarwal]

Hi Kenneth,

My replies are inline.

On Tue, Oct 3, 2017 at 9:59 AM Kenneth V <kenneth...@gmail.com> wrote:

Hello,

I'm modeling a problem using Ceres 1.13.0: thanks for this amazing tool !

For my problem I am minimizing a cost function of 6 dimensions, which are a 2D position, and two 2D vectors. The loss function involving this 6D parameters is quite intricate and calls an external library.

The problem I'm facing is in the validity domain of this space:

- I have bounds: e.g., positions and vector lengths should be strictly bounded,
- And invalid parameter combinations: e.g., the position coordinates should be smaller than the vector lengths, and the vectors have a certain relationship regarding their inner angle.

Looks like you have an intricate set of constraints on your search space. 

I have problems with both:

- on bounds: the CostFunctor seems to evaluate at parameter values out of the bounds I set using setParameter<Upper/Lower>Bound. This is not accepted by the external library I'm using.

are your starting values for each of the parameters feasible?

 

- on invalid combinations. I read about two strategies in the manual and tried them both (http://ceres-solver.org/modeling_faqs.html):
i) returning false when outside of the valid manifold. This regularly results in a "FAILURE (Residual and Jacobian evaluation failed.)". Can this be avoided or should I simply not proceed this way ?

if you start with feasible values, this can work, but is not very good at complicated search spaces. 

ii) projecting or clipping to the domain of validity. In the CostFunctor, I clip values to the validity domain before calling my external library. This gives convergence issues: I tried clipping and wrapping around the unit circle in case of angles ... none really bring satisfying results.

yeah this just confuses the solver. 

A more general observation is: my 6D space is not homogeneous. Imagine that 4 dimensions range from 0 to 1000, and the two others from 0 to Pi (angles). I see that "moving out of bounds" happens on the latter with a higher probability than on the former. Can this be handled somehow, e.g., with an parameterblock-adaptive step size ?

this is something that the LM algorithm should handle on its own, by scaling the different dimensions appropriately. This should ideally be reflected in the Jacobian values too.

 

Additional info regarding my implementation:
- Trust Region method (as I'm working with bounds) with the defaults: LEVENBERG_MARQUARDT and SPARSE_NORMAL_CHOLESKY.
- Numerical differentiation (because incompatibility with external library) wrapped in an AutoDiffCostFunction (following http://ceres-solver.org/interfacing_with_autodiff.html)
- I'm tuning numeric_diff_options_.relative_step_size to (try to) get it to converge.

have you tried using the fancier ridders' method? which should do away with this tuning and give you much higher quality derivatives.

Sameer

Thank you for your input.

Kind regards,

Kenneth

--
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/d631619a-720c-4838-a1e6-d90efff62185%40googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Sameer Agarwal]

one thought here is, is it possible to reparameterize your problem with lower dimensional parameterization or a more simply constrained one?

[Kenneth V]

Hi Sameer,

Thanks for your (usual) reactivity :)

On Wednesday, 4 October 2017 16:19:58 UTC+2, Sameer Agarwal wrote:

one thought here is, is it possible to reparameterize your problem with lower dimensional parameterization or a more simply constrained one?

Lower is not possible, I'm even considering going increasing it more now ... this was just a first test.

On Wed, Oct 4, 2017 at 7:18 AM Sameer Agarwal <sameer...@google.com> wrote:

Hi Kenneth,

My replies are inline.

On Tue, Oct 3, 2017 at 9:59 AM Kenneth V <kenneth...@gmail.com> wrote:

Hello,

I'm modeling a problem using Ceres 1.13.0: thanks for this amazing tool !

For my problem I am minimizing a cost function of 6 dimensions, which are a 2D position, and two 2D vectors. The loss function involving this 6D parameters is quite intricate and calls an external library.

The problem I'm facing is in the validity domain of this space:

- I have bounds: e.g., positions and vector lengths should be strictly bounded,
- And invalid parameter combinations: e.g., the position coordinates should be smaller than the vector lengths, and the vectors have a certain relationship regarding their inner angle.

Looks like you have an intricate set of constraints on your search space. 

Well, ... yeah ;).

I have problems with both:

- on bounds: the CostFunctor seems to evaluate at parameter values out of the bounds I set using setParameter<Upper/Lower>Bound. This is not accepted by the external library I'm using.

are your starting values for each of the parameters feasible?

Yes they definitely are. To avoid starting out of the feasible domain I even put it kind of "in the middle", so that jumping out of it (more) rarely occurs.

 

- on invalid combinations. I read about two strategies in the manual and tried them both (http://ceres-solver.org/modeling_faqs.html):
i) returning false when outside of the valid manifold. This regularly results in a "FAILURE (Residual and Jacobian evaluation failed.)". Can this be avoided or should I simply not proceed this way ?

if you start with feasible values, this can work, but is not very good at complicated search spaces. 

ii) projecting or clipping to the domain of validity. In the CostFunctor, I clip values to the validity domain before calling my external library. This gives convergence issues: I tried clipping and wrapping around the unit circle in case of angles ... none really bring satisfying results.

yeah this just confuses the solver. 

So, As I'm starting with feasible values, I should rather use option i) than ii) if I understand well ?

A more general observation is: my 6D space is not homogeneous. Imagine that 4 dimensions range from 0 to 1000, and the two others from 0 to Pi (angles). I see that "moving out of bounds" happens on the latter with a higher probability than on the former. Can this be handled somehow, e.g., with an parameterblock-adaptive step size ?

this is something that the LM algorithm should handle on its own, by scaling the different dimensions appropriately. This should ideally be reflected in the Jacobian values too.

It kind of does a not too bad job here indeed. Except I find that it goes out of the feasibility domain quicker in the narrow dimensions.

 

Additional info regarding my implementation:
- Trust Region method (as I'm working with bounds) with the defaults: LEVENBERG_MARQUARDT and SPARSE_NORMAL_CHOLESKY.
- Numerical differentiation (because incompatibility with external library) wrapped in an AutoDiffCostFunction (following http://ceres-solver.org/interfacing_with_autodiff.html)
- I'm tuning numeric_diff_options_.relative_step_size to (try to) get it to converge.

have you tried using the fancier ridders' method? which should do away with this tuning and give you much higher quality derivatives.

Yes, I ran it last night. It does give a boost and improves a lot. But still, I'm not rid of the "out of validity domain" values that make the external library interrupt the processing.

Thanks again !

Kenneth

[Sameer Agarwal]

Kenneth, 

Let me check where in the library we are doing out of bounds checks.

To view this discussion on the web visit https://groups.google.com/d/msgid/ceres-solver/40d01ad4-c309-4975-8202-72328f796fa9%40googlegroups.com.

[Kenneth V]

Dear Sameer,

Any news on this question ?

Although I mostly got rid of the problem by:
- reparameterizing in a more homogeneous space (everything is carthesian coordinates now, no more angles),

- using RIDDERS.

To improve convergence and accuracy, I now took a dive into the code of the external library I'm using and made it Jet-compatible.
However, I now have the following surprising behavior:

- Numerical differentiation is slow (RIDDERS) but converges to a reasonable result (even a very good one in simple cases).
- Automatic differentiation (up to the fact that there is an underlying discrete image being looked up, using BiCubic interpolation as suggested in your documentation) is faster (about an order of magnitude) but is nowhere near an as good solution as the numerical variant (the loss is orders of magnitude off: there are much more iterations being done in shorter time, but the cost_change is ridiculously small ...).

My question: according to your experience, is this necessarily a bug, or could it be that auto-diff is not the best way to go for my problem (on which I don't want to bother you with more detail yet, unless you tell me to) ?

Thank you for your insight.

Best,

Kenneth

[Sameer Agarwal]

Kenneth I have not had a chance, work has been busy. My comments inline.

On Fri, Oct 13, 2017 at 5:26 AM Kenneth V <kenneth...@gmail.com> wrote:

Dear Sameer,

Any news on this question ?

Although I mostly got rid of the problem by:
- reparameterizing in a more homogeneous space (everything is carthesian coordinates now, no more angles),

+1

 

- using RIDDERS.

To improve convergence and accuracy, I now took a dive into the code of the external library I'm using and made it Jet-compatible.
However, I now have the following surprising behavior:

- Numerical differentiation is slow (RIDDERS) but converges to a reasonable result (even a very good one in simple cases). 

- Automatic differentiation (up to the fact that there is an underlying discrete image being looked up, using BiCubic interpolation as suggested in your documentation) is faster (about an order of magnitude) but is nowhere near an as good solution as the numerical variant (the loss is orders of magnitude off: there are much more iterations being done in shorter time, but the cost_change is ridiculously small ...).

are you sure your implementations match?

 

My question: according to your experience, is this necessarily a bug, or could it be that auto-diff is not the best way to go for my problem (on which I don't want to bother you with more detail yet, unless you tell me to) ?

sounds like a bug to me. unless your function is noisy somehow, and ridders is getting around it. 

Sameer

 

To view this discussion on the web visit https://groups.google.com/d/msgid/ceres-solver/6eddf377-3105-42b0-9920-975156b39d6c%40googlegroups.com.

[Keir Mierle]

On Fri, Oct 13, 2017 at 7:29 AM, 'Sameer Agarwal' via Ceres Solver <ceres-...@googlegroups.com> wrote:

Kenneth I have not had a chance, work has been busy. My comments inline.

On Fri, Oct 13, 2017 at 5:26 AM Kenneth V <kenneth...@gmail.com> wrote:

Dear Sameer,

Any news on this question ?

Although I mostly got rid of the problem by:
- reparameterizing in a more homogeneous space (everything is carthesian coordinates now, no more angles),

+1

 

- using RIDDERS.

To improve convergence and accuracy, I now took a dive into the code of the external library I'm using and made it Jet-compatible.
However, I now have the following surprising behavior:

- Numerical differentiation is slow (RIDDERS) but converges to a reasonable result (even a very good one in simple cases). 

- Automatic differentiation (up to the fact that there is an underlying discrete image being looked up, using BiCubic interpolation as suggested in your documentation) is faster (about an order of magnitude) but is nowhere near an as good solution as the numerical variant (the loss is orders of magnitude off: there are much more iterations being done in shorter time, but the cost_change is ridiculously small ...).

are you sure your implementations match?

 

My question: according to your experience, is this necessarily a bug, or could it be that auto-diff is not the best way to go for my problem (on which I don't want to bother you with more detail yet, unless you tell me to) ?

sounds like a bug to me. unless your function is noisy somehow, and ridders is getting around it. 

Though I wanted to add-- if you are calling an external library, then care must be taken to ensure the derivatives are propagated correctly from the external function. How are you bridging to the external library if you're using autodiff?

 

Sameer

 

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/6eddf377-3105-42b0-9920-975156b39d6c%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/CABqdRUAM_snT6u0-7JTi6POOJYHs1ptFUpU1ADuv-5J9SQtjjg%40mail.gmail.com.

[Kenneth V]

Hi Sameer and Keir,

Thank you for your comments. Replies below:

On Friday, 13 October 2017 17:38:52 UTC+2, Keir Mierle wrote:

On Fri, Oct 13, 2017 at 7:29 AM, 'Sameer Agarwal' via Ceres Solver <ceres-...@googlegroups.com> wrote:

Kenneth I have not had a chance, work has been busy. My comments inline.

On Fri, Oct 13, 2017 at 5:26 AM Kenneth V <kenneth...@gmail.com> wrote:

Dear Sameer,

Any news on this question ?

Although I mostly got rid of the problem by:
- reparameterizing in a more homogeneous space (everything is carthesian coordinates now, no more angles),

+1

 

- using RIDDERS.

To improve convergence and accuracy, I now took a dive into the code of the external library I'm using and made it Jet-compatible.
However, I now have the following surprising behavior:

- Numerical differentiation is slow (RIDDERS) but converges to a reasonable result (even a very good one in simple cases). 

- Automatic differentiation (up to the fact that there is an underlying discrete image being looked up, using BiCubic interpolation as suggested in your documentation) is faster (about an order of magnitude) but is nowhere near an as good solution as the numerical variant (the loss is orders of magnitude off: there are much more iterations being done in shorter time, but the cost_change is ridiculously small ...).

are you sure your implementations match?

I am 99% sure, yes: they actually call the same templated function (instantiated with doubles when doing Numerical Diff). The only difference is in the wrapping of the templated cost function into a CostFunctionToFunctor for the numerical version.

 

My question: according to your experience, is this necessarily a bug, or could it be that auto-diff is not the best way to go for my problem (on which I don't want to bother you with more detail yet, unless you tell me to) ?

sounds like a bug to me. unless your function is noisy somehow, and ridders is getting around it. 

That's one (sad) possibility.

Though I wanted to add-- if you are calling an external library, then care must be taken to ensure the derivatives are propagated correctly from the external function. How are you bridging to the external library if you're using autodiff?

That's a very good point and I'm not certain about the answer.

The library I'm using defines a mesh (with 3D coordinates at its vertices). These coordinates are to be optimized according to my loss function and some constrained degrees of freedom.
The type of embedding for these vertices is templated: instead of Eigen vectors of type double, they get instantiated by Eigen vectors of type Jet when using AutoDiff. All fine until here.
The loss function is of the form: sum over all mesh faces, a function of its (vertex) coordinates. This means there's a topological iteration going on over the mesh structure. However, I haven't touched/bridged anything in the way the whole mesh structure (topology, etc.) is handled or is iterated over, which is what this library very nicely does for me.

The bottomline is: I'm afraid I haven't bridged the Ceres Jets mechanism sufficiently, but also that this is a quite unfeasible thing to do ...
If you have any comments on this, I'm very glad to take them.

Thanks a lot !

Kenneth

 

Sameer

 

To view this discussion on the web visit https://groups.google.com/d/msgid/ceres-solver/6eddf377-3105-42b0-9920-975156b39d6c%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.

[Sameer Agarwal]

I would start by looking at the function values and derivatives you are getting from a given cost function via automatic and numerical differentiation at a variety of points and how much they differ. 

do not invoke the solver, just look at the cost functions.

Sameer

To view this discussion on the web visit https://groups.google.com/d/msgid/ceres-solver/ba21c9c0-c51a-42fe-b22d-0e73c70a2566%40googlegroups.com.

[Kenneth V]

Thanks for the suggestion.

Just did that, and
- the residual is perfectly identical
- the Jacobian has significant differences

Having differences in the Jacobian is expected I guess, as the differentiation technique differs.
Maybe having significant differences (sometimes an order of magnitude, or an opposed sign) is not expected, or is it ?

Here an example of Jacobian values (after calls to CostFunction->Evaluate()):
Jacobian(AutoDiff):  0.0431325      0.00224283    0.120488     0.123803    1.05558       -0.0230825
Jacobian(NumDiff): -0.00269574   -0.00165561    0.0428341   0.13988       0.736482    -0.00394873

Best,

Kenneth

[Sameer Agarwal]

These differences in Jacobians seem rather large. Ridders is a very accurate differentiation technique, so this is worth looking into more carefully.

Sameer

To view this discussion on the web visit https://groups.google.com/d/msgid/ceres-solver/1db3a760-2f5e-4740-8923-e86749e41d8b%40googlegroups.com.

[Kenneth V]

I agree.
Will do, thanks for the hint.

K.

[Kenneth V]

I'm checking all the computation done and see if Jets are properly bridged.
Nothing wrong found yet.
In my code I'm computing a variance of a large number of scalars (involving mean computation based on sums, divisions, squares, etc.). From a quick look at the operators on Jets, I think this is well-defined with dual numbers as well, but haven't done the math yet (next thing on my list). In case this rings a bell for one of you, let me know..

Other question: is it normal that the auto derivatives are defined from a single evaluation of the cost function ? I guess so (after reading the theory on dual numbers), but in case that is an anomaly, let me know and I'll dig there ...

Best,

Kenneth

[Kenneth V]

On Wednesday, 18 October 2017 12:06:37 UTC+2, Kenneth V wrote:

I'm checking all the computation done and see if Jets are properly bridged.
Nothing wrong found yet.
In my code I'm computing a variance of a large number of scalars (involving mean computation based on sums, divisions, squares, etc.).

Square is the critical thing being used here I think.
I discovered that it's undefined at 0 for Jets. Although my application wasn't suffering from it, the goal of my optimization is to have sqrt(something) to go to tend to zero, so I should define something there in the future I guess ...
I'm checking for other hidden things I would have overseen.