root-project
How to improve MnScan in Minuit2?
For the next major release of iminuit, I finally implemented the ability to scan the function for a minimum using a brute-force grid search in N dimensions. This is very inefficient, but still a feature that users regularly request and there has been an open issue in iminuit about it for a long time, now closed.
Originally this was supposed to use MnScan from C++ Minuit2, but I found some severe problems with MnScan. I would like to discuss what we want MnScan to do, then I would be happy to work on a patch.
What MnScan currently does
It does a 1D scan with 41 steps for each parameter in sequence, so it is not actually scanning the full hypercube. It first scans one parameter, then starts the scan of the second parameter from the best value of the first and so on. Instead of a full 2D scan, it does something like this:
y
B
y
xxxxxxxxxxxxxxxxxx A xxxxxx
y
y
where A and B are the minima along the x and y axis respectively. This approach has the advantage that the number of function evaluations scales like with k * n, where k is the number of dimensions and n the number of steps per dimension, while a full grid search scales like n ^ k. However, this approach will fail miserably when x and y are correlated, trying this on the Rosenbrock function for instance gives terrible results (basically no improvement with respect to the starting value).
What to do?
The current behavior of MnScan is not what people usually consider a scan, which most people understand as a full grid search over the whole N-dimensional space. It seems that MnScan is not really used in ROOT, but I may be mistaken.
If it is not really used, I would suggested to keep the name MnScan and change the implemenation to do a full hypercube scan. I am strongly convinced that MnScan should do a full grid search instead of what it currently does, because the current implementation is fairly pointless for most real-world functions which have correlations.
If MnScan has a use case that I am not aware of, then I propose to add a new Minimizer, MnHyperScan (or similar name), which implements the full scan.
Other issues with current MnScan
- One cannot configure the number of steps taken per dimension when MnScan is called through the minimizer interface (MnApplication). The maxcalls option should be used for this.
- A gradient and second derivatives are computed for the starting values, only to be discarded. This is wasteful.
- The scan returns EDM = 0, which is very misleading. It should either return inf or NaN, to indicate that the EDM is invalid. Ideally, a proper EDM should be calculated for the obtained minimum after the scan.
- MnScan always builds a vector of all the (parameter, function value) pairs obtained during the scan, but that vector is discarded after the run. This is wasteful.
I am very happy to work on this to move the iminuit functionality upstream into Minuit2, but these questions need to be resolved first.
Hi @HDembinski! Minuit2 is undergoing some modernization and improvements now, and we would love to implement this by up-streaming your developments.
Do you have any advice or requests before we go ahead with this? It seems that you have already answered all the questions yourself, by defining a good example in iminuit, no?
In iminuit, when the user calls "scan", it runs a scan like I proposed here. The implementation is in Python, but that code is easy to translate to C++. I could try that and make a PR if you have a bit of patience. Otherwise, if you want to work on it then I suggest to have a look at the scan method in the iminuit.Minuit class to inspire your implementation.
Hi! Thanks for your reply. For now, I haven't found anyone in the ROOT team to work on this, so for the 6.34 release it's not going to happen. So I am patient :slightly_smiling_face:
What I want to focus on instead is to give the Fumili minimizer in Minuit2 some love, also trying it with RooFit. This should be beneficial for binned likelihoods