SPSA problems

[jdart]

What kind of chess evaluation function could have multiple local extrema?

You are not directly optimizing the evaluation function itself, but the result of games played with the evaluation function. So that is a more complex function of the parameters. It is pretty easy to get multiple local optima, especially if you have evaluation parameters that are redundant in some sense.

Finding the global optimum of a non-linear function is a very difficult problem, in fact there is a "no free lunch" theorem (https://en.wikipedia.org/wiki/No_free_l ... timization), which indicates that there is no single optimal algorithm for it. The difficulty increases substantially as the number of parameters increases.

[BeyondCritics]

Thanks for your answer!
...
What kind of chess evaluation function could have multiple local extrema?

If you have a sufficient complex parameter space, where it always would be possible to have something better than random evaluation, then you would have very likely myriads of local extrema. Local extrema are the norm in machine learning, not something you have to ask for.

If you have a feature that needs only one parameter, but you use two for it, then you have presumably introduced an ambuigity which in turn leads to multiple extrema, hampering convergence. The typical precaution would be parsimony in the parameter space.

Isn't it possible to find a global optimum if I choose a high ck?

Not really. ck controls the resolution of your learning. If you set it to high, you may experience convergence problems, except where your problem is well behaved. Make ck too low and you will see nothing but draws, when you don't want to have them. I would make it as high as possible, but not higher.

If you want to control exploration, A and alpha are the parameters to consider. You can lower A or increase alpha, the latter is allegedly dangerous.