NMinimize stops using CPU but still evaluating

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] :=

(* 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];

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}]

• Can you elaborate? I copied and paste the code and tried to run it. I got a result back. I'll clarify to include the code that leads to my problem though! – Lokdal May 4 '18 at 1:30
• When your code does not hang, it appears to be minimizing bProbTotal rather than bScore . – bbgodfrey May 4 '18 at 12:18
• That is weird... Can you tell me how you came to that conclusion? – Lokdal May 4 '18 at 16:12
• bProbTotal is given by Total[Which[# < 0, -100*#, # > 0.2, 100*(# - 0.2), True, 0] & /@ {0.20000000000965154, 0.07745625850428044, 0.03822638935911683, 0.019227848497057474}] for the solution given by @MarcoB and is equal to 9.65153*10^-10, which is greater than 0, triggering the Return statement. ParallelTable, when it works, behaves similarly. – bbgodfrey May 4 '18 at 16:58
• Also, I ran the calculation, printing every evaluation of bScore. It had values of order 3, and then the calculation returned an answer of 3.16211*10^-9, which could only have come from bProbTotal. – bbgodfrey May 4 '18 at 17:12

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.

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}} *)

• Even with ParallelTable, I obtain results in about a minute, {5.49044*10^-10, {EncodeErr -> 0.0476947, TestErr -> 0.056123, RespSame -> 0.18237, RespDiff -> 0.2}}. The work load across the four processors on my PC was extremely nonuniform,, explaining why little improvement in speed occurred. – bbgodfrey May 4 '18 at 4:03
• Interestingly, with Table I obtain different results, {3.46628*10^-9, {EncodeErr -> 0.2, TestErr -> 0.0774563, RespSame -> 0.0382264, RespDiff -> 0.0192278}}, suggesting an error in the code. Also interestingly, the Table calculation used about 2/3 of my CPU power, indicating that NMinimize must have used multiple processors even without being instructed to. – bbgodfrey May 4 '18 at 4:08
• So, I ran with ParallelTable again, and the calculation ground to a halt without terminating. So, I closed Mathematica and then started it from scratch, and it worked fine, although it produced different results than those in my first comment. Then, with the same kernels, I again ran the problem and it ground to a halt without terminating. – bbgodfrey May 4 '18 at 4:23
• Finally, I ran the code with Table several times to be sure that it was not failing on the second or third run. It did not. Probably, the code with ParallelTable is overwriting something. – bbgodfrey May 4 '18 at 4:28
• @bbgodfrey The ParallelTable version gave me similar results, i.e. it would stop using CPU power and just sit, CPU idle, without terminating. I had it happen multiple times, but could not reproduce it consistently, so I had suspected a sensitivity of the system to the choice of initial parameter values by NMinimize. – MarcoB May 4 '18 at 4:39