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

[Mathieu De Craene]

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