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.

[MJZ1977]

@ppigazzini : I am trying to understand how SPSA code is working and my knowledge is very weak. Nevermind, I am trying.
In the file rundb.py, I find the following:

    # Generate the next set of tuning parameters
    iter_local = spsa['iter'] + 1  # assume at least one completed,
                                   # and avoid division by zero
    for param in spsa['params']:
      c = param['c'] / iter_local ** spsa['gamma']
      flip = 1 if random.getrandbits(1) else -1
      result['w_params'].append({
        'name': param['name'],
        'value': self.spsa_param_clip_round(param, c * flip,
                                            spsa['clipping'], spsa['rounding']),
        'R': param['a'] / (spsa['A'] + iter_local) ** spsa['alpha'] / c ** 2,
        'c': c,
        'flip': flip,
      })
      result['b_params'].append({
        'name': param['name'],
        'value': self.spsa_param_clip_round(param, -c * flip, spsa['clipping'], spsa['rounding']),
      })

    # Update the current theta based on the results from the worker
    # Worker wins/losses are always in terms of w_params
    result = spsa_results['wins'] - spsa_results['losses']
    summary = []
    w_params = self.get_params(run['_id'], worker)
    for idx, param in enumerate(spsa['params']):
      R = w_params[idx]['R']
      c = w_params[idx]['c']
      flip = w_params[idx]['flip']
      param['theta'] = self.spsa_param_clip_round(param, R * c * result * flip,
                                                  spsa['clipping'],
                                                  'deterministic')
      if grow_summary:
        summary.append({
          'theta': param['theta'],
          'R': R,
          'c': c,
        })

My questions are:

• is "w_params / b_params" corresponding to "white / black parameters". If this is true, why always making "+c" for white and "-c" for black ? What I had understood is that we should make a couple of games with black and white alternating "+c/-c" and "-c/+c" ?
• in the second part "update_spsa", the gradient is calculated from wins/losses from last results. Are the results corresponding to a specified number of games for a worker (like 200 in SPSA tests), or just for a couple of games? Within the worker, is black/white alternating ? we should have something like
  engine1(+c) - engine2(-c)
  white - black
  black - white
  with the same opening ?

And sorry for these "technical questions" ...

Update : latest version of code

[vondele]

@MJZ1977 I think it is great somebody is looking at the implementation of SPSA. I'm still puzzled why our tuning attempts have such a low success rate (@linrock recent experience). I do think we need a very large number of games, as the Elo difference we're looking for are so small, and the parameters of SPSA are not obvious or automatic, but I also think we need to critically audit the actual implementation, just in case.

[tomtor]

@MJZ1977 You should also look at the worker code to get the complete picture, at and below this line
https://github.com/glinscott/fishtest/blob/db94846a0db8788fe8a8724678798dcc91d201e8/worker/games.py#L386

See https://github.com/zamar/spsa for the original implementation

[tomtor]

• Are the results corresponding to a specified number of games for a worker

@MJZ1977 A worker plays batches of 2*N-CPU games (white/black alternating) and requests a parameter update from the server after every batch.

[ppigazzini]

@vondele SPSA claims to minimize the number of function evaluations. Classic SPSA evaluates the function only at "variables_values_k+delta; variables_values_k-delta" for the gradient estimation, so SPSA obviously diverges with wrong delta. This is why I suggest to test locally the SPSA parameters with USTC before submitting to fishtest.

The one side SPSA computes the gradient with "variables_values_k+delta; variables_values_k", so having a CPU cost free function evaluation with variable_value_k it's possible to implement:

• a policy to reset the variables value upon some conditions (like done with extra CPU cost in the paper linked by @linrock)
• a policy to accept delta only if f(variables_values_k+delta) > f(variables_values_k) (for the maximization problem)

Neither policies can guarantee the convergence with bad delta, though. SPSA (and all gradient descent algorithms) works only to refine the starting values within the starting basin, to find better local maxima we should switch to global optimization algorithms based on function evaluations (Nelder-Mead, genetic etc.) to explore the space variables.
https://en.wikipedia.org/wiki/Global_optimization

[MJZ1977]

@tomtor : thank you for the links !
Update : removed

[vondele]

@ppigazzini concerning Nelder-Mead, I did work on interfacing cutechess games to the nevergrad suite of optimizers : https://github.com/vondele/nevergrad4sf and picked TBPSA which seems to be the recommended optimizer for noisy functions. I found it robust if given enough games (millions literally). Unfortunately, the optimized parameters seem very good at the TC they have been optimized (VSTC), but not transferable. Since I can't optimize at STC or LTC, it would need to be integrated in fishtest.... but I'm not able to do that (time and experience with the framework lacking atm).... if somebody wants to pick it up, I would be happy to help.

[MJZ1977]

After making some tests, I think that one of principal problems is that the random parameter "flip" is only taking values +1 or -1 (please correct if I am wrong). So basically, fishtest always tries to change all variables at the same time.
One improvement can be to take flip values from [+1, +0.1, -0.1, -1] for exemple. It corresponds to random division by 10. In this case, we will have some tests with only 1 or 2 variables changing.
I think it is also easy to implement even if I don't have the knowledge to make it !

[xoto10]

If we want to tune 1 constant, it would be nice if tuning could simply test the start value and N values either side (3? 5?) and then display a bar chart of the resulting performance. That might give us an easy to read clue as to whether there's a trend in in which values are better.
We tend to do this manually atm but it seems easy for the tuner to do?

[ppigazzini]

@MJZ1977

So basically, fishtest always tries to change all variables at the same time.

SPSA = Simultaneous perturbation stochastic approximation

One improvement can be to take flip values from [+1, +0.1, -0.1, -1] for exemple. It corresponds to random division by 10. In this case, we will have some tests with only 1 or 2 variables changing.
I think it is also easy to implement even if I don't have the knowledge to make it !

Random [+1, -1] is the Rademacher distribution, you can use other distributions, but the result IMO will not change: we can get good fishtest gains from SPSA only for bad tuned parameters or when SPSA finds for serendipity a new local maximum.

SPSA, like other gradient algorithms, it'a a local optimization, useful to refine the starting values "without hopping from the starting basin".

@xoto10 you are talking about a global optimization algorithm, take a look to the @vondele work.

[vondele]

while the TBPSA might also work for global optimization (that's always hard), I don't think we're typically stuck in local minima. At least, I have never seen evidence of that. TBPSA seems to be just rather good of doing the right thing in the presence of noise, also in (a relatively small) number of dimensions. @xoto10 the bar chart will tell almost nothing in most cases, unless we do on the order of 240000 games per point (that's roughly 1Elo error, i.e. the typical gain from a tune).

I once did a scan of one parameter for one of the search parameter, and the graph is somewhere in a thread on github, which I can't find right now, and it looks like this:

[ppigazzini]

I don't think we're typically stuck in local minima. At least, I have never seen evidence of that.

In that case (a proper implemented) SPSA should be able to find a better value, but in my first post I collected all my doubts about our SPSA implementation.

A simple proof is to set a blatant wrong value for a parameter (eg. Queen = 0.1 pawn, sorry I'm not a SF developer :) and view if our SPSA is able to recover a good value.

[MJZ1977]

I made some tests since yesterday and come to the conclusion that SPSA is not working well actually because of too much noise in individual results.
As an example to explain my thought, I take this simple example
SPSA beginning with KnightSafeCheck = 590
https://tests.stockfishchess.org/tests/view/5ea9b5c469c5cb4e2aeb82fd
SPRT master vs KnightSafeCheck = 590
https://tests.stockfishchess.org/tests/view/5eaa93b769c5cb4e2aeb8370
The best value should be KnightSafeCheck = ~790 like in master. SPSA is oscillating even if it seems increasing at the end.
I use only 1 variable to avoid any bias.

The only solution to this is to make iterations for at least 200 games instead of 2N games.
For example if the results are 60-40-100, it gives +20 to multiply by the same gradient. It is very different from multiplying "60" and "-40" by different gradients which clearly increases the noise. This is my opinion but I cannot be sure without making tests which are impossible now.

An improvement can be to add an SPSA parameter = minimum number of games per iteration instead of the default 2N

[vdbergh]

@vondele Some parameters naturally have only a discrete set of values. E.g. depth.

I have been reading the Fishtest rounding and clipping code and it does more or less the right thing in the sense that it will not put rounded values in its data base. So a parameter will not get stuck at a particular value due to rounding.

It might be good though to reenable stochastic rounding for the integer parameters that are actually sent to the worker. I don't see any drawback to that.

[ppigazzini]

It might be good though to reenable stochastic rounding for the integer parameters that are actually sent to the worker. I don't see any drawback to that.

Stochastic rounding should have a practical effect only with a wrong parameter scaling or bad hyper parameters.

[vdbergh]

@ppigazzini Why do you say this? I am mainly thinking of parameters which are naturally integers like depth. There is no benefit in replacing depth by 10*depth.

The SPSA algorithm fundamentally deals with real numbers and stochastic rounding is an elegant 1-line trick for combining real numbers and integers.

[ppigazzini]

@ppigazzini Why do you say this? I am mainly thinking of parameters which are naturally integers like depth. There is no benefit in replacing depth by 10*depth.

Ops, errata corrige "wrong parameter scaling", "wrong parameter range/scale"

If depth range is [80,81] I think that the right way is to run 2 SPSAs (with depth=80 and depth=81) to optimize the other parameters.

If depth range is [0,160] I don't think that stochastic rounding has an effects wrt deterministic rounding on the SPSA convergence.

I don't view drawbacks in the stochastic rounding, but the most important thing is to have a good SPSA guideline to avoid to wast CPU resources.

[vdbergh]

@ppigazzini Those are extreme examples. I was more thinking of intervals like [5,10].

I am not sure actually if stochastic rounding provides any benefit at all. But it kind of avoids one having to think about the issue.

[ppigazzini]

@ppigazzini Those are extreme examples. I was more thinking of intervals like [5,10].

I am not sure actually if stochastic rounding provides any benefit at all. But it kind of avoids one having to think about the issue.

Stochastic rounding is fine, but I fear a dev that avoid to think before submitting a SPSA :)

[vdbergh]

I started writing some javascript.

Currently I am bit stressed out about the draw ratio. The draw ratio can be measured dynamically but this requires changing things on the server side. Probably it is best to start with only client side changes.

On the client side we can make a reasonable guess about the draw ratio starting from the time control (i.e. interpolating). This would depend on the book, but the book does not change very often. So that should be ok.

But then there is nodestime :( :( I don't really want to think about nodestime. AFAIK its benefit has never been demonstrated and so I am tempted to just disable it when using the alternative algorithm.

[vondele]

I'd take any reasonable draw ratio (typical STC or LTC values)... at this point nothing too advanced.

[vdbergh]

The effect of the draw ratio on the required number of games is too big to ignore unfortunately. But the following simple function predicts the draw ratio within 1% accuracy from VSTC to LTC.

function draw_ratio(tc){
    /* 
       Formula approximately valid for the book "noob_3moves.epd".
    */
    const slope=0.372259082112;
    const intercept=0.953433526293;
    var tc_seconds_log=Math.log(tc_to_seconds(tc));
    return logistic(slope*tc_seconds_log+intercept);
}  

Disclaimer. The fit was based on only 4 data points. 1+0.01, 10+0.1, 20+0.2 and 60+0.6.

[vdbergh]

Just checked a 120+1.2 test and the function still gave the right answer (0.79).

[MJZ1977]

Can we please increase the batch size from 2N to 4N or 8N ?

• is it difficult?
• it seems to me that it has no drawbacks,
• it will significantly increase throughput,
• it will (perhaps) give some convergence stability.

[vondele]

bench or batch?

[MJZ1977]

batch, sorry ! I correct it

[linrock]

anything you guys think is particularly worth implementing based on this massive discussion so far? i'm happy to help either improve SPSA or introduce another optimizer (i.e. nevergrad)

[ppigazzini]

@linrock @vdbergh @vondele I propose:

• to make default the "stochastic rounding" 5f63500 and drop the normal rounding code
• to drop the "careful clipping" code 7eebda7

[vondele]

I don't have enough knowledge to suggest one option or another, I'm fine with what the experts suggest to be the default.

Note that this thread has lead to optionally new defaults for SPSA.

Also with the merge of NNUE, I expect there will be fewer SPSA tunes... even there is potential there as well.

[MJZ1977]

@linrock : if you can increase the batch size from 2xN to 4xN or make it an option it will be great !

[xoto10]

A question about SPSA; is it possible to incorporate the draw rate into the parameter optimisation, i.e. obviously have wins-losses as the main target, but also prefer a lower draw rate ?

[vondele]

SPSA could optimize another objective function. Right now, it optimizes the score of the match (i.e. Elo), you could have it optimize something else, in principle. Imagine you have (w,l,d) what formula f(w,l,d) would you optimize?

[xoto10]

I was thinking that the objective function was (something like) W-L, but reading your comment and a quick bit of the wikipedia Elo page suggests that the objective function is perhaps W + 0.5 * D ? (Which I should have guessed at / known to start with)

If so, can we reduce the draw weighting with the idea that this would encourage a more aggressive style of play ? It would be interesting if spsa runs can be parameterized to allow this so that we could try some tests. (Well, it seems like an interesting possibility to me - happy to be corrected :-)

[vondele]

yes, probably one could us e.g. 'w + 0.4 * d' and one would effectively optimize something like contempt. One could similarly do SPSA with the current objective function, but use e.g. time-odds (so optimize scores against a weaker player). I locally played with that, but without much success. It would presumably become even more difficult to have patches pass after such an SPSA tune, since our SPRT tests measure strength, and it seems contempt goes against that....

[xoto10]

Hmmm. I tend to think in terms of w-l being the ultimate aim, but because the 3 variables are linked I think this is equivalent to w+0.5d (not surprising I guess, it would be strange if years spent optimizing for w+0.5d were not actually aiming at the best target!)

W  L  D   w-l  w+0.5d
20 10 70  +10    55
15  5 80  +10    55

W  L  D   w-l  w+0.4d
19 11 70   +8    47
15  5 80  +10    47

So optimizing for w+0.5d makes +20-10 equivalent to +15-5. Changing to w+0.4d would make +19-11 equivalent to +15-5 ! So it would be as happy with +8 instead of +10 because of the 10 extra decisive games. Hmmm. Maybe 0.49 :)

I would want w-l to be the most important, but lower draw rates to be preferred if w-l values are the same. So perhaps include the draw rate in the fractions, e.g. w+0.5d-f where f = d/(w+l+d)/2 so that f cannot be more important than the main part of the formula.

W  L  D   w-l  w+0.5d-f
20 10 70  +10  55-0.35 = 54.65
15  5 80  +10  55-0.40 = 54.60

This would give a slight preference to the +20-10 result compared to the +15-5 one.

[xoto10]

Thinking some more, I think there are 2 slightly different angles here, aggressive play against strong players and aggressive play against weaker players. The difference is mainly one of degree, against weaker players we can play definitely sub-par moves if the gain in winning chances is good enough, while against strong players we need to still play good moves even if we're trying to choose more aggressive ones.

Currently I'm more interested in the aggression against strong players, e.g. in self-play, the aim being to get a more aggressive play style and a slightly lower draw-rate. This has the advantage that we can just test against master, we don't need all that complication of testing against weaker players. I'm assuming this would work out well against weaker players anyway :-)

Looking at rundb.py, line 983 does :
result = spsa_results["wins"] - spsa_results["losses"]
it would be nice if we could modify that to something like

    result = spsa_results["wins"] - spsa_results["losses"] \
            - X * spsa_results["draws"] \
            - Y * spsa_results["draws"] / (spsa_results["wins"] + spsa_results["losses"] + spsa_results["draws"])

where X and Y are parameters to the test run - would that work?