Could we explain the disadvantage of imbalanced data mathematically? Simple setup:

*

*observed response is binary (yes/no, 0/1, positive/negative).

*use logistic regression to model the probability of the response being, say, 1: $P(Y=1|X)$.

*the MLE of the model coefficients enable us to predict the probability by $\frac{1}{1+exp(-X\hat{\beta})}$.

*By checking ROC and AUC, we find the most appropriate threshold of $p_{0}$ such that $\hat{y}=1$ if $\hat{p}>p_{0}$, otherwise $\hat{y}=0$.

In this process, could we mathematically show that $P(Y=1|X)$ is underestimated if we have 10000 0's and 100 1's? How is this bias quantified in formula?

In general statisticians are not worried about bias in imbalanced data (not a problem per se), since

*

*they use probabilistic classifiers like logistic regression

*the bias (in small samples) of logistic regression is orders of magnitude smaller than the variance.

So it's my personal belief that ML researchers have been 'fooled by randomness'.  In addition SVMs and random forests are not (or not good) probabilistic classifiers, and there rebalancing might have been beneficial. gradient boosted models are well calibrated probability classifiers so this is no longer an issue.
There is a relatively recent freely accessible paper (https://gking.harvard.edu/files/0s.pdf) that covers your particular question for logistic regression, and reports the estimated bias which has been known since the 60s?
Although the paper seems to argue for the importance of bias correction, their results show that it's pretty immaterial for probability estimation ( until you go to 3 standard deviations from the mean of their normally distributed  input data). see figure 6.  Infact the debiased model gives worse results than both standard logistic regression and their proposed bayesian regression.  I interpret these results as consistent with the argument that the variance is the big problem with imbalanced data and standard regularisation approaches (like bayesian regression) have the most to offer to fix the problem.
@lambda, So I tried to find the theory paper (from the same author) that the paper you mentioned references.
Class Imbalance, Redux.  I have only access to a summary wallace imbalance.  It seems like the authors took the heuristic explanation given by King et al. (" To see this intuitively, and only heuristically...") and promoted it to a theory.  The suggestion seems to be that the maximum is biased low (as function of sample size). So in the perfect separation case, a decision boundary set between the extrema of majority and minority class will be biased (towards the minority class). Undersampling the majority class will help this (oversampling the minority will not help). Adjusting costs will not help this because you are already correctly classifying all the negative class correctly.
This assumes that the maximum is actually used in the ML algorithm.  As alluded to by @dikran-marsupial, this seems to depend on perfectly separating the data, it's not a general property (eg most clearly linear discriminant analysis only uses means and covariances of the class). Another proviso is this assumes numeric and not categorical data.
I do think this is an interesting argument and it might explain why this is something that ML people training trees etc to perfect classification hit this problem, whilst focussing on probability calibration avoids this.
