LinesearchMethod.Iterate() is subtly wrong

[vladimir-ch]

Working on #103 I noticed a possible subtle issue in LinesearchMethod.Iterate(). It is in a sense a consequence of another unclear definition/promise: that the location passed to Iterate() is always the same struct and that Methods are supposed to (or can) construct its fields gradually.

In linesearch.go:60 we compute the gradient projected onto the search direction and then pass it to Linesearcher.Finished() together with loc.F:

projGrad := floats.Dot(loc.Gradient, ls.dir)
if ls.Linesearcher.Finished(loc.F, projGrad) {

However, if only one of loc.F and loc.Gradient was evaluated previously, the other is NaN (because fortunately we invalidate). It obviously works, but I think it is more of a coincidence rather than intentional design. Backtracking requests only FuncEvaluation and checks only Armijo condition (so NaNs in the gradient don't bother it). Bisection requests FuncEvaluation | GradEvaluation, so projGrad = NaN never happens. The question is what would happen if we (or another external Linesearcher) started to issue the evaluations separately and request GradEvaluation only if the Armijo condition passes.

In general, I think we should not form projGrad and call Linsearcher.Finished() until we know that we have all the data for it but we do not (cannot) know that. It seems to me that it should be Linesearcher that announces to us that it has finished in a similar way how Method announces MajorIteration because Linesearcher best knows when it has all the data.

Comments, rebuttal, @btracey ?

As a side note, the change in Method interface as discussed in #103 basically precludes the *Location passed to Iterate() to be used as it is being used now, so it is a good thing. On the other hand, the snowball effect of changing the Method interface and merging IterationType and EvaluationType is pretty big. I may submit a trial PR sometime this week.

[vladimir-ch]

My own rebuttal: Passing invalid values (NaN or non-matching F and Gradient) to Linesearcher is inevitable. We have to pass them either to Finished() or Iterate() (or both as it is now) and Linesearcher decides if it has finished or not and both our Linesearchers decide correctly. So sorry for the noise.

What made me confused is that we pass the same values twice to Linesearcher and I realized that it is not necessary. If we want to minimize the API surface, then we can remove Finished() and instead Iterate() can return e.g. MajorIteration to indicate end of linesearch. I think it would be much cleaner and in line with LinesearchMethod. @btracey ?

[vladimir-ch]

With respect to whether Methods can rely on the passed Location to keep its contents between individual calls to Iterate(), I think there are basically two options.

1. We can document that it is implementation specific because it really depends on the combination of the Method and the driver function. Methods would like to reuse the location because it is convenient and saves a lot of copying and this will be the case in 99.9% of cases. However, they have no control over the driver that calls Iterate(). So we can say that Local() (or any other future driver function in the package) does not modify the location apart from requested evaluation (this means we would have to stop invalidating) so Methods can safely build up the location for MajorIteration without having to keep its own copy (they can if they have to). Our methods could rely on that assumtion. If an outsider implements its own driver function, she must not modify the location either, otherwise our Methods would break (and in that case, there is no point in using this package anyway).

2. Say that Methods should make no assumption on the contents of Location not evaluated by the previous request. Methods would always work, but it is not as convenient and leads to a lot of copying.

With respect to Linesearcher.Finished(), I think that replacing it with MajorIteration returned from Linesearcher.Iterate() is the cleanest approach.

[btracey]

I like the MajorIteration return from Linsearcher.

If an outsider implements its own driver function, she must not modify the location either, otherwise our Methods would break

You mean except for the X location?

[vladimir-ch]

I like the MajorIteration return from Linsearcher.

Ok, I will submit a PR later when the other one in queue is dealt with.

If an outsider implements its own driver function, she must not modify the location either, otherwise our Methods would break

You mean except for the X location?

I mean that if our Methods relied on the contents of Location not to be modified between calls to Iterate() apart from requested evaluations, then they would break if such modification took place (e.g., we would have to stop invalidating as we do now).

Someone taking our methods and using them in a custom version of Local() outside of optimize is unlikely, but can happen. Someone using its method in our Local() is on the other hand very likely, and in that case knowing that Location is not modified can be convenient for them. So we should decide, remove or keep invalidation, and document the behavior.

[btracey]

Yea, I think it makes the most sense if we promise not to modify. The previous model was "You tell us an X and and Operation, and we'll give that back to you". Now the model is "You fill in Location.X and tell us how to fill the rest".

Someone can't really use our methods outside of Local, as they are unexported. If they create an alternate implementation of Local to use with methods that's fine, but it's on them to keep the same contract.

Lastly, I don't think there's any real harm in promising to not modify location. Local doesn't communicate to the optimizers at present, so it doesn't need to modify the struct. Worst case the data can be copied if it needs to retain the information somehow.

[vladimir-ch]

Yea, I think it makes the most sense if we promise not to modify.

Ok. I put some comments in #123 to point out the affected code. I will keep that PR as it is (LinesearchMethod keeps its copy of Location) and will submit this change later in another PR.

Someone can't really use our methods outside of Local, as they are unexported

I don't understand, unexported? Our Methods are exported and can be used outside of the package.

If they create an alternate implementation of Local to use with methods that's fine, but it's on them to keep the same contract.

Ok.

Lastly, I don't think there's any real harm in promising to not modify location. Local doesn't communicate to the optimizers at present, so it doesn't need to modify the struct. Worst case the data can be copied if it needs to retain the information somehow.

Local does not communicate to the optimizers, but we do invalidate non-evaluated fields of Location as a kind of safety measure. That would have to go away.