[Insight-users] Re: ITK SPSA optimizer: StateOfConvergence question and SetScales bug.

Tue Jun 28 13:21:40 EDT 2005

Hi,

>As for the termination criteria, I agree that it sounds like a great idea 
>to have a stable of callbacks that people could attach to any optimizer to 
>achieve their desired termination criteria. This would be much better than 
>the current situation.

I like this idea as well.

>Given that that's in the future, do we want to do anything about the 
>termination condition as it exists now in the SPSA code? (Even something 
>as minimal as providing a reference to where a scheme like the 
>StateOfConvergence stuff is described, so users could read something for 
>guidance would be valuable.)

Maybe it would be better to just remove this whole convergence check and 
only terminate when the maximum number of iterations has been reached. It 
will save us from some parameters to choose. :)

Stefan.

>For my use, I'll probably just attach an observer and equip it with 
>whatever termination condition I need.
>
>Zach
>
>On Jun 27, 2005, at 7:34 AM, Mathieu De Craene wrote:
>
>>Le Monday 27 June 2005 à 13:32 +0200, Stefan Klein a écrit :
>>>Hi Zach,
>>>
>>>Thanks for your careful review of this code :)
>>>
>>>
>>>>(1) The convergence test is a bit unfamiliar to me. Since it's not
>>>>what is described in Spall's papers on SPSA, reading them didn't
>>>>help clarify matters.
>>>>
>>>>In general, I'm familiar with convergence tests that look at how
>>>>much the value of the objective function has changed, or how much
>>>>the parameters have changed, or how close the gradient magnitude is
>>>>to zero. However, the "StateOfConvergence" test in the SPSA class is
>>>>more unclear. Optimization terminates if StateOfConvergence is less
>>>>than some threshold, where StateOfConvergence starts at zero and is
>>>>updated as follows:
>>>>StateOfConvergence <= DecayRate * (StateOfConvergence + LearningRate
>>>>* GradientMagnitude)
>>>>
>>>>Could anyone give some guidance as to why this criteria was chosen
>>>>over more simplistic tests such as mentioned above, and how to
>>>>choose the threshold and decay rate parameter appropriately?
>>>>(Naively, it seems that if the gradient starts large and then goes
>>>>to zero, optimization could continue for some time as the "state of
>>>>convergence" parameter decays, even though the optimum has already
>>>>been found. Likewise, if the decay rate is too large, optimization
>>>>could be terminated prematurely. Thus, choosing the right decay rate
>>>>seems very important, but it is not clear how best to do so!)
>>>
>>>Good question. I copied this part from Mathieu's code, so he may be
>>>better able to answer this question. The problem of 'traditional'
>>>convergence tests is that they stop if the test has been satisfied
>>>once. In stochastic optimisation it is not unlikely that in one
>>>iteration a zero gradient is measured, but in the next iteration still
>>>progress is being made. Moreover, the gradient magnitude does not
>>>always cancel at the optimum (due to the stochasticity; that's why the
>>>decreasing gain sequence is needed). Mathieu's method tries to attack
>>>this problem, but I do agree now that the parameters are quite hard to
>>>choose properly.
>>>
>>>Would the following test be better maybe?:
>>>
>>>If ( (newPosition - currentPosition).magnitude()  <
>>>m_SomeUserEnteredThreshold )
>>>{
>>>   m_NumberOfVerySmallSteps++;
>>>   if (m_NumberOfVerySmallSteps >=
>>>m_UserEnteredMaximumNumberOfVerySmallSteps)
>>>   {
>>>      this->StopOptimization();
>>>   }
>>>}
>>>else
>>>{
>>>   m_NumberOfVerySmallSteps = 0;
>>>}
>>>
>>>The parameters to set are maybe more intuitive in this way.
>>
>>I have to confess that in my experiments, the convergence test always
>>fails (for a registration application I mean) and the optimizer performs
>>the maximum number of steps specified by the user. On synthetic cost
>>functions however, it works well. My only conclusion is that this might
>>not be the best test for noisy cost function such the ones we play
>>with ;-) I like the scheme suggested by Stefan.
>>
>>In fact, this discussion is not specific to spsa... Maybe it would be
>>better on a general point of view to use an observer on the optimizer so
>>that the user can call the StopOptimization() method when his own
>>convergence criterion is satisfied.  This is more a question for ITK
>>designers... Having a lot of various convergence tests embedded in
>>different optimizers is not so modular.
>>
>>>
>>>>(2) I think that there might be a bug in how the Scales parameter is
>>>>used to scale the perturbations and the gradient value. I've read
>>>>the email thread from a few months ago concerning this, but I think
>>>>there's a bug in the implementation that breaks this slightly.
>>>>
>>>>The logic for dealing with the scaled delta (perturbation) values,
>>>>as commented at the bottom of the ComputeGradient() method in
>>>>itkSPSAOptimizer.cxx (lines 414-451), assumes that scaling is
>>>>accomplished by dividing by sqrt(Scales). This sqrt(Scales) term
>>>>eventually is transferred to a numerator, and thus to correct for
>>>>that (i.e. put the scaling term back in the denominator where it
>>>>belongs), the comment suggests an additional division by Scales.
>>>>However in the actual code, the scaling is done (as it should be!)
>>>>by dividing by Scales. However, in the code the correction remains
>>>>an additional division by Scales, when it should be by Scales^2 (as
>>>>per the logic in the comment). Thus, the scaling factor winds up
>>>>being canceled out entirely, instead of being transfered from a
>>>>numerator to a denominator as a division by Scales^2 would properly
>>>>do.
>>>
>>>You are very right. If you use sqrt(Scales) you should divide by
>>>Scales later; if you use Scales, you should use Scales^2 later. I was
>>>in a doubt whether to use the first or second option; i forgot why I
>>>chose for the first option, but the second option (that you propose
>>>now) indeed gives the desired scaling, so is better!
>>>
>>>Kind regards,
>>>Stefan.
>>>
>>
>>I am a bit perplex about how we have to deal with scales... As far as I
>>understand, we could always use Scales of 1 for each parameter and adapt
>>the transformation for having parameters evolving in the same range...
>>That's how I deal with Scales in my rigid registration code... But I
>>know this is not the ITK way of seeing things. Sometime, a linear
>>mapping of the parameters space is not the best thing to do : when
>>optimizing the parameters of an affine transformation, it's good to have
>>the x,y and z scaling factors evolving from -inf,+inf instead of 0,+inf.
>>So a logarithmic mapping of these parameters is a good trick...
>>
>>Is there a gradient descent optimizer in ITK where the gradient is
>>estimated using finite differences ? It could give us some inspiration
>>no ?
>>
>>Math.
>>
>>--
>>Mathieu De Craene <decraene at tele.ucl.ac.be>
>>010 47 93 53 - 0478 51 54 54 (cell) - 010 47 20 89 (fax)
>>http://www.tele.ucl.ac.be/~decraene
>>
>>_______________________________________________
>>Insight-users mailing list
>>Insight-users at itk.org
>>http://www.itk.org/mailman/listinfo/insight-users

-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://public.kitware.com/pipermail/insight-users/attachments/20050628/7d374d7f/attachment.html