Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: This paper aims to solve the scalability issue of partial AUC maximization (including the sum of ranked range loss minimization) in the setting of large-scale imbalanced binary classification. It proposes a gradient-based optimization algorithm with (non-asymptotic) convergence analyses. Specifically, it casts the (surrogate) partial AUC maximization problem into a non-smooth difference-of-convex (DC) program and then develops  an approximated gradient descent method based on the Moreau envelope smoothing technique. Besides, it also uses a stochastic block coordinate update to get the stochastic gradient in the algorithm. Finally, experimental results are provided.
strengths_and_weaknesses: First of all, I have to admit that I am not an expert in this area and have not checked the proofs in detail. Below are my comments.

Strengths:

1. Clarity.

Overall, this paper is written clearly.

2.  Quality.

It is good that the theoretical analysis (i.e. the convergence rate analysis) and experimental results are both provided to illustrate the effectiveness of the proposed optimization algorithm for partial AUC maximization.

Weaknesses:

1. Originality.

I am afraid that the novelty is limited since the techniques such as the difference-of-convex (DC) program transformation and related smoothing techniques have been widely studied in the related literature although there is little difference in the setting (i.e., both components in the DC program are non-smooth) as mentioned by the authors. Besides, it is incremental to the DCA method.

2. Significance.

For the proposed optimization algorithm, there are many hyperparameters, which are hard to tune in practice. Thus, I am concerned that it is not practical in applications. For the proof technique of theory, I cannot see the novelty. Thus, I am afraid that this work may have little influence on the community.

3. Quality.

The proposed method is based on the widely-used techniques in the community. Besides, the claimed main contribution (i.e. theoretical results) does not compare with the existing theoretical results.



questions: 1. As mentioned by the authors, the convergence analysis of the proposed method is the main contribution. Then, what are the technical novelty and its challenge?
limitations: Although the authors have mentioned the limitations of this work, I have the following suggestion.
1. As mentioned by the authors, the convergence analysis of the proposed method is the main contribution. Thus it is better to summarize the technical novelty and its challenge. Besides, synthetic experimental results can be added to illustrate the effectiveness of the convergence rate obtained by the theoretical results in this paper. Moreover, it is convincing to compare with existing theory results.
2. There are many typos in this manuscript. For example, 
  -line 230, According to Theorem 1.
  -line 292, Figure2...
Please check and fix them carefully.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This work casts the partial AUC optimization problem into a non-smooth difference-of-convex (DC) program. Then, by means of the Moreau envelope smooth, this paper presents an effective approximated method that achieves the $\epsilon$-critical point with a $\tilde{\mathcal{O}}(1/\epsilon^6)$ complexity. Finally, empirical studies are conducted to show the strengths of the proposed approach.  
strengths_and_weaknesses: Strengths: 
- New perspective and important problem. This paper addresses the partial AUC optimization from a novel point of view, i.e., a non-smooth DC problem. 
- Roughly sound theoretical guarantee. The authors provide the convergence of the proposed algorithm, supporting the effectiveness theoretically. 
- The writing and presentation are good.
Weakness:
- The related work seems not complete and some important literature in the AUC community is missing, such as 
a)	Optimizing Two-way Partial AUC with an End-to-end Framework. 
b)	Stochastic online AUC maximization.
c)	Learning with Multiclass AUC: Theory and Algorithms.
- The experiments seem not comprehensive. It is better to evaluate the performance on more long-tailed benchmark datasets, such as CIFAR-10-LT and TINY-IMAGENET-200-LT, and compare the proposed algorithms with SOTA partial AUC methods, i.e., [65] and [69] in their paper. Although extra experiments are not easy to complete, it is a relatively minor point considering the contribution of this work.

Overall, despite some issues, this work presents an interesting exploration of the partial AUC problem, which could motivate more effective methods and bring some potential value in this direction. Therefore, I tend to weak accept this paper and would improve my score if the authors could correct my concerns well.
questions: The primary concerns are two-fold:
- The strengths of the proposed algorithm on large-scale datasets are not clear. In general, solving the DC program is somewhat inefficient, and the authors should better provide some discussions about this.
- How to use the proposed DC-based optimization in the two-way partial AUC (TPAUC) problem? Because TPAUC is another practical generalization of AUC in real-world applications.  

In addition, I hope the authors could also handle the weakness of this work listed in the above part.   

limitations: None
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper proposes a gradient-based method for maximizing the partial AUC. The key steps are 1) decompose the objective as a difference-of-convex function, 2) smooth both convex components by their Moreau envelopes, and 3) perform (inexact) gradient-based updates on the smoothed DC objective function. In particular, gradients of the smoothed objective can be obtained through a lower-level stochastic block coordinate descent method. 
strengths_and_weaknesses: 1. Originality. The approach adopted in this paper seem to be new in the context of AUC maximization. However, components of the algorithmic design, i.e., smoothing of DC functions, and stochastic BCD, seem to be developed upon existing methodologies. 
2. Quality. The overall quality is decent. The algorithmic design makes sense and the proof of Theorem 1 looks correct to me (admittedly I skipped the proofs of some intermediate results).
3. Clarity. The paper is well-organized and easy to follow. 
4. Significance. The theoretical contribution is only mild. Numerical experiments seem promising. 
questions: For numerical comparison, the proximal DCA seems to be a more relevant algorithm, which is essentially a proximal version of DCA. In analogues to subgradient method, DCA itself can be slow without further stabilization or acceleration. The authors are suggested to compare with related proximal DCA works.
limitations: The authors have admitted a limitation in the conclusion section. I do not see direct negative social impact from the current manuscript.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper proposed the method for partial AUC optimization. Compared with [24] and [42], the proposed method can be applied to deep neural networks. The idea of the proposed method is to formulate the maximization of pAUC as a non-smooth difference-of-convex (DC) program and to apply the Moreau envelop technique. Furthermore, the stochastic block coordinate descent (SBCD) method is used for handling large-scale data. The theoretical analysis showed the complexity of finding a nearly \epsilon-critical solution. Finally, the performance of the proposed method was compared with the existing pAUC methods.
strengths_and_weaknesses: ##### Strengths
- The proposed method enables us to train deep neural networks
- The proposed method scales well because of stochastic optimization

##### Weaknesses
- $\tilde{O}(\epsilon^-6)$ iterations seems large
- $\mu$ needs to be small to make $f(w) + 1/(2\mu)||w||^2$ convex, resulting in that the constant in the order of K becomes very large
questions: The main point of this paper seems to represent the pAUC objective function as DoC. The theoretical analysis seems based on the DoC property. The empirical evaluation showed that the performance of the proposed method is superior to the existing methods. However, my concern is how this approach is meaningful from the theoretical viewpoint. To represent the pAUC as DoC, it is necessary to add $1/(2\mu)||w||^2$ to non-convex functions $f^n(w)$ and $f^m(w)$. Along with this line, one can prove, e.g., the convergence property of their method with deep neural networks plus $1/(2\mu)||w||^2$ regularization (i.e., weight-decay) on the basis of convex analysis. Compared with such an analysis, how different this paper is? In addition, to make $f^n(w) + 1/(2\mu)||w||^2$ convex, $\mu$ needs to be too small. In this case, the constants in the complexity order finding a nearly $\epsilon$-critical point. 

In Table 1, the CPU and GPU time AGD-SBCD uses to exceed SVM_pAUC^tight's pAUCs were reported. It seems good. A small concern is that optimization algorithms sometimes take most of the computation to check convergence even though the method attains some level of performance. If the authors could include the graph plots pAUC on a vertial axis and CPU+GPU time on a horizontal axis, such a graph might help understand the performance of the proposed method. One can check that performance curves do not drop after exceeding the existing method's pAUCs. 

The proposed method took a few seconds to exceed the SVM_pAUC^tight's pAUCs. Probably, the proposed method outperforms less than one epoch without going through scanning all training samples. If so, are there any explanations for why this can happen? Other than computation time, is it possible to report the number of epochs or iterations to exceed the SVM_pAUC^tight's pAUCs?
limitations: The limitation about the smoothness assumption was discussed in Conclusion.
review_title: null

Meta-review: metareview: The paper proposes a difference-of-convex (DC) based algorithm for optimizing the partial AUC performance measure. The authors show convergence guarantees and superior empirical performance compared to baselines.

The reviewers had some concern about the novelty of the use of DC optimization, to which the authors point out that the presence of non-smooth terms in both components of the DC objective makes their formulation non-standard and interesting. 

Overall, the reviewers seem to agree that paper should be accepted.

To address some pending concerns, the authors are **strongly encouraged** to include the following:
- A detailed discussion on hyper-parameter tuning and the values they prescribe in practice, as well as, an analysis of how sensitive their algorithm is to the hyper-parameters
- The additional experiments that the authors promised to Reviewer AF28

We trust that the authors will include the above in the camera-ready version of the paper.
confidence: Certain
Decision: Accept