Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: summary: The paper proposes a novel framework that optimizes AUPRC in an end-to-end manner. The main idea is inspired by the theoretical properties of the objective function and the stochastic algorithm. The authors show that the objective function is asymptotically unbiased by approximation error analysis, and the proposed stochastic optimization algorithm has a generalization guarantee. Their experiments demonstrate the proposed framework work well on image retrieval datasets.
strengths_and_weaknesses: I consider this work novel and sound in three aspects:
1) The proposed stochastic estimator solves the estimation bias issue. The instability is mitigated by an auxiliary vector estimating positive scores. Sufficient theories and numerical experiments illustrate the proposed method.
2) It is the first work studying the algorithm-dependent generalization of stochastic AUPRC optimization. It is a challenging topic involving the list-wise problem and compositional problem.
3) The main claims are properly verified on both simulation and real-work data.

The main weakness of this work is missing explanations/analyzes of some techniques:
1) In table 2, the model with the semi-variance term has higher R@K, but similar mAUPRC. I’m interested in the mechanism of the semi-variance regulation.
2) The time consumption of the proposed score interpolation is $O(N^+)$. It might slow down the training process.

To sum up, this paper looks solid on both technical and theoretical parts. The presentation is overall well organized. Therefore, I recommend accepting this paper.

questions: I hope the authors can clarify some more in-depth analysis mentioned in the weaknesses part. Besides, the stochastic estimator is only proved to be asymptotically unbiased, but the order is still unclear. I suggest the authors to provides the asymptotic order. It might require data distribution hypotheses, as what the authors did in simulation experiments.
limitations: Yes.
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 proposes a stochastic algorithm for AUPRC optimization based on a sampling-rate-invariant unbiased stochastic estimator. The authors study the theoretical properties including the approximation error and generalization bound. Based on the theoretical results, they propose a semi-variance regular term to further improve the performance. The algorithm is applied to the image retrieval task.
strengths_and_weaknesses: Strengths:
- The weaknesses of some previous works are clearly identified and the proposed method is tailored to alleviate them. Both theoretical analysis and simulation experiments are provided to support the soundness.
- Formal theoretical interpretation of the components of the proposed method. This may inspire future work along this line.
- The extensive experiments have validated the proposed method. The ablation studies clearly present the effect of each component.

Weaknesses:
- The experiment details of the competitors need to be more specific to ensure fair comparisons.
- How the surrogate loss $\ell_1$ is chosen seems unclear. The theoretical results hold as long as it is an upper bound of $\ell_{0,1}$, why not use commonly used surrogate losses like square loss?
questions: Please see the weaknesses for my main concerns. Some minor issues are given as follows:
- The performance gain is more significant in iNaturalist than SOP. What’s the difference between these two datasets?
- How to determine the prior $\pi$ in the image retrieval task?

limitations:  The limitations and potential negative societal impact have been described.
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: In this paper, the authors aim to explore the properties of the AUPRC stochastic optimization. They provide two main theoretical results: the unbiasedness of stochastic estimators and the generalization of the optimization algorithm. To develop the algorithm-dependent generalization, they extend the model stability to list-wise loss. Experiments are conducted on three datasets.
strengths_and_weaknesses: The theoretical results of this paper are solid in the following aspects:
1. It’s interesting and challenging to study the algorithm-dependent generalization of AUPRC optimization. This work fills the gap in the list-wise loss stability analysis.
2. The authors provide a useful tool to analyze the convergence/stability of compositional optimization problems. Although transition matrices are widely used in complicated processes, it is novel and effective to simplify the calculation with the matrix spectrum.
3. By jointly considering the convergence and the generalization, this work provides guidance to find the trade-off between convergence and generalization of AUPRC optimization.
4. The main results are well presented and clearly proved.

My main concern is the presentation of some key techniques can be further improved. While the proposed techniques like simplification with matrix spectrum sound novel and reasonable to me, they haven’t been formally present in the main paper. Presenting it briefly in the main paper allows researchers to reuse these techniques on other problems.

Overall, this paper addresses some important theoretical issues of AUPRC optimization, and I tend to accept this paper.

questions: 1. In section 3.2 (P1), it is claimed that $n^+ / (n^+ + n^-) = \pi$ is hard to satisfied in practice. I think this condition can be achieved by changing the sampling rate during training, could you provide more explanations?
2. In my view, the $O(1/N^+)$ term is caused by the estimation of $h(S^+)$. Is it possible to use acceleration techniques in optimization, like variance reduction, to avoid this problem?
limitations: Yes
review_title: null

Meta-review: metareview: All reviewers agree the paper makes novel contributions for AUPRC optimization. 

It proposes new batch-based estimator of AUPRC and studies its approximation error. Then it develops a new algorithms for optimizing this estimator. It also establishes the generalization error of the proposed algorithms via novel listwise stability. 

It seems that the proposed method is still sensitive to the batch size as shown in the results. The authors are encouraged to compare with [53], which proposes a stochastic algorithm for AP maximization with convergence guarantee and is not sensitive to the batch size. 
confidence: Certain
Decision: Accept