Earlystopping in multi-output deep learning
How would one implement this without risking overtraining some output nodes while preventing others from under-training?


This isn't done with early stopping. There are rather other techniques that could prevent that some main nodes are trained in your model such as Dropout. By using Dropout your model can't rely on some main nodes, because they could get shut off at any time. So with Dropout the model  should learn to balance the weights throughout the nodes.


  Should one monitor the net validation loss, or is there any way to implement early-stopping such that m out of n (m goes from 1 to n) outputs' validation losses are monitored and training stops at convergence of all/oscillations within a certain threshold.


You noted that n in your case refers to the number of output nodes. Generally, that is the number of classes in your classifier which is mostly denoted by c. So, in multi-class classification you wouldn't have c different validation losses but average them to obtain one mean validation loss for the whole model.


  How would one implement ...


There is no gold rule to how to implement early stopping. 
The simplest way to do it is as follows:


Set a so called patience i.e. after how many epochs do we stop if the loss doesn't improve (usually set to 10)
After each epoch check your validation loss
Then select the model patience epochs before you stopped, because that was the best performing model.


You see that this is not the best approach and there could be better ones. In this paper, some of them are suggested.


  ... training stops all/oscillations within a certain threshold


Could be another idea, that would have to be checked. I wouldn't recommend it though, because with SGD you still have oscillations at the very beginning.