SPSA improvements [RFC]

[ppigazzini]

Issue opened to collect info about possible future SPSA improvements.

SPSA references

SPSA is a fairly simple algorithm to be used for local optimization (not global optimization).
The wiki has now a simple documentation to explain the SPSA implementation in fishtest
Here is other documentation:

• SPSA seminal paper cited by @zamar in the forum
• SPSA website
• wikipedia SPSA page

SPSA implementation problems/improvements

• we ask for "c_k_end" and "r_k_end" (final parameters values), but IMO we should ask for for "c" and "r" (starting values) if those are too big the SPSA diverges
• we use "r_k = a_k / c_k^2" instead of "r_k = a_k" (I searched unsuccessfully a reference in some SPSA papers)
• we set "c_k_end" and "r_k_end" for any single variable to be optimized (the original SPSA uses global values): this makes sense to account for the different sensitivity of the variables, but IMO this should be dealt with an internal normalization of the variables values based upon the starting values and the bounds.
• one iteration should be set to a 2 games for match, but our worker code cannot support this, so we set one iteration to a 2*N_cores games for match
• compute an averaged SP gradient per iteration to lower the noise
• we have experimental code (special rounding and clipping) that nobody use: I'm afraid that it's theoretically correct but not very useful for the rough way we use SPSA
• "A" parameter should be computed from the number of games
• the worker passes rounded values to cutechess-cli: we should normalize the variables values to have the same resolution for all the variables

SPSA testing process (aka Time Control)

---

EDIT_000
this paragraph is outdated, I kept it to avoid disrupting the chain of posts:

• read the wiki for a SPSA description https://github.com/glinscott/fishtest/wiki/Creating-my-first-test#tuning-with-spsa
• the experience on these last years has shown that a very short time control on fishtest is not working:
  • with NNUE, workers running on dual CPU have time losses at ultra short time control (USTC)
  • that SPSA using or LTC or even ULTC has a high Signal/Noise ratio that helps the convergence. A ULTC match is very drawish, so in SPSA one side will win a pair of games only if the parameters random increments are somehow aligned with the gradient direction

---

I suggest this process to optimize the developer time and the framework CPU.

• first steps: run some SPSAs at Ultra STC (e.g. 1+0.01) to find good "c_k_end", "r_k_end" values and some good variables starting values. This can be done or locally with a recent CPU or in fishtest.
• last step: run a final SPSA in fishtest to optimize the variables for a longer TC (e.g. STC, 20+0.2, LTC etc.)

I took a SPSA from fishtest and run it locally changing only the the TC, the results are similar:

• 20+0.2 - original test on fishtest:
  https://tests.stockfishchess.org/tests/view/5e2dade6ab2d69d58394fb5e

• 2+0.02:

• 1+0.01::

• 0.5+0.01:

[MJZ1977]

From my experience on SPSA, the main problem is the high level of noise in the results. If any proposition reduce this noise, I agree with it :-)
You said :

"one iteration should be set to a 2 games for match, but our worker code cannot support this, so we set one iteration to a 2*N cores gamer for match"

Can we choose them number N ? Increase it specially. I think that below 100 games, the result can be completely wrong and lead to a bad convergence.

[ppigazzini]

@MJZ1977 the companion code of the seminal paper asks for the number of averaged SP gradients to be used per iteration. List updated, thank you :)

[ppigazzini]

The experimental options "careful clipping" and "randomized rounding" don't seems to have a first order effect, so we could keep only one method to clip and to round.

• careful clipping

• randomized rounding

• careful clipping + randomized rounding

[MJZ1977]

@ppigazzini : what are the effects of these options? did they change the number N of games before updating parameters ?

[ppigazzini]

@MJZ1977 "careful clipping" 7eebda7 and randomized rounding 5f63500 are theoretical improvements with little/no effect on SPSA convergence wrt other parameters. People stuck to default, so the GUI was simplified dropping the possibility to chose them. I will do some other tests and then I will simplify the code dropping the options not useful.

https://github.com/glinscott/fishtest/blob/5b07986dab3e638292cd04d6cf95d89d9959faeb/fishtest/fishtest/rundb.py#L599-L625

[linrock]

From what i'm finding online, alpha is usually 0.602, gamma at 0.101 is ok, and A is ~ 10% the number of iterations. would these be good defaults for the SPSA fields?

Sources:
https://hackage.haskell.org/package/spsa-0.2.0.0/docs/Math-Optimization-SPSA.html
https://www.ncbi.nlm.nih.gov/pmc/articles/PMC4769712/
https://www.chessprogramming.org/SPSA
https://www.jhuapl.edu/SPSA/PDF-SPSA/Spall_Implementation_of_the_Simultaneous.PDF

[vondele]

@linrock it makes definitely sense to have defaults for the fields (actually, I was thinking they had defaults...). Also @ppigazzini suggests to have A depend on the number of games. Shouldn't we call the field 'A[in %]' and give it a default of 10%, so that the field doesn't need to be adjusted when the number of games is changed ?

[linrock]

ah yea, i removed the SPSA defaults in the "create new test" redesign PR when all that should've been removed was the list of hard-coded params in the SPSA parameter list.

A as a percentage of # games makes sense. from what i'm reading, A is typically less than or equal to 10% the expected # of iterations (2 games per iteration). So maybe it could be either:

• A (% games) with default of 5%
• A (% iterations) with default of 10%

[xoto10]

Haha, in all this time I never realised that A was (/ should be) related to the number of games! :)

Regarding SPSA at very low tc, does that stress the server a lot because workers are continually returning small batches of data?

[ppigazzini]

@xoto10 the SPSA at very low tc can be also done locally :)

[vondele]

@linrock either percentage seems fine to me. Probably games, since we specify #games for SPSA and not number of iterations. In the future, I could imagine that an iteration contains more than 2 games (i.e. batching for SPSA, @vdbergh?), to reduce server load, and because it presumably makes sense (but I don't know the SPSA details).

[vdbergh]

@vondele I am working on a small PR to allow the server to set a batch_size. It is mainly for sprt but it will also work for spsa and fixed games although for those one may consider leaving it to the worker. We can see.