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

[Stefan Klein]

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.


>(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.


-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://public.kitware.com/pipermail/insight-users/attachments/20050627/57c3ffdd/attachment-0001.html