You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@commons.apache.org by Phil Steitz <ph...@steitz.com> on 2012/11/17 21:34:30 UTC
[math] Making last iteration data available when iterative algorithms
fail to converge (MATH-902)
I think MATH-902 makes a reasonable request, but I don't think the
exception is the right place to communicate last iteration data.
When iterative algorithms fail to converge and TooManyEvaluations or
other iteration bounds exceptions are thrown, the request in
MATH-902 is to make the last iterate available as a field in the
exception. My inclination would be to not to do this, but instead
to adopt the convention that the class doing the iteration should
maintain last iteration state information.
Phil
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org
Re: [math] Making last iteration data available when iterative
algorithms fail to converge (MATH-902)
Posted by Gilles Sadowski <gi...@harfang.homelinux.org>.
> > > [...]
> >>> I like a lot the idea of registering user event handlers to be called
> >>> back by the solver at each iteration. This can be used to only overwrite
> >>> better solutions as they are found, but it also has many more usages
> >>> like displaying progress. This is what Nikolaus asked for when we
> >>> implemented CMAES. I'm not sure about the API though. Either we could
> >>> pass many parameters (number of iterations, current point and value) or
> >>> simply a reference to the optimizer, and add custom getters for each
> >>> optimizers, so the user could retrieve specific information when they
> >>> know which optimizer type they use and they can cast the refererence to
> >>> call algorithm-specific getters abnout the current state.
> >>>
> > The first solution is the one used in IterativeSolverEvent, which extends
> > IterationEvent. I don't like the second option (using custom getters for
> > each optimizers). As I said, iterative linear solvers do *not* hold
> > information relating to the system currently being solved. It seems that
> > things are a bit different in optimizers, but if we assume that all
> > interesting information can be retrieved from the object which actually
> > performs the iterations, I think we lose flexibility.
> >
> > At the moment, for iterative linear solvers, saving the last iterate can
> > only be done in an event handler. For example, in the corresponding
> > IterationListener, you could use e.getSolution() each time
> > iterationPerformed(e) is called. This is potentially costly, though, since
> > this returns a copy of the (potentially large) vector x. I think that we
> > could add a method to IterationListener, e.g. aboutToFail(e) (for lack of a
> > better name). Then a copy of the current solution would be taken only here.
> > What do you think? I don't know how applicable to optimizers that would be,
> > but it would be fairly straightforward for iterative linear solvers.
> >
> >
> >>> We already have something roughly similar to this in the ODE package. We
> >>> have both step handlers and events handlers, but they have slightly
> >>> differente meanings to what is desired here. Perhaps we should use a
> >>> name like IterationHandler to avoid confusion.
> >> I don't like what currently exists in "CMAESOptimizer" just because it is
> >> ad-hoc code. The justification was that, for "scientific purpose", it is
> >> necessary to be able to follow the behaviour of the algorithm. I totally
> >> agree with the latter statement, but I do not agree that every
> >> implementation should do it in its own way.
> >> And, more importantly, if we put this justification forward, there is a
> >> much
> >> straightforward solution: logging. Logging should be available before
> >> sinking into littering the useful code with "infrastructure" statements
> >> whose only purpose is to give "real-time" information.
> >> As it is, we can probably agree that CM is not suitable for analysing an
> >> algorithm's behaviour. But, again, is it the purpose? I think not (from my
> >> interpretation of stated goals): users call CM as a black box, and can only
> >> assume that given some input, it will provide the correct (= expected)
> >> output.
> >>
> >> Yes and no. If each iteration of the algorithm is very long, then the
> > ability of monitoring the iterations is very useful -- not only from an
> > academic point of view, even if I think this is also important, as there is
> > no equivalent to CM with these academic facilities you do not seem to like.
> > So I would say: the main purpose of CM is not the analysis of an algo.
> > However, if that's not too much of a hassle, opening the algos is a plus
> > which we should not reject. I think event handlers offer this flexibility.
> >
> > You mentioned logging. I was not aware of logging in CM, or even on any
> > consensus about logging at all. I'm sorry if this is a silly question, but
> > what exactly do you have in mind?
>
> One way to look at this is that logging is what a client app can
> choose to do when it gets an event that it wants to log from
> [math]. I agree that we should try to do two things to make this
> easier for users of [math]:
>
> 0) expose properties that can be interrogated at run time that users
> may wish to observe and log or otherwise persist
> 1) design appropriate event listener support into the library
>
> The current discussion was started by a user request for an instance
> of problem 0). We have done some experimenting with 1). I think it
> is better to continue that than to add logging (and dependency on
> logback or somesuch) to the code. If we give users access to the
> properties and events they need, they can do their own logging.
I do not hold the same view of the purpose of logging (or maybe I missed a
point here). IMO, the primary goal of logging is to trace the behaviour of
a code in order to ensure that an algorithm behaves as expected. I admit
that it is neither necessary nor sufficient to prove correctness: it is just
a simple tool that usually allows to figure out what is going wrong. [In
debugging CM, I guess that we all resorted to the poor man's logging:
sprinkling the code with temporary "println" statements...]
In logging, the _developer_ decides what information to provide, and the
_user_ decides how much of the available information he wants to see (based
on the log level).
This is not in contradiction with having a more sophisticated setup, but
I'd say: simple things first.
There would be only one, quite stable and lightweight, dependency:
"slf4j-api".
Users would just need to choose an actual logging system that implements
that API (or put an "no-op" logger JAR in their classpath to disable logging
completely).
Regards,
Gilles
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org
Re: [math] Making last iteration data available when iterative algorithms
fail to converge (MATH-902)
Posted by Phil Steitz <ph...@gmail.com>.
On 11/18/12 11:00 AM, Sébastien Brisard wrote:
> Hi,
>
>
> 2012/11/18 Gilles Sadowski <gi...@harfang.homelinux.org>
>
>> On Sun, Nov 18, 2012 at 11:19:14AM +0100, Luc Maisonobe wrote:
>>> Le 18/11/2012 10:53, Sébastien Brisard a écrit :
>>>> Hi,
>>> Hi all,
>>>
>>>>
>>>> 2012/11/17 Gilles Sadowski <gi...@harfang.homelinux.org>
>>>>
>>>>> On Sat, Nov 17, 2012 at 12:34:30PM -0800, Phil Steitz wrote:
>>>>>> I think MATH-902 makes a reasonable request, but I don't think the
>>>>>> exception is the right place to communicate last iteration data.
>>>>>> When iterative algorithms fail to converge and TooManyEvaluations or
>>>>>> other iteration bounds exceptions are thrown, the request in
>>>>>> MATH-902 is to make the last iterate available as a field in the
>>>>>> exception. My inclination would be to not to do this, but instead
>>>>>> to adopt the convention that the class doing the iteration should
>>>>>> maintain last iteration state information.
>>>>> I understand the temptation to provide such a facility but it will
>> make
>>>>> the implementation more complicated (additional bookkeeping) than
>> necessary
>>>>> for the regular case, by which I mean that inputs were passed that
>> don't
>>>>> lead to failure.
>>>>> Indeed, correct usage rests on the user, who is responsible for
>> providing
>>>>> compatible values for maximum number of evaluations and the
>> convergence
>>>>> criteria.
>>>>> The current design stems from the consideration that is "maxEval" is
>>>>> reached, it means that something has gone wrong: it took more
>> evaluations
>>>>> than the _user_ was expecting.
>>>>> If this check gets in the way (as suggested by MATH-902), the user can
>>>>> always pass "Integer.MAX_VALUE", thereby disabling the safe-guard;
>> but he
>>>>> must accept that he might wait a long time...
>>>>>
>>>>> It would be easier to figure out which approach is correct if we
>> could have
>>>>> a concrete use-case.[1]
>>>>>
>>>>> The same issue also occurs with iterative linear solvers. I have
>> concrete
>>>> use-cases, in this instance. Some of the systems I try to invert are
>> quite
>>>> large (as in 128 * 128 * 128 * 6 unknowns). If the system is
>>>> ill-conditioned and the requirements on the stopping criterion is too
>>>> stringent, then the whole inversion will fail because of the maximum
>> number
>>>> of iterations being reached. Now, failure is so "brutal" (meaning:
>> nothing
>>>> is returned) that you can't even know how close the best estimate of
>> the
>>>> solution is to the true solution, so you don't even know how to alter
>> the
>>>> parameters of your solvers for failure not to happen again. Since these
>>>> iterations take a long time, this is a bit annoying.
>>>>
>>>> With iterative solvers, there is a work-around, using the event
>> handling
>>>> that is provided, which allows access to the *current* estimate of the
>>>> solution.
>>>>
>>>> So I agree with Phil that it would be nice to retrieve the "best"
>> estimate
>>>> of the solution, even if crash occurs. But I also agree with Gilles
>> that
>>>> this must be done carefully. All the iterative solvers implemented so
>> far
>>>> are almost state-less. The only class variables are related to the
>> stopping
>>>> criterion. No data relating to the current system being inverted is
>> stored
>>>> as a class variable (and is therefore not accessible). Again, event
>>>> handlers might be the way to go, we could add an event which is fired
>> prior
>>>> to throwing the failure exception.
>>> I like a lot the idea of registering user event handlers to be called
>>> back by the solver at each iteration. This can be used to only overwrite
>>> better solutions as they are found, but it also has many more usages
>>> like displaying progress. This is what Nikolaus asked for when we
>>> implemented CMAES. I'm not sure about the API though. Either we could
>>> pass many parameters (number of iterations, current point and value) or
>>> simply a reference to the optimizer, and add custom getters for each
>>> optimizers, so the user could retrieve specific information when they
>>> know which optimizer type they use and they can cast the refererence to
>>> call algorithm-specific getters abnout the current state.
>>>
> The first solution is the one used in IterativeSolverEvent, which extends
> IterationEvent. I don't like the second option (using custom getters for
> each optimizers). As I said, iterative linear solvers do *not* hold
> information relating to the system currently being solved. It seems that
> things are a bit different in optimizers, but if we assume that all
> interesting information can be retrieved from the object which actually
> performs the iterations, I think we lose flexibility.
>
> At the moment, for iterative linear solvers, saving the last iterate can
> only be done in an event handler. For example, in the corresponding
> IterationListener, you could use e.getSolution() each time
> iterationPerformed(e) is called. This is potentially costly, though, since
> this returns a copy of the (potentially large) vector x. I think that we
> could add a method to IterationListener, e.g. aboutToFail(e) (for lack of a
> better name). Then a copy of the current solution would be taken only here.
> What do you think? I don't know how applicable to optimizers that would be,
> but it would be fairly straightforward for iterative linear solvers.
>
>
>>> We already have something roughly similar to this in the ODE package. We
>>> have both step handlers and events handlers, but they have slightly
>>> differente meanings to what is desired here. Perhaps we should use a
>>> name like IterationHandler to avoid confusion.
>> I don't like what currently exists in "CMAESOptimizer" just because it is
>> ad-hoc code. The justification was that, for "scientific purpose", it is
>> necessary to be able to follow the behaviour of the algorithm. I totally
>> agree with the latter statement, but I do not agree that every
>> implementation should do it in its own way.
>> And, more importantly, if we put this justification forward, there is a
>> much
>> straightforward solution: logging. Logging should be available before
>> sinking into littering the useful code with "infrastructure" statements
>> whose only purpose is to give "real-time" information.
>> As it is, we can probably agree that CM is not suitable for analysing an
>> algorithm's behaviour. But, again, is it the purpose? I think not (from my
>> interpretation of stated goals): users call CM as a black box, and can only
>> assume that given some input, it will provide the correct (= expected)
>> output.
>>
>> Yes and no. If each iteration of the algorithm is very long, then the
> ability of monitoring the iterations is very useful -- not only from an
> academic point of view, even if I think this is also important, as there is
> no equivalent to CM with these academic facilities you do not seem to like.
> So I would say: the main purpose of CM is not the analysis of an algo.
> However, if that's not too much of a hassle, opening the algos is a plus
> which we should not reject. I think event handlers offer this flexibility.
>
> You mentioned logging. I was not aware of logging in CM, or even on any
> consensus about logging at all. I'm sorry if this is a silly question, but
> what exactly do you have in mind?
One way to look at this is that logging is what a client app can
choose to do when it gets an event that it wants to log from
[math]. I agree that we should try to do two things to make this
easier for users of [math]:
0) expose properties that can be interrogated at run time that users
may wish to observe and log or otherwise persist
1) design appropriate event listener support into the library
The current discussion was started by a user request for an instance
of problem 0). We have done some experimenting with 1). I think it
is better to continue that than to add logging (and dependency on
logback or somesuch) to the code. If we give users access to the
properties and events they need, they can do their own logging.
Phil
>
>> Best regards,
>> Gilles
>>
> Best regards,
> Sébastien
>
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org
Re: [math] Making last iteration data available when iterative
algorithms fail to converge (MATH-902)
Posted by Sébastien Brisard <se...@m4x.org>.
Hi,
2012/11/18 Gilles Sadowski <gi...@harfang.homelinux.org>
> On Sun, Nov 18, 2012 at 11:19:14AM +0100, Luc Maisonobe wrote:
> > Le 18/11/2012 10:53, Sébastien Brisard a écrit :
> > > Hi,
> >
> > Hi all,
> >
> > >
> > >
> > > 2012/11/17 Gilles Sadowski <gi...@harfang.homelinux.org>
> > >
> > >> On Sat, Nov 17, 2012 at 12:34:30PM -0800, Phil Steitz wrote:
> > >>> I think MATH-902 makes a reasonable request, but I don't think the
> > >>> exception is the right place to communicate last iteration data.
> > >>> When iterative algorithms fail to converge and TooManyEvaluations or
> > >>> other iteration bounds exceptions are thrown, the request in
> > >>> MATH-902 is to make the last iterate available as a field in the
> > >>> exception. My inclination would be to not to do this, but instead
> > >>> to adopt the convention that the class doing the iteration should
> > >>> maintain last iteration state information.
> > >>
> > >> I understand the temptation to provide such a facility but it will
> make
> > >> the implementation more complicated (additional bookkeeping) than
> necessary
> > >> for the regular case, by which I mean that inputs were passed that
> don't
> > >> lead to failure.
> > >> Indeed, correct usage rests on the user, who is responsible for
> providing
> > >> compatible values for maximum number of evaluations and the
> convergence
> > >> criteria.
> > >> The current design stems from the consideration that is "maxEval" is
> > >> reached, it means that something has gone wrong: it took more
> evaluations
> > >> than the _user_ was expecting.
> > >> If this check gets in the way (as suggested by MATH-902), the user can
> > >> always pass "Integer.MAX_VALUE", thereby disabling the safe-guard;
> but he
> > >> must accept that he might wait a long time...
> > >>
> > >> It would be easier to figure out which approach is correct if we
> could have
> > >> a concrete use-case.[1]
> > >>
> > >> The same issue also occurs with iterative linear solvers. I have
> concrete
> > > use-cases, in this instance. Some of the systems I try to invert are
> quite
> > > large (as in 128 * 128 * 128 * 6 unknowns). If the system is
> > > ill-conditioned and the requirements on the stopping criterion is too
> > > stringent, then the whole inversion will fail because of the maximum
> number
> > > of iterations being reached. Now, failure is so "brutal" (meaning:
> nothing
> > > is returned) that you can't even know how close the best estimate of
> the
> > > solution is to the true solution, so you don't even know how to alter
> the
> > > parameters of your solvers for failure not to happen again. Since these
> > > iterations take a long time, this is a bit annoying.
> > >
> > > With iterative solvers, there is a work-around, using the event
> handling
> > > that is provided, which allows access to the *current* estimate of the
> > > solution.
> > >
> > > So I agree with Phil that it would be nice to retrieve the "best"
> estimate
> > > of the solution, even if crash occurs. But I also agree with Gilles
> that
> > > this must be done carefully. All the iterative solvers implemented so
> far
> > > are almost state-less. The only class variables are related to the
> stopping
> > > criterion. No data relating to the current system being inverted is
> stored
> > > as a class variable (and is therefore not accessible). Again, event
> > > handlers might be the way to go, we could add an event which is fired
> prior
> > > to throwing the failure exception.
> >
> > I like a lot the idea of registering user event handlers to be called
> > back by the solver at each iteration. This can be used to only overwrite
> > better solutions as they are found, but it also has many more usages
> > like displaying progress. This is what Nikolaus asked for when we
> > implemented CMAES. I'm not sure about the API though. Either we could
> > pass many parameters (number of iterations, current point and value) or
> > simply a reference to the optimizer, and add custom getters for each
> > optimizers, so the user could retrieve specific information when they
> > know which optimizer type they use and they can cast the refererence to
> > call algorithm-specific getters abnout the current state.
> >
>
The first solution is the one used in IterativeSolverEvent, which extends
IterationEvent. I don't like the second option (using custom getters for
each optimizers). As I said, iterative linear solvers do *not* hold
information relating to the system currently being solved. It seems that
things are a bit different in optimizers, but if we assume that all
interesting information can be retrieved from the object which actually
performs the iterations, I think we lose flexibility.
At the moment, for iterative linear solvers, saving the last iterate can
only be done in an event handler. For example, in the corresponding
IterationListener, you could use e.getSolution() each time
iterationPerformed(e) is called. This is potentially costly, though, since
this returns a copy of the (potentially large) vector x. I think that we
could add a method to IterationListener, e.g. aboutToFail(e) (for lack of a
better name). Then a copy of the current solution would be taken only here.
What do you think? I don't know how applicable to optimizers that would be,
but it would be fairly straightforward for iterative linear solvers.
> > We already have something roughly similar to this in the ODE package. We
> > have both step handlers and events handlers, but they have slightly
> > differente meanings to what is desired here. Perhaps we should use a
> > name like IterationHandler to avoid confusion.
>
> I don't like what currently exists in "CMAESOptimizer" just because it is
> ad-hoc code. The justification was that, for "scientific purpose", it is
> necessary to be able to follow the behaviour of the algorithm. I totally
> agree with the latter statement, but I do not agree that every
> implementation should do it in its own way.
> And, more importantly, if we put this justification forward, there is a
> much
> straightforward solution: logging. Logging should be available before
> sinking into littering the useful code with "infrastructure" statements
> whose only purpose is to give "real-time" information.
> As it is, we can probably agree that CM is not suitable for analysing an
> algorithm's behaviour. But, again, is it the purpose? I think not (from my
> interpretation of stated goals): users call CM as a black box, and can only
> assume that given some input, it will provide the correct (= expected)
> output.
>
> Yes and no. If each iteration of the algorithm is very long, then the
ability of monitoring the iterations is very useful -- not only from an
academic point of view, even if I think this is also important, as there is
no equivalent to CM with these academic facilities you do not seem to like.
So I would say: the main purpose of CM is not the analysis of an algo.
However, if that's not too much of a hassle, opening the algos is a plus
which we should not reject. I think event handlers offer this flexibility.
You mentioned logging. I was not aware of logging in CM, or even on any
consensus about logging at all. I'm sorry if this is a silly question, but
what exactly do you have in mind?
>
> Best regards,
> Gilles
>
Best regards,
Sébastien
Re: [math] Making last iteration data available when iterative
algorithms fail to converge (MATH-902)
Posted by Gilles Sadowski <gi...@harfang.homelinux.org>.
On Sun, Nov 18, 2012 at 11:19:14AM +0100, Luc Maisonobe wrote:
> Le 18/11/2012 10:53, Sébastien Brisard a écrit :
> > Hi,
>
> Hi all,
>
> >
> >
> > 2012/11/17 Gilles Sadowski <gi...@harfang.homelinux.org>
> >
> >> On Sat, Nov 17, 2012 at 12:34:30PM -0800, Phil Steitz wrote:
> >>> I think MATH-902 makes a reasonable request, but I don't think the
> >>> exception is the right place to communicate last iteration data.
> >>> When iterative algorithms fail to converge and TooManyEvaluations or
> >>> other iteration bounds exceptions are thrown, the request in
> >>> MATH-902 is to make the last iterate available as a field in the
> >>> exception. My inclination would be to not to do this, but instead
> >>> to adopt the convention that the class doing the iteration should
> >>> maintain last iteration state information.
> >>
> >> I understand the temptation to provide such a facility but it will make
> >> the implementation more complicated (additional bookkeeping) than necessary
> >> for the regular case, by which I mean that inputs were passed that don't
> >> lead to failure.
> >> Indeed, correct usage rests on the user, who is responsible for providing
> >> compatible values for maximum number of evaluations and the convergence
> >> criteria.
> >> The current design stems from the consideration that is "maxEval" is
> >> reached, it means that something has gone wrong: it took more evaluations
> >> than the _user_ was expecting.
> >> If this check gets in the way (as suggested by MATH-902), the user can
> >> always pass "Integer.MAX_VALUE", thereby disabling the safe-guard; but he
> >> must accept that he might wait a long time...
> >>
> >> It would be easier to figure out which approach is correct if we could have
> >> a concrete use-case.[1]
> >>
> >> The same issue also occurs with iterative linear solvers. I have concrete
> > use-cases, in this instance. Some of the systems I try to invert are quite
> > large (as in 128 * 128 * 128 * 6 unknowns). If the system is
> > ill-conditioned and the requirements on the stopping criterion is too
> > stringent, then the whole inversion will fail because of the maximum number
> > of iterations being reached. Now, failure is so "brutal" (meaning: nothing
> > is returned) that you can't even know how close the best estimate of the
> > solution is to the true solution, so you don't even know how to alter the
> > parameters of your solvers for failure not to happen again. Since these
> > iterations take a long time, this is a bit annoying.
> >
> > With iterative solvers, there is a work-around, using the event handling
> > that is provided, which allows access to the *current* estimate of the
> > solution.
> >
> > So I agree with Phil that it would be nice to retrieve the "best" estimate
> > of the solution, even if crash occurs. But I also agree with Gilles that
> > this must be done carefully. All the iterative solvers implemented so far
> > are almost state-less. The only class variables are related to the stopping
> > criterion. No data relating to the current system being inverted is stored
> > as a class variable (and is therefore not accessible). Again, event
> > handlers might be the way to go, we could add an event which is fired prior
> > to throwing the failure exception.
>
> I like a lot the idea of registering user event handlers to be called
> back by the solver at each iteration. This can be used to only overwrite
> better solutions as they are found, but it also has many more usages
> like displaying progress. This is what Nikolaus asked for when we
> implemented CMAES. I'm not sure about the API though. Either we could
> pass many parameters (number of iterations, current point and value) or
> simply a reference to the optimizer, and add custom getters for each
> optimizers, so the user could retrieve specific information when they
> know which optimizer type they use and they can cast the refererence to
> call algorithm-specific getters abnout the current state.
>
> We already have something roughly similar to this in the ODE package. We
> have both step handlers and events handlers, but they have slightly
> differente meanings to what is desired here. Perhaps we should use a
> name like IterationHandler to avoid confusion.
I don't like what currently exists in "CMAESOptimizer" just because it is
ad-hoc code. The justification was that, for "scientific purpose", it is
necessary to be able to follow the behaviour of the algorithm. I totally
agree with the latter statement, but I do not agree that every
implementation should do it in its own way.
And, more importantly, if we put this justification forward, there is a much
straightforward solution: logging. Logging should be available before
sinking into littering the useful code with "infrastructure" statements
whose only purpose is to give "real-time" information.
As it is, we can probably agree that CM is not suitable for analysing an
algorithm's behaviour. But, again, is it the purpose? I think not (from my
interpretation of stated goals): users call CM as a black box, and can only
assume that given some input, it will provide the correct (= expected)
output.
Best regards,
Gilles
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org
Re: [math] Making last iteration data available when iterative algorithms
fail to converge (MATH-902)
Posted by Luc Maisonobe <Lu...@free.fr>.
Le 18/11/2012 10:53, Sébastien Brisard a écrit :
> Hi,
Hi all,
>
>
> 2012/11/17 Gilles Sadowski <gi...@harfang.homelinux.org>
>
>> On Sat, Nov 17, 2012 at 12:34:30PM -0800, Phil Steitz wrote:
>>> I think MATH-902 makes a reasonable request, but I don't think the
>>> exception is the right place to communicate last iteration data.
>>> When iterative algorithms fail to converge and TooManyEvaluations or
>>> other iteration bounds exceptions are thrown, the request in
>>> MATH-902 is to make the last iterate available as a field in the
>>> exception. My inclination would be to not to do this, but instead
>>> to adopt the convention that the class doing the iteration should
>>> maintain last iteration state information.
>>
>> I understand the temptation to provide such a facility but it will make
>> the implementation more complicated (additional bookkeeping) than necessary
>> for the regular case, by which I mean that inputs were passed that don't
>> lead to failure.
>> Indeed, correct usage rests on the user, who is responsible for providing
>> compatible values for maximum number of evaluations and the convergence
>> criteria.
>> The current design stems from the consideration that is "maxEval" is
>> reached, it means that something has gone wrong: it took more evaluations
>> than the _user_ was expecting.
>> If this check gets in the way (as suggested by MATH-902), the user can
>> always pass "Integer.MAX_VALUE", thereby disabling the safe-guard; but he
>> must accept that he might wait a long time...
>>
>> It would be easier to figure out which approach is correct if we could have
>> a concrete use-case.[1]
>>
>> The same issue also occurs with iterative linear solvers. I have concrete
> use-cases, in this instance. Some of the systems I try to invert are quite
> large (as in 128 * 128 * 128 * 6 unknowns). If the system is
> ill-conditioned and the requirements on the stopping criterion is too
> stringent, then the whole inversion will fail because of the maximum number
> of iterations being reached. Now, failure is so "brutal" (meaning: nothing
> is returned) that you can't even know how close the best estimate of the
> solution is to the true solution, so you don't even know how to alter the
> parameters of your solvers for failure not to happen again. Since these
> iterations take a long time, this is a bit annoying.
>
> With iterative solvers, there is a work-around, using the event handling
> that is provided, which allows access to the *current* estimate of the
> solution.
>
> So I agree with Phil that it would be nice to retrieve the "best" estimate
> of the solution, even if crash occurs. But I also agree with Gilles that
> this must be done carefully. All the iterative solvers implemented so far
> are almost state-less. The only class variables are related to the stopping
> criterion. No data relating to the current system being inverted is stored
> as a class variable (and is therefore not accessible). Again, event
> handlers might be the way to go, we could add an event which is fired prior
> to throwing the failure exception.
I like a lot the idea of registering user event handlers to be called
back by the solver at each iteration. This can be used to only overwrite
better solutions as they are found, but it also has many more usages
like displaying progress. This is what Nikolaus asked for when we
implemented CMAES. I'm not sure about the API though. Either we could
pass many parameters (number of iterations, current point and value) or
simply a reference to the optimizer, and add custom getters for each
optimizers, so the user could retrieve specific information when they
know which optimizer type they use and they can cast the refererence to
call algorithm-specific getters abnout the current state.
We already have something roughly similar to this in the ODE package. We
have both step handlers and events handlers, but they have slightly
differente meanings to what is desired here. Perhaps we should use a
name like IterationHandler to avoid confusion.
best regards,
Luc
>
> Best regards,
> Sébastien
>
>
> Regards,
>> Gilles
>>
>> [1] There is a similar situation with "CMAESOptimizer":
>> https://issues.apache.org/jira/browse/MATH-873
>> It behaves as the reporter of MATH-902 would like all optimizers to,
>> but it changes completely the meaning of "maxEval" (instead of a
>> safe-guard, it becomes a "normal" termination condition and the user
>> must check whether the convergence criteria have been met or not).
>>
>> ---------------------------------------------------------------------
>> To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
>> For additional commands, e-mail: dev-help@commons.apache.org
>>
>>
>
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org
Re: [math] Making last iteration data available when iterative
algorithms fail to converge (MATH-902)
Posted by Gilles Sadowski <gi...@harfang.homelinux.org>.
> > [...]
> >
> > So I agree with Phil that it would be nice to retrieve the "best" estimate
> > of the solution, even if crash occurs. But I also agree with Gilles that
> > this must be done carefully. All the iterative solvers implemented so far
> > are almost state-less. The only class variables are related to the stopping
> > criterion. No data relating to the current system being inverted is stored
> > as a class variable (and is therefore not accessible). Again, event
> > handlers might be the way to go, we could add an event which is fired prior
> > to throwing the failure exception.
>
> I think that a "framework" is indeed the flexible way but this is a lot of
> refactoring and not easy to get right as current attempts have shown.
> My preference is still to allow extensive logging in CM, as this helps with
> the presented uses-cases without getting in the way at all, and it's trivial
> to add.
>
> I'll try and to see the implications of just adding a "getCurrentBest()"
> method to the optimizers API.
Would it be OK to record one evaluated point per iteration?
[That seems to be a relatively non-intrusive change, but the value could
either be "null" or be worse than the starting point.]
Ensuring that the current best will always be returned entails changes
that will obscure the code: every call to "computeObjectiveValue" must be
enclosed in try/catch, catching the exception, setting the "current best"
then rethrowing. I still have the strong impression that it's working around
the current design (which is based on the user's knowing how to choose
"good" input values and exceptions indicating that it didn't work out.)
Best,
Gilles
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org
Re: [math] Making last iteration data available when iterative
algorithms fail to converge (MATH-902)
Posted by Gilles Sadowski <gi...@harfang.homelinux.org>.
On Sun, Nov 18, 2012 at 10:53:59AM +0100, Sébastien Brisard wrote:
> Hi,
>
>
> 2012/11/17 Gilles Sadowski <gi...@harfang.homelinux.org>
>
> > On Sat, Nov 17, 2012 at 12:34:30PM -0800, Phil Steitz wrote:
> > > I think MATH-902 makes a reasonable request, but I don't think the
> > > exception is the right place to communicate last iteration data.
> > > When iterative algorithms fail to converge and TooManyEvaluations or
> > > other iteration bounds exceptions are thrown, the request in
> > > MATH-902 is to make the last iterate available as a field in the
> > > exception. My inclination would be to not to do this, but instead
> > > to adopt the convention that the class doing the iteration should
> > > maintain last iteration state information.
> >
> > I understand the temptation to provide such a facility but it will make
> > the implementation more complicated (additional bookkeeping) than necessary
> > for the regular case, by which I mean that inputs were passed that don't
> > lead to failure.
> > Indeed, correct usage rests on the user, who is responsible for providing
> > compatible values for maximum number of evaluations and the convergence
> > criteria.
> > The current design stems from the consideration that is "maxEval" is
> > reached, it means that something has gone wrong: it took more evaluations
> > than the _user_ was expecting.
> > If this check gets in the way (as suggested by MATH-902), the user can
> > always pass "Integer.MAX_VALUE", thereby disabling the safe-guard; but he
> > must accept that he might wait a long time...
> >
> > It would be easier to figure out which approach is correct if we could have
> > a concrete use-case.[1]
> >
> > The same issue also occurs with iterative linear solvers. I have concrete
> use-cases, in this instance. Some of the systems I try to invert are quite
> large (as in 128 * 128 * 128 * 6 unknowns). If the system is
> ill-conditioned and the requirements on the stopping criterion is too
> stringent, then the whole inversion will fail because of the maximum number
> of iterations being reached. Now, failure is so "brutal" (meaning: nothing
> is returned) that you can't even know how close the best estimate of the
> solution is to the true solution, so you don't even know how to alter the
> parameters of your solvers for failure not to happen again. Since these
> iterations take a long time, this is a bit annoying.
>
> With iterative solvers, there is a work-around, using the event handling
> that is provided, which allows access to the *current* estimate of the
> solution.
>
> So I agree with Phil that it would be nice to retrieve the "best" estimate
> of the solution, even if crash occurs. But I also agree with Gilles that
> this must be done carefully. All the iterative solvers implemented so far
> are almost state-less. The only class variables are related to the stopping
> criterion. No data relating to the current system being inverted is stored
> as a class variable (and is therefore not accessible). Again, event
> handlers might be the way to go, we could add an event which is fired prior
> to throwing the failure exception.
I think that a "framework" is indeed the flexible way but this is a lot of
refactoring and not easy to get right as current attempts have shown.
My preference is still to allow extensive logging in CM, as this helps with
the presented uses-cases without getting in the way at all, and it's trivial
to add.
I'll try and to see the implications of just adding a "getCurrentBest()"
method to the optimizers API.
Best,
Gilles
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org
Re: [math] Making last iteration data available when iterative
algorithms fail to converge (MATH-902)
Posted by Sébastien Brisard <se...@m4x.org>.
Hi,
2012/11/17 Gilles Sadowski <gi...@harfang.homelinux.org>
> On Sat, Nov 17, 2012 at 12:34:30PM -0800, Phil Steitz wrote:
> > I think MATH-902 makes a reasonable request, but I don't think the
> > exception is the right place to communicate last iteration data.
> > When iterative algorithms fail to converge and TooManyEvaluations or
> > other iteration bounds exceptions are thrown, the request in
> > MATH-902 is to make the last iterate available as a field in the
> > exception. My inclination would be to not to do this, but instead
> > to adopt the convention that the class doing the iteration should
> > maintain last iteration state information.
>
> I understand the temptation to provide such a facility but it will make
> the implementation more complicated (additional bookkeeping) than necessary
> for the regular case, by which I mean that inputs were passed that don't
> lead to failure.
> Indeed, correct usage rests on the user, who is responsible for providing
> compatible values for maximum number of evaluations and the convergence
> criteria.
> The current design stems from the consideration that is "maxEval" is
> reached, it means that something has gone wrong: it took more evaluations
> than the _user_ was expecting.
> If this check gets in the way (as suggested by MATH-902), the user can
> always pass "Integer.MAX_VALUE", thereby disabling the safe-guard; but he
> must accept that he might wait a long time...
>
> It would be easier to figure out which approach is correct if we could have
> a concrete use-case.[1]
>
> The same issue also occurs with iterative linear solvers. I have concrete
use-cases, in this instance. Some of the systems I try to invert are quite
large (as in 128 * 128 * 128 * 6 unknowns). If the system is
ill-conditioned and the requirements on the stopping criterion is too
stringent, then the whole inversion will fail because of the maximum number
of iterations being reached. Now, failure is so "brutal" (meaning: nothing
is returned) that you can't even know how close the best estimate of the
solution is to the true solution, so you don't even know how to alter the
parameters of your solvers for failure not to happen again. Since these
iterations take a long time, this is a bit annoying.
With iterative solvers, there is a work-around, using the event handling
that is provided, which allows access to the *current* estimate of the
solution.
So I agree with Phil that it would be nice to retrieve the "best" estimate
of the solution, even if crash occurs. But I also agree with Gilles that
this must be done carefully. All the iterative solvers implemented so far
are almost state-less. The only class variables are related to the stopping
criterion. No data relating to the current system being inverted is stored
as a class variable (and is therefore not accessible). Again, event
handlers might be the way to go, we could add an event which is fired prior
to throwing the failure exception.
Best regards,
Sébastien
Regards,
> Gilles
>
> [1] There is a similar situation with "CMAESOptimizer":
> https://issues.apache.org/jira/browse/MATH-873
> It behaves as the reporter of MATH-902 would like all optimizers to,
> but it changes completely the meaning of "maxEval" (instead of a
> safe-guard, it becomes a "normal" termination condition and the user
> must check whether the convergence criteria have been met or not).
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
> For additional commands, e-mail: dev-help@commons.apache.org
>
>
Re: [math] Making last iteration data available when iterative
algorithms fail to converge (MATH-902)
Posted by Gilles Sadowski <gi...@harfang.homelinux.org>.
On Sat, Nov 17, 2012 at 12:34:30PM -0800, Phil Steitz wrote:
> I think MATH-902 makes a reasonable request, but I don't think the
> exception is the right place to communicate last iteration data.
> When iterative algorithms fail to converge and TooManyEvaluations or
> other iteration bounds exceptions are thrown, the request in
> MATH-902 is to make the last iterate available as a field in the
> exception. My inclination would be to not to do this, but instead
> to adopt the convention that the class doing the iteration should
> maintain last iteration state information.
I understand the temptation to provide such a facility but it will make
the implementation more complicated (additional bookkeeping) than necessary
for the regular case, by which I mean that inputs were passed that don't
lead to failure.
Indeed, correct usage rests on the user, who is responsible for providing
compatible values for maximum number of evaluations and the convergence
criteria.
The current design stems from the consideration that is "maxEval" is
reached, it means that something has gone wrong: it took more evaluations
than the _user_ was expecting.
If this check gets in the way (as suggested by MATH-902), the user can
always pass "Integer.MAX_VALUE", thereby disabling the safe-guard; but he
must accept that he might wait a long time...
It would be easier to figure out which approach is correct if we could have
a concrete use-case.[1]
Regards,
Gilles
[1] There is a similar situation with "CMAESOptimizer":
https://issues.apache.org/jira/browse/MATH-873
It behaves as the reporter of MATH-902 would like all optimizers to,
but it changes completely the meaning of "maxEval" (instead of a
safe-guard, it becomes a "normal" termination condition and the user
must check whether the convergence criteria have been met or not).
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org