Venue: NeurIPS 2022 Conference

Reviews:

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: f-divergences can be written as variational objectives, typically parameterised in terms of a density-ratio estimator between 'positive' and 'negative' distributions. This paper identifies a new equivalence between a particular kind of f-divergence and the arc length of the `optimal AUC curve' (i.e. the best possible AUC curve amongst all classification scoring-functions). Convergence guarantees are given when the  estimated (arctan) log-density-ratio belongs to an RKHS. Finally, this estimator is used to (approximately) lower bound the optimal AUC, which is an important quantity in unbalanced binary classification settings, as shown in the experiments on Cifar-10.
strengths_and_weaknesses: Strengths

- It's an interesting, non-obvious finding that the ROC curve can be connected to variational f-divergence representations. Also, it takes some ingenuity to consider the arc-length rather than the more standard AUC.

- As far as I can tell, the theoretical results look correct (although I have concerns about novelty - see below)

- The experiment is interesting and shows some promise (but I have concerns - see below).

Weaknesses

- I have questions about the novelty of the theoretical results. See Questions below.

- I think it is *very* important to report the wallclock times for the different methods used in the experiments. I understand that the proposed method has better asymptotic complexity, but I want a sense of how big those hidden constant factors are.

- Section 4.1 (line 146 onwards) & Section 4.2 were hard to follow. In equation 5, the variational formula is reparameterised in term of an angle v \in [0, \pi/2]. At this point in the exposition, it is quite unclear why such a reparameterisation is a good idea; it is more standard to parameterise the variational formla in terms of the log-density-ratio, which belongs to [0, \infty]. A whole page later, we discover that the log-density-ratio approach (combined with a linearity assumption) is theoretically less convenient because of nonconvexity. I think that this nonconvexity issue could be mentioned *before* Equation 5, so the reader understands where the argument is going.

- Section 5 (lines 232-256) is very math-notation-heavy, making it difficult to read. More plain-english explanations would greatly improve clarity. For instance, many explanations could be stated in terms of the lines in Figure 2, rather than using math.

- the abstract is rather vague, and I struggled to understand it (In contrast, the introduction was quite clear). I recommend clarifying what is meant by `score function', since it has multiple meanings (e.g. the gradient of log-likelihood w.r.t parameters/data).
questions: Could the authors comment on the added value of their theoretical convergence results over that of Nguyen et al. ? (2007, "Estimating divergence functionals and the likelihood ratio by penalized convex risk minimization). A superficial glance at that paper suggests that they prove a rather similar result for *arbitrary* f-divergences.

If I am correct that your results are similar to the prior work (but perhaps involve small modifications), then this should be made clear in the exposition.

Right now, I have assigned a score of 'fair' to the contributions of this paper. I would be willing to raise this if these concerns regarding theoretical novelty turn out to be wrong.


Minor points

line 40: the term 'surface area' is unclear here.  How does it differ from the usual AUC? needs clarifiying.
line 73-74: Readers may be used to thinking of FPR & TPR as fixed scalars (rather than functions of a threshold). I think it could help to give these functions arguments and perhaps refer to such arguments as `thresholds'.

minor correction: line 40: `maximual' --> `maximal'
limitations: The authors are very upfront about certain limitations (e.g. the fact that they require differentiabiltity of the score function w.r.t its input, unlike prior work).

One issue is that their `lower bound' on the AUC does not appear to truly be a lower-bound (since they have to replace certain terms with approximations). This limitation could be made clearer, since right now, the conclusion implies otherwise.
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 paper discusses f-divergence with arc length of ROC curve.  The authors find that several papers use ROC curves to compare two distributions.  And then try to answer the reason why arc length of ROC curve could be a type of f-divergence. The authors build the connection between the arc length of ROC curve and f-divergence, and then derive the algorithm to estimate the arc length of ROC curve. The experiments on Cifar-10 show that the score function obtained from 2-step procedure produced promising results.
strengths_and_weaknesses: Strength:

1. The paper provides a good presentation to the paper.

2. The paper starts with a question of using ROC curves to compare two distributions, and then answers this question step by step. The deviations in the main body make sense. 


Weakness:
1. Although the authors have convinced me that the arc length of ROC curve is a type of f-divergence similar to KL divergence, total variational distance, the relationship with them are not discussed well. I only find proposition 3 discuss the relationship with total variational distance. More relations are appreciated to be provided. In addition, in the experiments, the authors only show the rationality of the arc length of ROC curve, the discussion and comparison with other f-divergences are missed here.

2. Although the paper is of a good presentation, still has some minor types, like line 30 the font of f should be mathematical way, line 32, there has one more space between [28] and ‘.’.
questions: It would be great if the author could address the questions in weakness and comments.
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 builds a connection between the ROC curve of testing two distribution $p_{+}(\boldsymbol{x})$,  $p_{-}(\boldsymbol{x})$ and the "distance" between these two distributions. In particular, the length of the optimal ROC curve corresponds to a type of $f$-divergence between $p_{+}(\boldsymbol{x})$ and $p_{-}(\boldsymbol{x})$. This $f$-divergence can be estimated utilizing its variational formulation. The optimal solution of the equivalent variational problem is $\arctan[\frac{p_{+}(\boldsymbol{x})}{p_{-}(\boldsymbol{x})}]$. Therefore, by solving the empirical version of this variational problem, an estimate of $\arctan[\frac{p_{+}(\boldsymbol{x})}{p_{-}(\boldsymbol{x})}]$ can be obtained.
strengths_and_weaknesses: Strengths: The fact that the length of optimal ROC curve corresponds to a $f$-divergence is an interesting new result. Also the presentation of this paper is clear and fun to read.
Weakness: I think the condition in Proposition 4, which requires that $\arctan[\frac{p_{+}(\boldsymbol{x})}{p_{-}(\boldsymbol{x})}] \in \mathcal{H}$ is a little stringent. In practice, to reduce computational complexity, the class $\mathcal{H}$ may not be very rich. It is better to discuss what will happen when there exist some approximation error of $\arctan[\frac{p_{+}(\boldsymbol{x})}{p_{-}(\boldsymbol{x})}]$. Also I think it will be better if more numerical experiments are provided, e.g., comparison with other methods of choosing score function $t(x)$ (if any) and experiments in other datasets.
questions: 1. For the two-step procedure stated in Line 264, why do we need the second step? The goal is to estimate $\arctan[\frac{p_{+}(\boldsymbol{x})}{p_{-}(\boldsymbol{x})}]$, which has been done in Step 1.

2. It turns out that the optimal solution of the variational problem (Line 141) is a monotone transform of likelihood function. Can the author comment on under which choice of $g$, this is the case?

3. Is there a typo in Eq. (1): Should it be $[\partial_{\tau}\tilde{F}_{-}(\tau)]^2$ ?

limitations: NA
review_title: null

final_score: rating: 4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
review_content: summary: This paper propose a novel method that utilizes arc length of the AUROC curve to approximate AUROC itself. Then, propose to optimize the arc length of the curve with some theoretical justifications for the relationship with AUROC. 
strengths_and_weaknesses: Strengths: The idea is novel and interesting. The paper provides some illustrations for the idea. 

Weakness: 

i) Optimizing arc length is not consistent with optimizing AUROC itself. As the examples shown in Figure 1, people could have the same optimized arc length, but have different optimized AUROC (subfigure a and b). Or, people could have the same optimized AUROC but have different optimized arc length (subfigure b and c).

ii) Although the idea is novel as an alternative way to optimizing AUROC, the paper lack some justifications for the advantages over the main-stream AUC optimization methods based on surrogate loss functions. (Gao, Wei, et al. "One-pass AUC optimization." International conference on machine learning. PMLR, 2013.;  Ying, Yiming, Longyin Wen, and Siwei Lyu. "Stochastic online AUC maximization." Advances in neural information processing systems 29 (2016).;  Liu, Mingrui, et al. "Fast stochastic AUC maximization with $ o (1/n) $-convergence rate." International Conference on Machine Learning. PMLR, 2018. etc.)

iii) The experiments are insufficient. Only CIFAR10 is conducted for the experiment. And only logistic regression and a pairwise squared loss optimization method are considered as comparisons. There is no deep learning experiments. Moreover, even based on the current experimental results, the proposed method doesn't outperform the pairwise loss optimization. 

iv) There are some short claims for the computational efficiency of proposed method, but there is no justifications.
questions: Please refer to the weakness part above. I like the new idea, but don't think it is ready to be published.
limitations: I don't see any limitations for societal impact.
review_title: null

Meta-review: metareview: The paper shows that the arc length of the optimal ROC curve is an $f$-divergence, propose san estimator for it, and builds on the insights obtained to design a new algorithm for approximately maximizing the area under the ROC curve.

The reviewers generally appreciate the theoretical results / insights. The only concern seems to be about the empirical evaluation of the AUC maximization procedure and about the lack of sufficient comparison to the state-of-the-art AUC maximization methods.

Given that the main contribution is the connection drawn between the arc length of ROC curve and $f$-divergence, a majority of the reviewers are in favor of accepting the paper even if the empirical evaluation is not entirely satisfactory.

**Authors inaccurate about offline AUC maximization taking $O(n^2)$ time**

One of the selling points in the paper is that the new AUC maximization approach achieves a better run-time complexity than more traditional methods for AUC-maximization. Based on the authors' back-and-forth with Reviewer WsBr, it appears that the method of Ying et al. (2016) already achieves an O(n) run-time even for the offline setting. 

I would also like to point to the authors that, dating back to as early as 2005, there have been methods for offline AUC maximization with O(n log(n)) computational cost. For example, with the pairwise SVM loss, Joachims (2005, lemma 2) show that the loss/gradient computation only requires $O(n \log(n))$ computation. This computational time applies to both linear and non-linear models, as I elaborate below.

Suppose there are $n^+$ positive examples and $n^-$ negative examples, and we would like to minimize the pairwise hinge loss for scoring function $f$:

$L(f) = \sum_{i=1}^{n^+} \sum_{j=1}^{n^-} \phi(f(x^+_i) - f(x^-_j) )$

where $\phi(z) = \max(0, 1 - z)$. Computing this loss does not need us to explicitly enumerate $O(n^2)$ pairs. Instead it suffices to sort the positives according to $f(x^+_i)$ and the negatives according to $1 + f(x^-_j)$, and then compute the following cumulative stats by taking a single pass (O(n)) over the sorted examples:

$N_{i}^{+}= \sum^{n^-}_{j=1} \mathbb{I}( 1 + f(x^-_j) \geq f(x^+_i)  )$

$L_{i}^{+}= \sum_{j:~ 1 + f(x^-_j) \geq f(x^+_i)  } f(x^-_j)$

The pairwise loss can then be computed in O(n) time:

$L(f) = \sum_{i=1}^{n^+} L_{i}^{+} + N_{i}^{+} \cdot (1 - f(x^+_i) )$

A similar procedure can be used to compute gradients for the pairwise loss, and would again require only $O(n\log(n))$ computation (for the sorting step).

*Ref*: Joachims, A Support Vector Method for Multivariate Performance Measures, ICML 2005.

**Recommended changes/inclusions to camera-ready version**

We are accepting this paper under the expectation that the authors will include a more accurate description off-line AUC maximization methods, and accurately describe the exact computational advantages their method has (if any) over prior AUC maximization methods. If there are none, please don't highlight them in the paper. A review of stochastic AUC maximization methods is also highly desirable. 
confidence: Less certain
Decision: Accept