Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The author presented a technique for optimizing the Area under the Precision-Recall curve (AUCPR). The proposed technique works by replacing the indicator function in the empirical AUCPR formulation with a smooth loss function and then decompose the formula as a sum of compositional functions. The author then proposed a learning algorithm based on stochastic compositional optimization. Finally, the author shows the effectiveness of the proposed model on various classification tasks.
main_review: **Strengths**

1. Optimizing AUCPR is useful, particularly in the setting of imbalanced datasets. Having a method that works in deep learning settings is useful for many applications.
2. The use of the stochastic compositional optimization technique in the proposed algorithm is interesting.
3. The author provides a convergence analysis of the model.
4. The experiments show the benefit of the model, and the model is less sensitive to batch size.

**Weaknesses, Concerns, and Questions**

1. The idea of replacing the indicator functions in the fractional metrics with smooth surrogate functions and directly perform optimization on that objective using neural networks is not new. Multiple related papers have tried that on several different metrics. The new idea in this paper is to use the stochastic compositional optimization technique to solve the resulting objective. I am not sure if this contribution only can warrant a NeurIPS acceptance. 
2. One of the challenges in optimizing a non-decomposable metric is that calculating the gradients of the surrogate requires computations over all samples. The author proposed a method to approximate the gradient using stochastic samples. How does this approximation affect the performance of the model?
3. One of the disadvantages of constructing a learning objective on a fractional metric by putting a smooth (convex) surrogate on both numerator and denominator is that the value of this fraction of surrogates may deviate a lot from the value of the original metric due to fractional computation. This is in contrast with a simple surrogate on the accuracy metric, e.g., hinge loss which has a monotonic relationship with the zero-one loss metric. Has the author investigated this potential misalignment of the surrogate vs. the original metric?
limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper investigates the imbalanced classification problems under the areas under precision-recall curves (AUPRC). To handle the nondifferentiability of the indicator functions in  the averaged precision (AP) estimators, they propose a differentiable surrogate functions such as squared hinge loss to replace the indicator function, leading to a compositional optimization problem. To solve this compositional problem, the authors use the moving average forward estimators in Wang et al., 2017, to estimate g_{xi}(w) in the gradient estimator of the objective function. For the outer updates, the authors introduce both the SGD-type and Adam-type gradient updates. Theoretically, this paper is the first one to provide the finite-time convergence analysis as well as a computational complexity for stochastic optimization of AUPRC. I am happy to see that the proposed method perform quite well in various imbalanced classification problems. The experiments are clear, comprehensive and involve a variety of datasets like CIFAR10, 100, HIV, MUV, and data for drug discovery, and test different types of neural networks such as ResNet. Under such a setup, they show their method outperforms existing state-of-the-arts via a notable margin (particularly for those highly imbalanced datasets). 
main_review: ========================================================
After rebuttal:

I am satisfied with the good response and additional empirical results. Therefore, I keep my score towards acceptance.  

========================================================

This paper investigates the imbalanced classification problems under the areas under precision-recall curves (AUPRC). To handle the nondifferentiability of the indicator functions in  the averaged precision (AP) estimators, they propose a differentiable surrogate functions such as squared hinge loss to replace the indicator function, leading to a compositional optimization problem. To solve this compositional problem, the authors use the moving average forward estimators in Wang et al., 2017, to estimate g_{xi}(w) in the gradient estimator of the objective function. For the outer updates, the authors introduce both the SGD-type and Adam-type gradient updates. Theoretically, this paper is the first one to provide the finite-time convergence analysis as well as a computational complexity for stochastic optimization of AUPRC. I am happy to see that the proposed method perform quite well in various imbalanced classification problems. The experiments are clear, comprehensive and involve a variety of datasets like CIFAR10, 100, HIV, MUV, and data for drug discovery, and test different types of neural networks such as ResNet. Under such a setup, they show their method outperforms existing state-of-the-arts via a notable margin (particularly for those highly imbalanced datasets). 

For my own interest, I have several questions as below:

1.	Can the authors explain a little bit why the moving average estimators involve the momentum-type updates, i.e., (1-\gamma)u+\gamma g? Does this help to reduce the variance of the estimators? What happens if such momentum-type updates are removed?
2.	I miss something but do the authors investigate the impact of different surrogate functions on the final empirical performance of SOAP? Can the authors provide a guideline on how to choose the surrogate functions for different problems?
3.	It seems to me that for a relatively larger imbalanced ratio, e.g., 12% and above, as shown in Table 4 in the appendix A, the proposed method is sometimes worse than MinMax method. Can the authors provide a comparison for a higher ratio such as 20%? I am wondering whether the proposed method is comparable to MinMax even for a relatively larger ratio. I am concerned about this because it may happen that the extremely imbalanced datasets are not that common in practice.  


Despite the above questions, I still like this paper due to two major reasons. First, the surrogate loss idea is clever although not hard to come up with. This reformulation of the AC really helps to design provable and faster gradient-based algorithms. Furthermore, the compositional optimization view point, the adoption of the moving average estimators and the developed nonasymptotic theoretical analysis are interesting. Second, I am happy to see that the proposed method can work quite well in practice, and the improvements over existing baselines are significant for highly imbalanced datasets. For these reasons, I tend to accept this paper.  

limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper studies classification in an imbalanced data setting, where the goal is to obtain large area under the precision-recall curve (AUPRC). This paper proposes a stochastic optimization method procedure for directly optimizing the AUPRC. Their procedure is based on optimizing a continuous approximation to the average precision (AP), which is obtained by substituting non-continuous indicator functions with continuous loss surrogates, and directly optimizing the resulting objective. 

The optimization algorithm proposed by this paper is called SOAP, and it is essentially a first order optimization method (e.g. SGD or Adam) with a better estimate for the stochastic gradient of the objective. The key for the improved stochastic estimate is to control the variance by tracking an exponential moving average to compute terms in the denominator of the gradient. SOAP has convergence guarantees that the average gradient norm of the surrogate AP objective will go to zero. 

Empirically, the authors apply SOAP to a variety of settings with imbalanced datasets such as imbalanced CIFAR, Melanoma datasets in the image classification settings, molecular prediction datasets with graph NNs, and drug discovery datasets with graph NNs. They show that SOAP can outperform competing baselines, particularly in the setting where the dataset is extremely imbalanced. 
main_review: This paper has nice theoretical and empirical contributions for the setting with very imbalanced data, I recommend accept. 

Originality: the paper proposes novel methods and analysis. 

Quality: both theoretical and empirical claims are well-supported in this paper. The experiments are very thorough and conducted for a lot of datasets for a wide range of architectures and settings. 

Clarity: The submission is clearly written and easy to follow. 

Significance: the paper proposes a clean framework for optimizing AUPRC directly with theoretical guarantees and good empirical performance even in the setting with small minibatch updates, which allows the method to scale to deep learning. This is a nice contribution over prior work. 

A question/concern for the authors:

-- One limitation of the loss surrogate seems to be that, depending on the exact surrogate loss $\ell$, it no longer seems to be an upper bound for the AP. In contrast, in typical settings where loss surrogates are used, the loss surrogate tends to be an upper bound (perhaps up to some constant factor scaling) on the target loss (e.g. standard classification where 0/1 loss is the target, and cross entropy is the surrogate). Can the authors comment on which choice of loss surrogate is used in the paper, and how the the value of the loss surrogate will generally compare to the true AP?

=====================================================================

Update after rebuttal: Thanks to the authors for the responses. I have read the other reviews and responses and will keep my score the same. 
limitations_and_societal_impact: Yes.
review_title: null

Meta-review: The paper proposes a stochastic optimization technique for maximizing the AUPRC metric, a popular metric in the evaluation of models on class-imbalanced problems. The paper makes compelling theoretical contributions, which are then supported by strong experimental results. All the reviewers lean towards accepting the paper. 

Some questions were raised about how closely the proposed surrogate approximations align with the true metric, and how the method fares with different choices of surrogates, to which the authors have provided a satisfactory response with additional experimental results. We strongly encourage the authors to include the additional results in the final paper (perhaps in the appendix if there isn't enough space in the main text).
Decision: Accept (Poster)