NMinimize stops using CPU but still evaluating

Question

I have a problem where I launch this code in NMinimize and after a minute, the CPU usage of Mathematica drops to 0. The notebook still shows as evaluating.

Here's some context and explanation of my code. I am trying to fit the accuracy data obtained from a cognitive task. I first show l letters to a participant, then another set of l letters out of which d are different from the first set of letters. For example, showing ABCD followed by AECF is l = 4, d = 2. Participants answer "same" if they think all the letters match, and "different" if at least 1 letter mismatches.

Matching letters are encoded as 1 and mismatching letters as -1. If all letters are considered to be matching, then the sum of all letters will be l and the participant will answer "same". This will result in a correct answer when d = 0. Conversely, if the total is not l, then the participant will answer "different", which is a correct answer if d > 0.

I'm testing whether noise during different steps of the cognitive process could explain the accuracy of participants. My function has 4 parameters, each indicating a probability that noise will interfere (real numbers between 0 and 1). After making sure NMinimize does not use invalid values (constraints don't work as "hard constraints"), I compute the expected accuracies for all types of trials with up to 4 letters (a total of 14 conditions). I then give the result of my objective function, which is how far from the real data each calculated accuracy is, plus a penalty that favorizes smaller differences at the cost of a larger global offset.

Clear[fNumericalToFit]
fNumericalToFit[Pe_Real, Pt_Real, Prs_Real, Prd_Real, iN_Integer: 10000] :=

Block[{bProbTotal,bMAsM,bMAsD,bNormalAnswer,bAcc,bErrMism,bErrMatch,bScore},

(* Verify that NMinimize does not use invalid values *)
bProbTotal = Total[Which[
    # < 0, -100*#,
    # > 0.2, 100*(# - 0.2),
    True, 0] & /@ {Pe, Pt, Prs, Prd}];

If[bProbTotal > 0, Return[bProbTotal]];

bMAsM = (1 - Pe)*(1 - Pt) + Pe*Pt; (* Prob of a match being interpreted as match *)
bMAsD = (1 - Pe)*Pt + Pe*(1 - Pt); (* Prob of a match being interpreted as mismatch *)
bNormalAnswer = (1 - Prs - Prd); (* Prob of not making a biased answer *)

bAcc = ParallelTable[
    Which[
        d == 0, 
        bErrMatch = RandomChoice[{bMAsM, bMAsD} -> {1, -1}, {iN, l}].ConstantArray[1, l];
        (Count[bErrMatch, l]/iN)*bNormalAnswer + Prs,

        d == l,
        bErrMism = RandomChoice[{1 - Pt, Pt} -> {1, -1}, {iN, d}].ConstantArray[-1,d];
        (1 - Count[bErrMism, l]/iN)*bNormalAnswer + Prd,

        True,
        bErrMism = RandomChoice[{1 - Pt, Pt} -> {1, -1}, {iN, d}].ConstantArray[-1,d];
        bErrMatch = RandomChoice[{bMAsM, bMAsD} -> {1, -1}, {iN,l - d}].ConstantArray[1, l - d];
        (1 - Count[bErrMism + bErrMatch, l]/iN)*bNormalAnswer + Prd],
    {l, 4}, {d, 0, l}];

  bScore = Abs[Flatten[bAcc] - {0.97`, 0.971`, 0.96`, 0.955`, 0.975`, 0.955`, 0.909`, 0.97`, 0.975`, 0.947`, 0.785`, 0.945`, 0.973`, 0.983`}];
  Total[bScore] + 2*Max[bScore]
  ]

Does anyone have a clue why running this function in NMinimize results in not using any CPU after a minute while still evaluating?

NMinimize[fNumericalToFit[EncodeErr,TestErr,RespSame,RespDiff],{EncodeErr,TestErr,RespSame,RespDiff}]

Answer 1

Even with ParallelTable replaced by Table, as suggested by MarcoB, the code in the question has two significant issues.

• First, fNumericalToFit returns bProbTotal or bScore, depending on its input parameters, and the values of these two quantities typically are quite different. Depending on what region of parameter space NMinimize begins in, it will minimize one or the other of bProbTotal or Total[bScore] + 2*Max[bScore]. It happens that, for the code as written, it attempts to minimize bProbTotal, which is not the desired quantity.
• Second, if NMinimize does try to minimize Total[bScore] + 2*Max[bScore], it cannot converge, because the evaluation of bScore involves random numbers, which change from one call to the next. It can, however, obtain a rough minimum in some cases.

To illustrate the first issue, replace If[bProbTotal > 0, Return[bProbTotal]] by If[bProbTotal > 0, Sow[bProbTotal, bP]; Return[bProbTotal]], and Total[bScore] + 2*Max[bScore] by Sow[Total[bScore] + 2*Max[bScore], bS] in order to distinguish between the two paths by which fNumericalToFit can return. Then, compute

tst = Reap[NMinimize[fNumericalToFit[EncodeErr, TestErr, RespSame, RespDiff], 
    {EncodeErr, TestErr, RespSame, RespDiff}], {bP, bS}]; tst // First
(* {3.39165*10^-10, {EncodeErr -> 0.2, TestErr -> 0.0774563, 
                     RespSame -> 0.0382264, RespDiff -> 0.0192278}} *)

Now look at the final 40 values returned by bProbTotal.

tst[[2, 1, 1, -40 ;;]]
(* {1.49046*10^-6, 3.3919*10^-10, 3.3919*10^-10, 3.3919*10^-10, 
    1.06634*10^-6, 3.39179*10^-10, 3.39179*10^-10, 1.49046*10^-6, 
    3.39179*10^-10, 3.39179*10^-10, 3.39179*10^-10, 3.3917*10^-10, 
    3.3917*10^-10, 1.49046*10^-6, 3.3917*10^-10, 3.3917*10^-10, 
    3.3917*10^-10, 1.2784*10^-6, 3.39168*10^-10, 3.39168*10^-10, 
    1.49046*10^-6, 3.39168*10^-10, 3.39168*10^-10, 3.39168*10^-10, 
    3.39165*10^-10, 3.39165*10^-10, 1.49046*10^-6, 3.39165*10^-10, 
    3.39165*10^-10, 3.39165*10^-10, 1.38443*10^-6, 3.39165*10^-10, 
    3.39165*10^-10, 1.49046*10^-6, 3.39165*10^-10, 3.39165*10^-10, 
    3.39165*10^-10, 3.39165*10^-10, 1.83437*10^-9, 3.39165*10^-10} *)

In contrast, the final 40 values returned by Total[bScore] + 2*Max[bScore] are

tst[[2, 2, 1, -40 ;;]]
(* {3.33007, 3.31574, 3.30547, 3.3116, 3.31537, 3.30142, 3.3148, 3.2837, 3.36089, 
    3.31254, 3.3148, 3.30792, 3.31537, 3.32385, 3.34129, 3.32441, 3.32347, 
    3.32498, 3.31961, 3.34006, 3.32064, 3.32998, 3.31433, 3.32168, 3.33375, 
    3.30208, 3.32441, 3.33874, 3.31442, 3.29454, 3.32932, 3.3164, 3.32017, 
    3.29623, 3.30406, 3.33139, 3.3312, 3.31942, 3.31537, 3.346} *)

Evidently, NMinimize has minimized bProbTotal.

One way to minimize the desired quantity is to penalize bProbTotal values by Return[10^5 bProbTotal] instead of Return[bProbTotal]. The resulting computation is much slower but finally returns

{0.664027, {EncodeErr -> 0.000252496, TestErr -> 0.0106023, 
            RespSame -> 0.0297825, RespDiff -> 0.0190421}}

along with the warning,

NMinimize::cvmit: Failed to converge to the requested accuracy or precision within 100 iterations.

The final 40 values returned by Total[bScore] + 2*Max[bScore] now are

(* {0.656203, 0.65411, 0.65725, 0.657821, 0.662563, 0.657154, 0.661722, 0.655251, 
    0.654094, 0.660295, 0.650668, 0.656393, 0.653142, 0.661802, 0.655046, 0.654395, 
    0.659994, 0.659343, 0.661342, 0.660184, 0.656488, 0.652096, 0.662389, 0.658964, 
    0.653825, 0.657917, 0.660675, 0.655426, 0.652302, 0.652952, 0.65449, 0.65078, 
    0.652968, 0.658488, 0.656473, 0.655654, 0.658677, 0.653729, 0.65366, 0.665608} *)

all hovering about 0.664027, the poorly converged solution returned by NMinimize. It is informative to evaluate fNumericalToFit for the final parameters also returned by NMinimize.

fNumericalToFit @@ Values[tst[[1, 2]]]
(* 0.654389 *)

close to 0.664027. In fact, if this last line of code is executed repeatedly, it yields a different value close to 0.664027 each time. This is not surprising, because, as already noted, the calculation of bScore involves random numbers.

In summary, to obtain an approximate minimum for Total[bScore] + 2*Max[bScore], severely penalize any values of bProbTotal returned by fNumericalToFit.

The original question posed was, of course, why does ParallelTable sometimes not work, whereas Table does. This question probably cannot be resolved without knowing the internal working of NMinimize. Certainly, using ParallelTable changes the order in which table elements are computed, and therefore changes what random numbers are used to compute those elements. In closing, I would remark that Table is more efficient than RandomTable for this problem, by as much as a factor of two. I determined this by observing CPU usage on my PC. Also, NMinimize, left to its own devices, performs a degree of parallelization on its own.

Answer 2

I did observe a behavior similar to the one you described with your definitions (i.e. CPU sitting idle while calculation continued).

However, I found that changing ParallelTable to a simple Table in the definition of your function seems to fix whatever problem you had. I did not spend enough time on it to figure out why there was a problem. Perhaps the distribution of definitions to parallel kernels was incomplete?

Anyway, when applying the ParallelTable -> Table substitution in your code (and instrumenting the minimization function to see it run and collect the intermediate results):

e = 0; s = 0;
Row[{"Evaluation = ", Dynamic[e], "    ", "Steps = ", Dynamic[s]}]

results = 
  Reap@
   NMinimize[
     fNumericalToFit[EncodeErr, TestErr, RespSame, RespDiff], 
     {EncodeErr, TestErr, RespSame, RespDiff},
     EvaluationMonitor :> e++,
     StepMonitor :> (s++; Sow[{EncodeErr, TestErr, RespSame, RespDiff}])
   ];

The calculation terminated in less than a minute and I obtained:

results[[1]]

(* Out: {3.52701*10^-9, {EncodeErr -> 0.2, TestErr -> 0.0774563, 
                         RespSame -> 0.0382264, RespDiff -> 0.0192278}} *)