Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: This paper considers the question of parameter estimation in a binary response model (e.g., logistic regression), in the imbalanced case where the fraction of positive instances is small/vanishing.
This question is formulated by considering a well-specified model, and adding an intercept to the log-odds ratio which diverges as the sample size goes to infinity (with the other parameters kept fixed).

The main results are the following:

- First, it is shown (in Theorem 1) that the convergence rate of the MLE (computed on the full dataset) only depends on the number N_1 of positive instance, rather than on the sample size (which also includes negative instances). MLE also shown to be asymptotically normal, and the asymptotic covariance is provided.

- Since the convergence rate of MLE only depends on N_1 (but not on the total number N of samples), it can make sense to perform "negative sampling", namely to reduce N by only retaining a small fraction of negative instances, in order to reduce computations. Of course, removing negative instances creates a bias, so the authors considers inverse probability weighted (IPW) estimators, where negative samples are re-weighted (inversely proportionally to the deletion probability). An asymptotic normality result is obtained, with a covariance larger than MLE (as expected), by an additional covariance depending on the rejection probability function (Theorem 2). The optimal rejection function (minimizing asymptotic variance) is deduced (Theorem 3).

- Finally, the authors consider a different estimator, based on log-odds correction. This estimator corresponds to MLE on the selected data, based on adjusting the likelihood of the selected data by accounting for the deletion mechanism. This leads to a correction which is less sensitive to small probability instances than the IPW method.
The asymptotic normality and covariance of this estimator is provided (Theorem 4). Interestingly, it is shown (Theorem 5) that this scheme is always better than the IPW (with optimal rejection function), in that it leads to a smaller asymptotic covariance. An optimality result of this estimator among (asymptotically) unbiased estimators is then provided in Theorem 6.
main_review: I enjoyed reading this paper. It is well-written, considers a practically meaningful question, and provides precise answers. It also does not contain any spurious or unsubstantiated claims or decorative results. I appreciate the interesting adjusted MLE estimator based on the likelihood of selected data, and in particular its comparison with the IPW. The results also provide a coherent picture and naturally complement each other.

I am therefore strongly in favor of acceptance of this paper, and would also suggest considering it for a spotlight or oral presentation, as it could potentially be of interest to many NeurIPS attendees. I would also encourage the authors to consider publishing a final version of this work to a suitable statistics journal.

I should mention, however, that I am not familiar with the literature on the topic, in the sense that I have read none of the papers listed in the references. I am therefore not in a very good position to gauge the level of originality (though I somehow doubt that related work could warrant rejection, unless the same results were obtained before). I might also be slightly biased by the fact that many of the ideas are new to me, although some might be more routine in this topic. (Due to a high reviewing load, I did not check the proofs in the supplementary material.)
I have accounted for this both in my low confidence score and in the overall score.

Below are some comments:

1. I would suggest (maybe in a final version) to put the results (asymptotic covariance matrices) in more explicit or simple form in the specific case of logistic regression, which is arguably one of the most standard and relevant ones.

2. It would perhaps be helpful to comment the results in connection with the asymptotic distribution of the MLE (given by the Fisher distribution) or the Cramer-Rao lower bound/asymptotic optimality of MLE. It actually seems that these standard result do not apply, as the data distribution changes with N (since the fraction of positive instances vanishes), which justifies a specific analysis as in this paper.

3. It seems that, as noted in the paper, the misspecified case could also be considered in future work. Asymptotic normality should also hold there (with a covariance depending on the distribution), with the true parameter replaced by the best KL approximation.
limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper considers the estimation of the parameters of a binary response model when the positive instances are rare. Rareness is modeled via a scaling regime on the logits, with the key restriction being that the scaling occurs _uniformly over features_. The paper first shows that the fraction of positive instances bottlenecks estimation and uses this to motivate subsampling the negative instances, to save on computation. The paper considers two negative subsampling approaches: importance weighting the original likelihood and maximizing it (IPW), or maximizing the log-likelihood under subsampling (Lik). Under correct model specification, asymptotic analysis is provided for both methods, with the latter enjoying many advantages, including stability and smaller asymptotic variance. The approach is tested on synthetic and click-through-rate data. The experiments support the theory and go beyond it, by showing that the methods work well even under model misspecification.
main_review: ### Strengths

+ The paper gives a very comprehensive modeling and treatment of rare positive instances in binary response: motivating sub-sampling, revisiting key sub-sampling methods, optimizing these methods to perform well, analyzing the presented variants, giving practical implementation tweaks, analyzing those tweaks, and finally testing on meaningful experiments. Each of these steps is a worthwhile contribution to share with the community. _(originality, significance, quality)_

### Weaknesses

- The scaling regime is somewhat limiting, because it requires the logits to decay uniformly over all features. This is definitely an acceptable and useful simplifying assumption for theoretical work, but it’s not clear why this is the right model to capture rare positives. Some discussion on this matter would be appreciated. _(significance)_

- The paper is theory-intense, which is not a problem, but this is presented in a dry and dense fashion which makes it a heavy read. More signpost paragraphs to maintain the high-level picture can make this a more pleasant read. _(clarity)_

- Some claims need a little care for nuance. For example, on line `line 86`, does the MLE remain the most efficient estimator (among asymptotically unbiased ones), even in this scaling regime? Saying the number of positive instances is what matters `line 98`, is obviously not true, because the result hinges on $N_1/N\to 0$. Of course, down the line with the subsampling results, it’s clear we need to include "enough" negative samples to get the same asymptotic behavior as the full sample.  On `line 117` saying that will happen at $c=0$ should be emphasized to be just conceptual, since at that point Theorem 2 no longer holds. _(quality)_

### Suggestions

* It’s worthwhile to do a grammatical pass on the text, since there are several incorrect English phrases. These don’t deter from the quality of the work, but the polish would be appreciated. 

[Edit: Thank you authors for your response. My evaluation is unchanged.]
limitations_and_societal_impact: The paper adequately discusses the limitations of the work. Societal impact is not discussed. While there may be some implications, considering that a big motivation is eliciting marketing response, which could negatively impact some sub-populations, it's not immediately apparent whether the proposed approaches could actively lead to discrimination.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper discusses the sampling strategy for imbalanced binary-label datasets. For a binary-label dataset where the number of negative samples $N_0$ is much larger than that of positive samples $N_1$, we often "subsample" a part of negative samples in order to balance two labels.

The paper discusses the asymptotic convergence rate of the optimal model parameter against the number of samples in the dataset, and improves the rate from conventional model parameter estimation method.
-   Theorem 1 proved that the convergence rate is proportional to $N_1^{-1/2}$, that is, determined not by the number of all instances but of positive instances if $N_0\gg N_1$.
-   Theorems 2 and 3 composes a function that provides the best strategy to subsample negative samples.
-   Theorems 4 through 6 modifies the result of Theorems 2 and 3 for improving the efficiency by incorporating the sampling strategy.
-   Theorems 7 and 8 discusses the effect of the "pilot" model parameter and provides the construction of it for better convergence rate.
main_review: Since we often encounter imbalanced datasets, subsampling strategy is very important for them. The proposed method is theoretically proved to be effective, including the setups for practical uses. Experimental results supported the results.

The reviewer felt that the paper was not well organized in the sense that the paper's contribution is not clear. The reviewer hopes the paper that the following points to be clearer: what is based on conventional methods, and what is new in the proposed method. (In the appendix there are references if existing analyses are employed for the proposed method, but the reviewer hopes references in the main paper in order to discuss the novelty of the paper.)

-   Section 1, the part "Rare events data and negative sampling are studied in [28], but it focused on linear logistic regression and only considered uniform sampling. We approach this problem under general binary response models from the perspective of optimal subsampling, which aims to minimize the asymptotic variance of the IPW estimator [30, 26, 29, 31]. This topic was not well investigated neither for imbalanced data nor for negative sampling."
    -   What is main updates of the proposed method from the negative sampling strategy in [28] and the IPW? Does the paper just combines them (as well as providing with some new analyses)?
-   Section 2.1
    -   The reviewer felt that the result of Theorem 1 for simpler case seem to be proved by someone else. Please refer to conventional related analyses and their relationships to Theorem 1 in the main paper (not only the appendix) if any: For example, balanced case with (without) Assumptions 1 or 2, or imbalanced case with different assumptions.
-   Section 2.1
    -   Please provide, if any, the intuitive interpretation of $M^{-1}_f$ since it is essential to discuss the performance of the proposed method.
-   Section 6
    -   Since main theorems discuss the convergence rate against the number of samples in Theorem 1, perhaps experiment on it will support the paper's analysis more.
limitations_and_societal_impact: The impact is mainly stated in Section 1 and 7, theoretical assumptions are stated before respective theorems, and limitations are stated in Section 7. The reviewer thinks that they are adequately stated.
review_title: null

Meta-review: In this paper, an optimal negative sampling strategy from imbalanced data for rare event prediction is studied. The problem of class imbalance in rare event prediction is of considerable importance in various applied problems. The theoretical properties of the proposed method are clearly presented, and its advantages are clearly demonstrated by experimental validation on artificial and real data. All reviewers found the paper useful for the ML community. The authors are encouraged to consider updating the paper based on the reviewers' comments and suggestions.
Decision: Accept (Poster)