<html>
<body>
<font size=3>Hi Zach, <br><br>
Thanks for your careful review of this code :)<br><br>
<br>
<blockquote type=cite class=cite cite>(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.<br><br>
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:<br>
StateOfConvergence <= DecayRate * (StateOfConvergence + LearningRate *
GradientMagnitude)<br><br>
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!)</font></blockquote><br>
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.
<br><br>
Would the following test be better maybe?:<br><br>
If ( (newPosition - currentPosition).magnitude() <
m_SomeUserEnteredThreshold )<br>
{<br>
m_NumberOfVerySmallSteps++;<br>
if (m_NumberOfVerySmallSteps >=
m_UserEnteredMaximumNumberOfVerySmallSteps)<br>
{<br>
this->StopOptimization();<br>
}<br>
}<br>
else<br>
{<br>
m_NumberOfVerySmallSteps = 0;<br>
}<br><br>
The parameters to set are maybe more intuitive in this way.<br><br>
<br>
<blockquote type=cite class=cite cite><font size=3>(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.<br><br>
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.<br>
</font></blockquote><br>
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!<br><br>
Kind regards,<br>
Stefan.<br><br>
</body>
<br>
</html>