Which classification algorithms are negatively affected by class imbalances? I've seen a few posts and papers floating around the web (mostly those related to over/undersampling, SMOTE, and cost-sensitive training) that, when discussing class imbalance, specify that certain algorithms are negatively impacted by class imbalance.
Which algorithms are those? Which are not? How can we figure out whether or not an algorithm or approach will be negatively affected by class imbalance?
 A: 
Which algorithms are [negatively affected by class imbalances]?

Many are, at least out-of-the-box: notably decision trees, random forest, neural networks, and SVMs. However, this can usually be patched up with something as simple as class weights, so it's hardly a reason not to choose these algorithms.

Which are not? 

For logistic regression it can be proved that class imbalance only affects the intercept coefficient. 

How can we figure out whether or not an algorithm or approach will be negatively affected by class imbalance?

The papers I've seen usually investigate this empirically, by artificially unbalancing the classes and seeing how that affects some performance metric.
Class imbalance is not a particularly serious problem. If the imbalance isn't severe, you often don't need to do anything at all, and won't see any benefit from playing around it. Nevertheless, here's a rough workflow.
1) If your classes are so wildly imbalanced (say 1:1000) that you're having performance or memory problems getting enough minority examples, it's usually safe to use majority undersampling to cut that down to 1:10 or less. You'll still have plenty of examples to learn from.
2) Once classes are roughly balanced (less than factor of 10 difference,) setting sample weights to the reciprocal of class propensity usually fixes the problem. Most software libraries routinely implement class weights (or sample weights, which can serve the same role.) It is always worth confirming that the benefit is real with cross validation, of course. Cross validation can even be used to do a hyperparameter search for optimal class weights; in theory this could yield a small performance boost, although in my experience it rarely pays off. 
3) If you have so much data that you're already taking a random sample before training (I don't mean train/validation/test splitting, I literally mean not using most of the available data) then oversampling the minority class to achieve a balance can be a better option than class weights, because your minority class will have more "unique" examples. In rare cases you may also be able to see a performance gain from techniques like SMOTE, but that's a matter for cross validation. 
A: 
How can we figure out whether or not an algorithm or approach will be negatively affected by class imbalance?

First, data. See if the instances in the minority class have sufficient signal for the model to learn. If not, it becomes a few-shot learning problem, and the model may assume the rare classes just don't exist.
Second, output evaluation. See if the metric you use is appropriate. If you simply use accuracy, your model probably tends to just learn the very straightforward heuristic: always output the majority class. Otherwise its performance becomes worse even though it is trying to learn the underlaying data patterns.
Third, outcome evaluation. Your approach will be negatively affected by class imbalance if the cost of a wrong prediction on a sample of the rare class is much higher than that of the majority class.
From the algorithmic perspective, this may help:

Some tasks are more sensitive to class imbalance than others. Japkowicz showed that sensitivity to imbalance increases with the complexity of the problem, and that noncomplex, linearly separable problems are unaffected by all levels of class imbalance. Class imbalance in binary classification problems is a much easier problem than class imbalance in multiclass classification problems. Ding et al. showed that very deep neural networks—with “very deep” meaning over 10 layers back in 2017—performed much better on imbalanced data than shallower neural networks.

References:

*

*Designing Machine Learning Systems
