[mlpack] CMA-ES and LMCMA, GSOC and Gym

[Ryan Curtin]

On Thu, Apr 08, 2021 at 02:12:10PM +0200, Oleksandr Nikolskyy wrote:
> Hi Marcus,
> 
> I've found at least one error in the CMA ES implementation in ensmallen:
> 
> in line *209* and *214* where *p_sigma* is computed, the choleski factor of
> the covariance matrix is used, while the original algorithm takes the
> inverse root of the covariance matrix.  (eq *44*, page *29* in the tutorial
> https://arxiv.org/pdf/1604.00772.pdf ). What is the best way to compute
> A^(-1/2) = BD^(-1)B^T in armadillo?

Hey Oleksandr,

Are you sure that this is a problem?  Using the Cholesky factorization
is a valid way to compute an inverse.  I took a look through the code
though and you may be right---it seems that we are using L^T (for LL^T =
C) where instead we should be using, e.g., (L^-1) * (L^-1)^T.  Maybe
Marcus can say more; I haven't spent too much time with the CMAES code.

Also, I noticed a while loop that adds to the diagonal in case the
Cholesky factorization fails... this can be a little bit scary, because
there can be situations where you spend very long here (or where it
becomes effectively an infinite loop).  It may be worth changing that
strategy a bit to have a maximum number of attempts or something.

> Also, I have implemented the LM CMA (https://arxiv.org/abs/1511.00221),
> I've tested it on learning cartpole and rosenbrock.
> It outperforms CMA ES on rosenbrock in terms of computation time with 1000
> params. I'd love to contribute it to ensmallen.

That sounds great!  If you'd like to open the PR I will to try to review
it when I have a chance (or maybe someone else will beat me to it).

> Btw I am really sorry to be so late with my proposal. I hope to upload it
> tonight, hope it is still OKay.

It's not late, the deadline is still several days away. :)

Thanks for pointing this potential issue out!

Ryan

-- 
Ryan Curtin    | "Bye-bye, goofy woman.  I enjoyed repeatedly
ryan at ratml.org | throwing you to the ground." - Ben Jabituya