What is the relationship between mean squared error and classification error? I've trained a network using a genetic algorithm and I have two possible fitness functions for my GA: MSE and CErr.
If I use MSE as my fitness function, over time MSE decreases and classification error decreases. Looking at my plots, it looks like MSE and CErr are directly related. However, if I use CErr as my fitness function, over time my CErr decreases but my MSE doesn't always decrease.
For example, consider these two training attempts, the first with MSE as fitness function and second with CErr as fitness function. The data, train/test split, activation function, etc everything is equal except fitness function. Accuracy is just a function of classification error (1 - CErr = Acc).


From this I can deduce a lower MSE means a lower CErr but a lower CErr doesn't always mean a lower MSE. For a genetic algorithm, I should use MSE as my fitness function because if MSE were to rise to reach a better CErr, it might get trapped in local minima as better solutions are guaranteed when the MSE is lower (and the algorithm, through crossover and mutation, will focus on areas in the search volume which are suboptimal).
But why do I get results like this in the first place? I thought MSE was directly proportional to CErr and vice-versa but I do not always observe this.
 A: If your algorithm is estimating probabilities of class membership, then mean-square error (MSE) is effectively the Brier score, a strictly proper scoring rule that is optimized by a model that provides the true probabilities.
Classification error (CErr) involves an often hidden assumption about assignment of class membership based on class probabilities. For example, in binary classification the model's class assignment would usually by default go to the class that has highest probability, a cutoff probability of 0.5. But if you choose such a cutoff in practice then you are effectively assuming that all mis-classifications have the same cost. If false negatives are more costly than false positives, however, then a different cutoff that lowers the false-negative rate might be more appropriate to minimize overall cost.
So there is no reason to expect that MSE and CErr would track together. Your criterion should be MSE or some other proper scoring rule to model class-membership probabilities first. Then use your relative costs of mis-classification to determine class assignments based on those probabilities.
