Exploring the Algorithm-Dependent Generalization of AUPRC Optimization with List Stability
Authors: Peisong Wen
Qianqian Xu
Zhiyong Yang
Yuan He
Qingming Huang
Venue: NeurIPS 2022 Accept (2022)
Keywords: AUPRC optimization
generalization via stability
learning to rank
deep learning

Abstract: Stochastic optimization of the Area Under the Precision-Recall Curve (AUPRC) is a crucial problem for machine learning. Although various algorithms have been extensively studied for AUPRC optimization, the generalization is only guaranteed in the multi-query case. In this work, we present the first trial in the single-query generalization of stochastic AUPRC optimization. For sharper generalization bounds, we focus on algorithm-dependent generalization. There are both algorithmic and theoretical obstacles to our destination. From an algorithmic perspective, we notice that the majority of existing stochastic estimators are biased when the sampling strategy is biased, and is leave-one-out unstable due to the non-decomposability. To address these issues, we propose a sampling-rate-invariant unbiased stochastic estimator with superior stability. On top of this, the AUPRC optimization is formulated as a composition optimization problem, and a stochastic algorithm is proposed to solve this problem. From a theoretical perspective, standard techniques of the algorithm-dependent generalization analysis cannot be directly applied to such a listwise compositional optimization problem. To fill this gap, we extend the model stability from instancewise losses to listwise losses and bridge the corresponding generalization and stability. Additionally, we construct state transition matrices to describe the recurrence of the stability, and simplify calculations by matrix spectrum. Practically, experimental results on three image retrieval datasets on speak to the effectiveness and soundness of our framework.

Exploring the Algorithn-Dependent Generalization of AUPRC Optimization with List Stability
Peisong Wen 1.2
Qianqian Xu
Zhiyong Yang" 1,2,4,5
Yuan He
Qingming Huang
Key Lab of Intell. Info. Process., Inst. Comput. Tech., CAS
School of Computer Science and Tech., University of Chinese Academy of Sciences
Allibaba Group
4 BDKM, University of Chinese Academy of Sciences
Peng Cheng Laboratory
(venpeisong202, sugiangiia))@ic..ac. en
(yangzhiyong21 quhuangg/ucaa an heyuan hataenhh@lllbbb baydallbbba-inn.com
Abstract
Stochastic optimization of the Area Under the Precision-Recall Curve (AUPRC) is crucial problem for machine learning. Although various algorithms have been extensively studied for AUPRC optimization, the generalization is only guaran- teed in the multi-query case. In this work, we present the first trial in the single- query generalization of stochastic AUPRC optimization. For sharper generaliza- tion bounds, we focus on algorithm-dependee algorithmic and theoretical obstacles to our destination. From an algorithmic per- spective, we notice that the majority of existing stochastic estimators are biased when the sampling strategy is biased, and is leave-one-ous unstable due to the non- decomposability. To address these issues, we propose a sampling-rate-invanne rnva-iiari unbiased stochastic estimator with superior stability. On top of this, the AUPRC optimization is formulated as composition optimization problem, and stochas- tic algorithm is proposed to solve this problem. From theoretical perspective, standard techniques of the algorithm-dependen generalization analysis cannot be directly applied to such listwise compositional optimization problem. To fill this gap, we extend the model stability from instancewise losses to listwise losses and bridge the corresponding generalization and stability. Additionally, we construct state transition matrices to describe the recurrence of the stability, and simplify calculations by matrix spectrum. Practically, experimental results on three image retrieval datasets on speak to the effectiveness and soundness of our framework.
generalization. There are both
1 Introduction
Area Under the Precision-Recall Curve (AUPRC) is a widely used metric in the machine learning community, especially in learning to rank, which effectively measures the trade-off between preci- sion and recall of ranking model. Compared with threshold-specifie recall@k, AUPRC reflects a more comprehensive performance by capturing all possible thresholds. In addition, literature has shown that AUPRC is insensitive toward data distributions [20], making it adaptable to largely skewed data. Benefiting from these appealing properties, AUPRC has become one of the standard metrics in various applications, e.g., retrieval [55, 58, 22, 41], object detection [45, 49, 15], medical diagnosis [50, 35]. and recommendation systems [16, 73, 1, 64, 2].
metries like accuracy and
Over the past decades, the importance of AUPRC has prompted extensive researches on direct AUPRC optimization. Early work focuses on full-batch optimization [45, 44, 26]. However, in
*Corresponding authors.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

the era of deep learning, the rapidly growing scale of models and data makes these full-batch al- gorithms infeasible. Therefore, in recent years, it has raised an increasing favor of the stochastic AUPRC optimization [9, 12, 31, 46]. Since AUPRC optimization is a stochastic dependent composi- tional optimization problem, general convergence rates are infeasible for AUPRC optimization. To fill this gap, [54, 70, 69] provide AUPRC optimization algorithms with provable convergence. See Appendix A for more on related work.
Despite the promoting performance of these methods in various scenarios, the generalization of AUPRC optimization algorithms is still an open problem. Some studies [17, 63] provide provable generalization for AUPRC optimization in information retrieval. In this scene, dataset consists of multiple queries, where each query corresponds to a of positive and negative samples. However, these results require sufficient queries to ensure small generalization errors, but leave the single- query case alone, iee, whether the generalization error tends to zero with the length of a single- query increasing is still unclear. This limits the adaptation scope of these methods. To fill this gap, in this paper we aim to design a stochastic optimization framework for AUPRC with a provable gegorithh-dependee
generalization performance in the single-query case.
The target is challenging in three aspects: (a) Most AUPRC stochastic estimators are biased with a biased sampling rate. Moreover, due to the non-decomposability, outputs of existing algorithms might change lot with slight changes in the training data, which is called leave-one-ota unstable in this paper. Such an unstability is harmful to the generalization. (b) The standard framework to analyze the sum of instancewise terms, while AUPRC involves listwise loss. (c) The stochastic optimization of AUPRC is two-level compositional optimization problem, which brings more complicated proofs of the stability.
generalization requires the objective function to be expressed as
In search of a solution to (a), we propose sampling-rate-invarian asymptotically unbiased stochas- tic estimator based on a reformulation of AUPRC. Notably, to ensure the stability [28, 39, 37, 38] of the estimator, the objective is formulated two-level compositional problem by introducing an auxiliary vector for the ranking estimation. Error analysis further supports the feasibility of our method, and inspires us to add a semi-variance regularization term. To solve this problem. we propose an algorithm with provable convergence that combines stochastic gradient descent (SGD), linear interpolation and exponential moving average.
Facing challenge (b), we extend instancewise model stability to listwise model stability, and cor- respondingly put forward the generalization via stability of listwise problems. On top of this, bridge the generalization of AUPRC and the stability of the proposed optimization algorithm.
As for challenge (c), since the variables to be optimized are typically updated alternately in the compositional optimization problem, we propose state transition matrices of these variables, and simplify the calculations of the stability with matrix spectrum.
In nutshell, the main contributions of this paper are summarized as follows:
Algorithmically, a stochastic learning algorithm is proposed for AUPRC optimization. The core of the proposed algorithm is a stochastic estimator which is sampling- caahiinng-rttiinnn ruteiinvaiannt asymptotically unbiased.
Theoreticallly, we present the first trial on the algorithm-dependent generalization of stochastie AUPRC optimization. To the best of our knowledge, it is also the first work to analyze the stability of stochastic compositional optimization problems.
Technically, extend the concept of the stability and generalization guarantee listwise non-convex losses, Then we simplify the stability analysis of compositional objective by matrix spectrum. These techniques might be instructive for other complicated metrics.
2 Problem Formulation
2.1 Preliminaries AUPRC
Notations.
Consider set of N examples S ((,,, v. independently drawn from sample space D = X x V, where X' is the input space and y = (-1, 1} is the label space. For sake of the presentation, denote the set of positive examples of S as S+ {x Jes, and similarly the set
N+

---

of negative examples is denoted as S = {x, J where N = | I. |S- With slight abuse of notation, we also denote that the dataset is sufficiently large, such that / + N-)
S U ST there is no ambiguity. Generally. we assume
P"y 1) == Our target is to learn a score function Aw X' + R with parameters w E Ω C Rd such that the scores of positive examples are higher than negative examples. Furthermore, when appling the score function to dataset S E XN, we denote hw X + RN,, where the k-th element of h (S)) has the top-k values of {hw (z=)a E S}. Denote the asymptotic upper bound on complexity as O, and denote asymptotically equivalent as x,
In this work, our main interest is optimize score function in the view of AUPRC:
J. Ply = 1//1((2)) 2 c) d (()w(()) 2 cly
AUPRC( (w; D)
TTPR(()
TTPR(C) + (1 FPF)(( d( cly 1),
where (x,,) 3) D. c refers a threshold, and TPR(c) (() 2 dy = F),()
P(h (x) 2 cly 0). For a finite set S, AUPRC is typically approximated by replacing the
distribution function P( (x) 2 cly = 1) with its empirical cumulative distribution function [8, 19]:
x TTP((huu
È *+~S- xTPR(h (x )) + (1 F.-.)FPP(MA (x AUPRC(W;
(2)
where (PR(c) = Exst (c (2))) ((o FPR(() = Ba-s- 110,1 hw (2))) L (x)
if æ < 0 or to (z) = 0 otherwise. It has been shown that AUPRC is unbiased estimator when
N+ /+N+ - N= )} + a and N 7 oo 18]. With the above estimation, we have the following
optimization objective:
1 π TPR(hu(at)) ]
FPR(hu (x (
min w
AUPRC (w; 1- AUPRC(W;
É a0+
(3)
where (xx) = x/(1+ (11+))) is concave and monotonically increasing. To make it smooth, surrogate
losses L,, 62 are used to replace fo,1 in FPR and TPR respectively, yielding the following surrogate objective:
FPR(h ):(1) ]
min f(w;
E x S
o
(4)
π
TPR(h (or ):62)
where TPR(c E2) Exnsi [62(c - hew (x))] FPR((; = Ea-s [L hww (x)) Specifi-
cally, when N /(N+ + N-) = n, equivalent to another commonly used formulation Average
Precision (AP) Loss:
Eans (hr(to( - Nww (2)))
AP Sw
(5)
Exnst (1 hw (x))
2.2 Stochastic Learning of AUPRC
Under the stochastic learning framework for instancewise losses, the empirical risk F(w; S) is ex- pressed as a sum of instancewise losses: F) = & Eæ~s f(w; where f(w; x) is the stochastic estimator of F)w;S). Different from instancewise losses, listwise losses like AUPRC require a batch of samples to calculate the stochastic estimator. Specifically, at each step, subset of S: == 2 U = is randomly drawn, where = consists of + positive examples and x consists of n negative examples. Then stochastic estimator of the loss function, denoted as f(w; 2), is computed with Similar to the instancewise case, consider variant of the empirical/population AUPRC risks as approximations, which a sum of stochastic losses w.r.t all posible z:
F(u:; S) M Σ f(w: 2), F(w) ES (F(w)(((w;S)))
(6)
where M is the number of all posible z. Unfortunately, due to the non-decomposability of the empir- ical AUPRC risk f(w;; S), it is tackle to determine the approximation emror between F(w;; S) and
3

---

(w;; S) in general. Nonetheless, in Sec. 3.3 we argue that by selecting proper f(w; z). F(w; S) can be asymptotically unbiased estimator of f(w; S), which naturally makes F(w) an asymptoti- cally unbiased estimator of 1 - AUPRC. In this case, f is said to be an asymptotically unbiased stochastic estimator. Moreover, if the unbiasedness holds under biased sampling rate, it is said to be sampling-rate-nnarian asymptotically unbiased.
Asymptotically Unbiased Stochastic AUPRC Optimization
In this section, will present our SGD-style stochastic optimization algorithm of AUPRC. In Sec. 3.1, we propose surrogate losses to make the objective function differentiable. In Sec. 3.2, we present details of the proposed stochastic estimator and the corresponding optimization algorithm. Analyses on approximation errors are provided in Sec. 3.3.
3.1 Differentiable Surrogate Losses
Since f0.1 appears in both the numerator and denominator of Eq. (4), simply implementing L, with a single function [56, 9, 54] will bring difficulty to analyze the relationship between
AUPRC (w;S) and S) This motivates us to choose & 2 f0.1. S fo.1. such that AUPRC (w; S f(u;; S), thus the original empirical risk could be optimized by minimizing its upper bound ((w:S), Concretely, & and la are defined as the one-side Huber loss and the one-side sigmoid loss:
2r/T x/T)) 0 x < T1
x 6<0, 0
exp(-x/T1) -1 (2(x) = exp(-x0/0 +1'
x <<< 0,
(xxx==
0,
I 2 TI.
x M
Here Ti, 72 > are hyperparameters. is convex and decreasing, which ensures the gap between positive-negative pairs is effectively optimized. Additionally, compared with the square loss and the exponential loss, & is more robust noises. E2 is Lipschitz continuous, and &g + Eo, with 72 + 0.
3.2 Stochastic Estimator of AUPRC
The key to a stochastic learning framework the design of the stochastic estimator (or the cor- responding gradients). iee., f(w; z). Existing methods [9, 74, 12] implement with AP (w; (Eq. (5)), which might suffer from two problems:
(P1) Comparing Eq. (4) and Eq. (5), it can be seen that only when n* /(n+ + + n=) ) + AP" is an asymptotically unbiased estimator. However, it is hardly satisfied since the sampling strategy is usually biased in practice.
(P2) Each term in the summation of AP is related to all instances of batch, leading weak leave-one-out stability, i.e., changing one instance might result in relatively large fluctua- tion in the stochastic gradient, especially when changing positive example.
To tackle the above problems, we first substitute FP with Pe (e] (xr) Jom (x))], and then introduce auxiliary vector e E R to estimate TPR. Formally, propose the following batch-based estimator:
1 - π Expz [h (x*) h (x)()) (x))
f(w; x) 10 f(w;
B x trug
(8)
E Evnel (xx - u)]
Such an estimator enjoys two advantages: in terms P1, is asymptotically unbiased regardless of the sampling rate (see Sec. 3.3 for detailed discussions); for P2, such that each positive example
substitute h (S*) +)
mini-batch only appears in one term. Ideally, can be consid- ered as using all positive examples in the dataset estimate TPR instead of that from mini-batch. With the fact that n >> nt, this makes the corresponding algorithm more stable. Moreover, based on the model stability, generalization bounds are available (see Sec. 4).

---

3.3 Analyses on Approximation Errors
In this subsection, we analyze errors from two approximations in the above algorithm: the gap between F(w; S) and the true AUPRC loss; 2) the gap between the interpolated scores o(hw (2+)) and the true scores fiw( (S+). Proofs are provided Appendix B.1.
Denote т = / + N) and To n /(n+ + n
We would like to show that for all w E Ω. (w; 2)] is an unbiased estimator when n - oc, no matter how To is chosen, while for
E_ (w; z)]. it holds only when To = Since only one model w is considered, we let w w the update rule of v (Eq. (10)), and we have the following proposition:
Proposition 1. Consider updating v with Eq. (10) for T steps, then have
E|u] = (lo(hu(( (x+) + (1- (v1 - EiØ (hw (zx))))) Varlu] & Varlo(hw 1) - B
Remark 1. Two conclusions could be drawn from the above proposition: first, if the linear in- terpolation is asymptotically unbiased (see next subsection). by choosing large T or setting
V1 E[o(h (2+)),, we have [E[o] se hSt)));; second, by choosing smaller B, vo is more likely to concentrate on (S*).
Proposition 2. Assume the linear interpolation is asymptotically unbiased.
Let ni
(xt) arrrr-s--l 161 (c- (cc-hulaa))1) x² (Vo- (22 (c -c- v]]]]. When Rî/n + O, ng/nt + O, then there exists a positive scale H, such that
E Eags|f(w; z)] & AUPRC" (w; Bags [AP (w: z)] L (1+ (To H) AUPRC' (w:S),
where Eo refers convergence in probability, and C S refers subsets described in Sec. 2.2.
Remark 2. The above proposition suggests that the proposed batch-based estimator is sampling- rate-invariant asymptotically unbiased, while AP tends to be larger when the sampling rate of the positive class is greater than the prior, and vice versa. We also provide a non-asymptotic result in Appendix B.2.
Simulation experiments are conducted as complementary to the theory. Following previous work [8]. the scores are drawn from three types of distributions, including binormal, bibeta and offset uniform. The results of binormal distribution are visualized Fig. 1, and detailed descriptions and more results are available in Appendix B.2. These results are consistent with the above remark.
Next further study the interpolation error. For the sake of presentation, denote p : [0 + IR to be an increasing score function describing (S+), where p(x) is the score in the bottom r- quantile of (S+). Similarly, let á to be the interpolation results of EA [h( (x+)) Assume that (x( are located in the (i/ )-quantiles of p. where i E [n+], such that p(i/n+) = p(i/n+)
and all interpolation intervals are with length 1 1/nt. The following proposition provides an upper bound of the approximation error (see [61] for proof):
Proposition 3 (Linear Interpolation Error). Let p. e be defined as above. Then we have
Pp pl I loc/ (8(n+)2)
Similar to the last subsection, simulation results are shown in Fig. 1(c), which shows the expected emrrr of linear interpolation ignorable.
3.4 Optimization Algorithm
In the rest of this section, we focus on how optimize F(w; The main challenge is de- sign update rules for such that it could efficiently and effectively approximate (S*) without full-batch scanning. To overcome the challenge, we propose an algorithm called Stochastic Opti- mization of AUPRC (SOPRC), which jointly updates model parameters w and the auxiliary vector v. summary of the detailed process is shown as Alg. 1. At step I, a batch data is sampled from the training set, and then compute the corresponding scores. Afterward, scores of positive examples are mapped into -imennnnoo vector with linear interpolation & as shown Alg. Pt-1 are updated with the interpolated scores in moving average manner.
5

---

Negatte Fostie
Ous
Irlop fics
Normwloee AUURIC
Natr PAL PAUIPICC
Derauit
2.5
0.
60
0.5
-55
133
1008
10000
138
1006
10000
3.
0.
0.4
0.
0.
13
Batch Size
Batch Size
Quantlle
(a) Density functions of
(b) Stochastic Estimation Errors with To 0.02 (left) and To = 0.2 (right).
(c) Interpolation Errors with No 0.03.
scores,
Figure I: Empirical analysis of estimation errors on simulation data.
Practically, n*tn" finite, causing inevitable estimation errors in f(w; Zi, v(+1). Notice that another factor influencing the stochastic estimation errors, i.e. K² and rzz To reduce them, it is ex- pected that the variance of positive (negative) scores small, which motivates to add variance regularization term. However, might force to reduce positive scores that higher than the mean value, which contrary our target. Therefore, we propose a semi aani-variance regularization term [4]:
Lvar
A
Σ (on
(bwr(x)) 22+
A
(Neo (2) 1 )²
where 1x*
n Σ
xrvt (x), Ht = 1 Lere- hw (x). A1, A2 are hyperparameters. Finally,
compute the gradients of flw; Ric, ve+1) Lvars and update parameters with gradient descent.
Algorithm 1 SOPRC
Algorithm 2 Score Interpolation Φ(.)
Input:
Training dataset S, maximum iterations
Input: real value vector u E R where n <
T, learning rate {ne) and (3:)=1-
N+, range of target values [b. B).
Output: model parameters wy+1-
Output: Interpolated vector m = é(u).
1: Initialize model parameters wi and U1-
I: Sort u in descending order.
2: for 1 to 7 do
2: Initialize m as 0 let Wg = mar (211
3: Sample a subset Zi, from S.
Ug b). Un+1 min(2u, -un B).
4: Compute hw, (z and map the results
3: for i 1 to m do
4: for j = -N (i-1) to N+ do
into @(hur (2 with Alg. 2.
5: Update v with
5:
my+ = [ jn/ N )ui-1
Vc+11 =(1 3.)vr
(10)
+(1 + jn/ in/N+ + - i) i)uu] /2
+ B. (2tt)
6: end for
6: Compute Sver with Eq. (9).
7: for j
N+ to N x++()+))
do
7:
Update the model parameter:
m, (i+ jnnNjnnNN/. N
Wi+1
wt T) V
(11)
+(jn/Nt -i)u)] /2
1}: Vf(w; Zi, 1141)-
end for
8:
end for
10: end for
4 Generalization of SOPRC via Stability
In this section, we turn to study the excess generalization error of the proposed algorithm. Formally, following standard settings [5], consider the test error of the model A(S) trained on the training set Our target is to seek an upper bound the excess error EA,s[F " arg minwen EA.s(PP (Fw")) ].. It can be decomposed as:
F(w*)) )], where
Es.A(P(A(S)) F(w")() = E... (F((S)) - F(A(S);)) + EESSSS))SS...PPP.. (F F(w))))
Estimation Error The estimation error sources from the gap of minimizing the empirical risk instead of the expected risk. Sec. 4.1, we provide detailed discussion on the estimation error. The optimization error measures the gap between the minimum empirical risk and the results obtained by the optimization
Optimization Error

---

algorithm, which will be studied in Sec. 4.2. Detailed proofs of this section are available in Appendix C. Before the formal presentation, we show the main assumptions:
Assumption (Bounded Scores & Gradient). (f(w; )1 - B, V (al:::))) ))l S for all un E Ω.
Assumption (L-Smooth Loss).
[V((w;)) f((: _ L| for all w v E Ω2
Assumption (Lipsehitz Continuous Functions). [6] E (7) - ر - æ (22(1)) (z) S
L2 J for all z, ū E [-2B, (lØ(=) - 6())ll2 - C || z|12 for all
4.1 Generalization of AUPRC via Model Stability
The generalization of SGD-style algorithms for instancewise loss has been widely studied with sta- bility measure [39, 21, 28]. However, these results could not be directly applied to listwise losses like AUPRC. The main reason is that the estimation of each stochastic gradient requires a list of examples, and the estimation is usually biased. Nonetheless, to bridge the optimization algorithm and the generalization of AUPRC, we propose a listwise variant of on-average model stability [39] follows:
Definition 1 (Listwise On-average Model Stability). Let S {(x )1) and S { v:) be two sets of examples whose features are drawn independently from X. For any i == 1,... .... N, denote 8(1) = {(m1,11) Ui),... (xi-11 1i-) (Ti, (mi+1, 11+1). (Inn Un)). A stochastic algorithm
listwise on-average model (ct, ( )-stable if the following condition holds:
E S,5A
1 N+
Σ W==1
A(S) - A(S
S set,
1 N-
=E Wi=-1
A(S) - |
SE.
The following theorem shows that the estimation error is bounded by the above-defined stability: Theorem 1 (Generalization via Model Stability). Let stochastic algorithm A be listwise on- average model (et c --stable and Asmp. 1 holds. Then we have
Es,A [F(A(S)) - F(A(S);)) s ((nnct+ncc>
(12)
With the above theorem, now we only need to focus on the model stability of the proposed algorithm. Notice that in Alg. both w, and ur are updated each step, thus we have consider the stability of both simultaneously. The following lemma provides a recurrence for the stability w, and Vt.
Lemma 1. Let S, S,S,S(0) be constructed as Def. and Asmp. 1, 3 hold. Let We and {w (0) } be produced by Alg. with S and S(t), respectively. Denote = max ( Leurs Ln/nt, C. B, G/2, BJ),
mi (8)
[ |w, -w, (1)
v. 11 1 ]]"
m No Ey. Es.A m (2)
|0
m,
N+ Σ -1 ES.A m! Then for all E [T], by setting Be S B/nt, we have
m S (Ia R mnt m S (Ig R₁) m,
(13)
where I3 is the x 3 identity matrix and
2
L(1-3
Lig N
2
Lneen
R
L3t
N+
0
R
LBt
N+
0
N-
0
(14)
N
0
Finally, we utilize the matrix spectrum of R, and R2 to show that the model stability w.r.t. Alg. decreases as the number of training examples increases (see Appendix C.2 for details):
Theorem 2. Let X LC,,(+ /1 f + B), and assumptions in Lem. I hold. By setting 1): S 3. = B x 1/n0t and T < N+, Alg. 1 is list on-average model stable with
C.
7
(Tn+)>a1 221
((Tn)) x2
E =
.-=0
, -0
(15)
N+
N
7

---

Table Quantitative results on SOP, iNaturalist, and VehicleID. All methods are trained with train-
ing sets. The best and the second best results are highlighted in soft red and soft blue, respectively.
Stanford Online Products mAUPRC
iNaturalist @@1
PKU VehicleID
Methods
@@1
R@ 10
mAUPRC
R@4 4
mAUPRC
R@1 I
R@5
Contrastive loss [27]
57.73
77.60
89.31
27.99
54.19
71.12
67.26
87.46
94.60
Triplet loss [32]
58.07
78.34
90.50
30.59
60.53
77.62
70.99
90.09
95.54
MS loss [7]]
60.10
79.64
90.38
30.28
63.39
78.50
69.15
88.82
95.06
XBM [72]
61.29
80.66
91.08
27.46
59.12
75.18
71.24
92.78
95.83
SmoothAP [9]
61.65
81.13
92.02
33,92
66.13
80.93
72.28
91.31
96.05
DIR [58]
60.74
80.52
91.35
33.51
64.86
79.79
72.72
91.38
96.10
FastAP [12]
57.10
77.30
89.61
31.02
56.64
73.57
70.82
89.42
95.38
AUROC [25]
55.80
77.32
89.64
27.24
60.88
77.76
58. 12
81.73
91.92
BlackBox [52]
59.74
79.48
90.74
29.28
56.88
74.10
70.92
90.14
95.52
Ours
62.75
81.91
92.50
36.16
68.22
82.86
74.92
92.56
96.43
4.2
Convergence of AUPRC Stochastic Optimization
Following previous work [24, 34J, study the optimization enror of the proposed algorithm under the Dolyak-tojasieviii (PL) condition. It has been shown that the PI. condition holds for several widely used models including some classes of neural networks [13, 42].
Assumption 4 sume F satisfy the expectation version of PL condition with parameter μ > ie.,
Condition [34, 37J). Denote w = arg minwes F(w). As-
1 Es[F(w:; S) - F(w")] < Bsll
(16)
μ
The main difference the existing convergence analysis on non-convex optimization is that the gradient estimation is biased. Nonetheless, we show that the bias terms from Alg. tend to 0 with sufficient training data and training time (see Appendix C.3), leading to the following convergence:
21 and B = 3 x 1/n we have Theorem 3. Ler Asmp. 1, 3, hold. By setting p(t+ifz
E [A(F(wt+1) F(w")))))))))))"))))()") O (n* T 1/N+).
(17)
Theorem 4. Let assumptions Thm. and hold. By setting T x (N+) 2 ()+) EXTI, we have
Bs.AlF(A(S)) -A((((()))(("") =0 ((N+) A+1
+ +0 ((N-)- IA7T (n 2X-7 (18)
Remark Recall that X LC + -1-3++ and = 4/u, when small, we have X RO 4L/u. Here L/μ is a condition number determined by the model and the generaliza- tion bound is O ((N+)=221) (nn (n²))/33 + +NN (N-) ) (n 413). As X increases, it increases to O ((N+)-1122
surrogate losses. Notice that n² & N =n
N=, -
+N-)-11/2 33/2)
Experiments
To validate the effectiveness of the proposed method, we conduct empirical studies on image retrieval task, in which data distributions largely skewed and AUPRC is commonly used as an evaluation metric. More detailed experimental settings are provided in Appendix D.I. The source code is available in https //g github. com com/
5.1 Implementation Details
Datasets. We evaluate the proposed method three image retrieval benchmarks with various domains and scales, including Stanford Online Products (SOP)² [48], PKU VehicleID [43] and
/twp////////////taao.oo./////eea Phttps://wws http://ppw../eeeoooooc/////ooaaa
Licensed MIT. Data files c Original Authors.

---

iNaturalist" [68]. We follow the official setting to split a test set from each dataset, and then further split the rest into training set and validation set by a ratio of 9
Network Architecture. The feature extractor is implemented with ResNer-50 [29] pretrained on ImageNet [60]. Following previous work [12, 9I, the batch normalization layers are fixed during training, and the output embeddings are mapped to 512-d with linear projection. Given L2 nor- malized embeddings of a query image e, and a gallery list {e:}.. the scores are represented by the cosine similarity e, e, for all i.
Optimization Strategy. In the training phase, the input images are resized such that the sizes of the shorter sides are 256. Afterward, we applied standard data augmentations including random cropping (224 x 224) and random flipping (50%). The model parameters are optimized in an end- to-end manner shown in Alg. 1, where B = 0.001 and the weight decay is set to 4 10-4, The default batch size is set to 224, where each mini-batch is randomly sampled such that there are exactly 4 positive examples per category. The learning rates validation sets: for SOP, the learning rate are initialized as 0.01 and decays by 0.1 at the 15k and 30k iterations, T = 50k; for VehicleID, the learning rate are initialized as 0.001 and decays by 0.1 at the 40k and 80k: iterations, T = 100k; for iNaturalist, the learning rate are initialized as 0.001 and decays by 0.1 at the 80k and 110k iterations, T = 130k.
tuned according to performance on
Competitors. We compare two types of competitors: 1) Pairwise Losses, including Contrastive Loss [27]. Triplet Loss [32], Multi Multi-Similarity (MS) Loss [71], Cross-Batch Memory (XBM) [72]. These methods construct loss functions with image pairs or triplets. 2) Ranking-Based Losses, including SmoothAP [9], FastAP [12], DIR [58], BlackBox [33], and Area Under the ROC Curve
Loss (AUROC) [76]. These methods directly optimize the vanking-based metrics.
Evaluation Metries. In all experiments, we adopt evaluation metries: mean AUPRC (MAUPRC) and Recall@k. mAUPRC is also called mean average precision (mAP) in literature, which takes the mean value over the AUPRC of all queries. Recall@1 measures the probability that at least one positive example is ranked in the top-k list.
5.2 Main Results
We evaluate all methods with mean AUPRC (mAUPRC) and Recall@k. mAUPRC measures the mean value of the AUPRC over all queries, a.k.a. mean average precision (mAP). The performance comparisons on test sets are shown in Tab. 1. Consequently, we have the following observations: 1) In all datasets, the proposed method surpasses all competitors in the view of mAUPRC, especially in the large-scale long-tailed dataset iNaturalist. This validates the advantages of our method in boosting the AUPRC of models. 2) Compared to pairwise losses, the AUPRC/AP optimization methods enjoy better performance generally. The main reason is that pairwise losses could only optimize models indirectly by constraining relative scores between positive and negative example pairs, while ignoring the overall ranking. 3) A Although some pairwise methods like XBM have a satisfying performance on Recall@1 I, their mAUPRC is relatively low. It is caused by the limitation of Recall @1 I, i.... it focuses on the top-1 score while ignoring the ranking of other examples. What's s more, this phenomenon shows the inconsistency of Recall @k and AUPRC, revealing the necessity of studying AUPRC optimization. More results are available in Appendix D.2.
To qualitattvely demonstrate the effect of the proposed method, we also show the mean PR curves and convergence curves in Fig. 2. The left two subfigures demonstrate that the proposed method achieves can effectively improve AUPRC. The right subfigure shows the affect of batch size, from which can be seen that large batch size leads to better performance. One of the reasons is that small batch size will amplify the AUPRC stochastic estimation error. Such a problem have been addressed by maintaining inner gradient estimations [54, 70, 75]. Unfortunately, when applied to image retrieval problems, it needs to maintain intermediate variables for each positive pair, bringing high complexity in time and space, thus we leave this problem as further work.
5.3 Ablation Studies
We further investigate the effect of different components of the proposed method. Results are shown in Tab. 2, and more detailed statements and analyses are as follows.
http://////gggoooooo//////aaaaat http:///ww/..aaaaa//////a/////ta Licensed MIT.

---

1.0
Pircicon
MAUPRO
MAUPRC
0.4
-186
FastA
B5 -5-111
Curs
SmootDAP
B5 65
0.0
0.0
0.2
04
0.6
0.8
Mean Recall
Figure 2: Qualitative results on iNaturalist. Left most: mean PR curves of different methods. Right two: convergence different methods and batch sizes terms of mAUPRC in the validation set.
Table 2: Ablation study over different components of our method on iNaturalist.
No.
Unb. Est.
with 2t.
with Lear
Opt.
mAUPRC
R@1
@4
R@32
X
SGD
34.58
66.35
81.04
89.80
92.72
SGD
35.84
67.08
81.68
90.17
92.98
3
v
V
SGD
35.99
67.50
82.03
90.44
93.26
4
V
V
SGD
36.16
68.22
82.86
91.02
93.71
5
V
Adam
36.20
68.48
82.70
90.96
93.63
Effeet of Unbiased Estimator. To show the performance drop caused by the biased estimator, we replace the prior in Eq. (8) with n n+/(n /(n+ + = Comparing line and line 2, using the unbiased estimator increases the mAUPRC by 1.3%, which is consistent with our theoretical results in Sec. 3.3. Notably, the unbiased estimator is the main source of improvements in terms of mAUPRC.
Effeet of vt. To show the effect of introducing o, to estimate @(S+). ), we directly use d(z+) instead in the first two lines. Comparing line and line 3, using di could bring consistent improvements due to the better generalization ability.
Effeet of Lvar. We show that shrinking variances could reduce the batch-based estimation errors. Comparing line 3 and line 4, it can seen that Lvar further boosts the proposed method. Effeet of Optimizer. Comparing line 4 and line 5, it can be seen that the choice of optimizer only has a slight influence.
Conclusion & Future Work
In this paper, we present stochastic learning framework for AUPRC optimization. To begin with, we propose stochastic AUPRC optimization algorithm based on an asymptotically unbi- ased stochastic estimator. By introducing auxiliary vector to approximate the scores of positive examples, the proposed algorithm more stable. On top of this, we study algorithm-dependent gen- eralization. First, we propose list model stability to handle listwise losses like AUPRC, and bridge the generalization and the stability. Afterward, we show that the proposed algorithm is stable, lead- Experiments
ing to upper bound of the generalization advantages of the proposed framework. One limitation is the convergence rate controlled by the scale of the dataset. In the further, will consider techniques like variance reduction improve the convergence rate, and jointly consider the corresponding algorithm-dependent generalization.
three benchmarks validate the
Acknowledgments
This work was supported in part by the National Key R&D Program of China under Grant 2018AAA0102000, in part by National Natural Science Foundation of China: U21B2038. 61931008, 62 6212200758 and 61976202, in part by the Fundamental Research Funds for the Cen- tral Universities. in part by Youth Innovation Promotion Association CAS, in part by the Strategic Priority Research Program of Chinese Academy of Sciences, Grant No. XDB28000000, in part by the China National Postdoctoral Program for Innovative Talents under Grant BX2021298 and in part by China Postdoctoral Science Foundation under Grant 2022M713101.
10

---

References
[1] Shilong Bao, Qianqian Xu, Ke Ma, Zhiyong Yang, Xiaochun Cao, and Qingming Huang. Collahorative preference embedding against sparse labels. In ACM International Conference on Multimedia, pages 2079-2087, 2019.
[2] Shilong Bao, Qianqian Xu, Zhiyong Yang, Xiaochun Cao, and Qingming Huang. Rethinking collabora- tive metric learning: Toward an efficient alternative without negative sampling. IEEE Trunsactions on Pattern Analysis and Machine Intelligence, 2022.
[3] Peter Bartlett and Shahar Mendelson. Rademacher and gaussian complexities: Risk bounds and struc- tural results. Journal of Machine Learning Research, 3(Nov):4633-82,, 2002.
[4] Shaun A Bond and Stephen E Satchell. Statistical properties of the sample semi-variance. Applied Mathematical Finance, 944:211--33, 2002.
[5] Léon Bottou and Olivier Bousquet. The tradeoffss of large scale learning. Advances in Neural Information Processing Systems, 20, 2007.
Stéphane Boucheron, Gábor Lugosi, and Pascal Massart. Concentration inequalities: nonasymptotic theory of independence. Oxford university press, 2013.
[7] Olivier Bousquet and André Elisseeff. Stability and generalization. Journal of Machine Learning Re- search, 2:499-526, 2002.
[8] Kendrick Boyd, Kevin H Eng, and C David Page. Area under the precision-recall recall curve: point estimates and confidence intervals. In ECMI PKDD, pages 451-466. Springer, 2013.
[9] Andrew Brown, Weidi Xic, Vicky Kalogeiton, and Andrew Zisserman. Smooth-ap: Smoothing the path to- wards large-scale image retrieval. European Conference on Computer Vision, pages 677 694. Springer, 2020.
[10] Christopher Burges, Rohert Ragno, and Quoc I.c. Learning to rank with nonsmooth cost functions. Ad- vances in Neural Information Processing Systems, 19:193-200, 2006.
[11] Christopher JC Burges. From ranknet to lambdarank to lambdamart: An overview. Learning, 11(23- 581):81, 2010.
[12] Fatih Cakir, Kun He, Xide Xia. Brian Kulis, and Stan Sclaroff. Deep metric learning rank. In JEEE/CVF Conference on Computer Vision and Pottern Recognition, pages 1861-1870, 2019.
[13] Zachary Charles and Dimitris Papailiopoulos. Stability and generalization of learning algorithms that converge to global optima. In International Conference on Machine Learning, pages 745-754. PMLR, 2018.
[14] Kean Chen, Jianguo Li, Weiyao Lin, John See. Ji Wang. Lingyu Duan, Zhibo Chen, Changwei He, and Junni Zou. Towards accurate one-stage object detection with ap-loss. In IREF/CVF Conference Computer Vision and Pattern Recognition, pages $1 199-17,,, 2019.
[15] Kean Chen, Weiyao Lin, John See, Wang, Junni Zou, et al. Ap-loss for accurate ste-stage object detection, IEEE Transactions on Pattern Analysis and Machine Intelligence, 2020.
[16] Ting Chen, Yizhou Sun, Yue Shi, and Liangjie Hong. On sampling strategies for neural network- collahorative filtering. In ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 767-776, 2017.
[17] Wei Chen, Tic- Yan Liu, Yanyan Lan, Zhi-Ming Ma, and Hang Li. Ranking measures and loss functions in learning to rank. Advances in Neural Information Processing Systems, 22:315-322 2009.
[18] Yuansi Chen, Chi Jin, and Bin Yu. Stability and convergence trade-off of iterative optimization algorithms. arXiv preprint arXiv: 1804.884111 2018.
[19] Stéphan Clémençon and Nicolas Vayatis. Nonparametric estimation of the precision-reed -ecaal curve. In International Conference on Machine Learning, pages 185-192. 2009,
[20] Jesse Davis and Mark Goadrich. The relationship between precision-recal. and roc curves. In Interna- tional Conference on Machine Learning, pages 233-240, 2006.

---

[21] Andre Elisseeff. Theodoros Evgeniou, Massimiliano Pontil, and Leslie Pack Kaelbing. Stability of ran- domized learning algorithms. Journal of Machine Learning Research, 6(1), 2005.
[22] Martin Engilherge, Louis Chevallier, Patrick Pérez, and Matthieu Cord. Sodeep: a sorting deep net to learn ranking loss surrogates. In IEEF/CVF Conference on Computer Vision and Pattern Recognition, pages 10792-10801, 2019.
[23] Dylan J Foster, Spencer Greenberg, Satyen Kale, Haipeng Luo, Mehryar Mohri, and Karthik Sridharan. Hypothesis set stability and generalization. Advances in Neural Information Processing Systems, 32, 2019.
[24] Dylan J Foster, Ayush Sekhari, and Karthik Sridharan. Uniform convergence of gradients for non-convex learning and optimization. Advances in Neural Information P Processing Systems, 31, 2018.
[25] Wei Gao and Zhi-Hua Zhou. On the consistency of auc pairwise optimization. In International Conference Machine Learning, 2015.
[26] Mark Goadrich, Louis Oliphant, and Jude Shavlik. Gleaner: Creating ensembles of first-order clauses to improve recall- rrell-precision curves. Muchine Learning, 64(1-3):231 (11-))223112-111 2111261,,200 2006.
[27] Raia Hadsell, Sumit Chopra, and Yann LeCun. Dimensionality reduction by learning an invariant map- ping. In /EEE/CVF Conference on Computer Vision and Pattern Recognition, volume 2, pages 1735-1742. IEEE, 2006.
[28] Moritz Hardt, Ben Recht, and Yoram Singer. Train faster, generalize better: Stability of stochastic gradient descent. In International Conference on Machine Learning, pages 1225-1234, 2016.
[29] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 770-778, 2016.
[30] Kun He, Fatih Cakir, Sarah Adel Bargal, and Stan Sclaroff. Hashing as twereware learning to rank. In IEFF/CVF Conference on Computer Vision and Pattern Recognition, pages 4023-4032, 2018.
[31] Paul Henderson and Vittorio Ferrari. End-to-end training of object class detectors for mean average precision. Asian Conference on Computer Vision, pages 198-213. Springer. 2016.
[32] Elad Hoffer and Nir Ailon. Deep metric learning using triplet network. In International workshop on similariry-based pattern recognition, pages 84-92. Springer, 2015.
[33] Qijia Jiang. Olaoluwa Adigun. Harikrishna Narasimhan, Mahdi Milani Fard, and Maya Gupta. Optimiz- ing black-box metrics with adaptive surrogates. In International Conference on Machine Learning, pages 4784-4793. PMLR, 2020.
[34] Hamed Karimi, Julie Nutini, and Mark Schmidt. Linear convergence of gradient and proximal-gradient methods under the polyak-lojasiewiez condition. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases, pages 795 811. Springer, 2016.
[35] Joon-myoung Kwon, Youngnam Lec, Yeha Loe, Scungwoo Lee, and Jinsik Park. An algorithm based on deep learning for predicting in-hospital cardiac arrest. Journal of the American Heart Association, 7(3))e008678, 2018.
[36] Yunwen Lei, Antoine Ledent, and Marius Kloft. Sharper generalization bounds for pairwise learning. Advances Neural Information Processing Systems, 33:21236 222466 2020.
[37] Yunwen Lei, Mingrui Liu, and Yiming Ying. Generalization guarantee of sgd for pairwise learning. Advances in Neural Information Processing Systems, 34, 2021.
[38] Yunwen Lei, Zhenhuan Yang, Tianbao Yang, and Yiming Ying. Stability and generalization of stochastic gradient methods for minimax problems. In International Conference Machine Learning, pages 6175- 6186. PMLR, 2021.
[39] Yunwen Lei and Yiming Ying. Fine-grained analysis of stability and generalization for stochastic gradient descent. In International Conference on Machine Learning, pages 5809 5819, 2020.
[40] Jian Li, Xuanyuan Luo, and Mingda Qiao. On generalization error hounds of noisy gradient methods for non-convex lcarning. In International Conference on Learning Representations, 2019.
[41] Zhuo Li, Weiqing Min, Jiajun Song, Yaohui Zhu, Liping Kang, Xiaoming Wei, Xiaolin Wei, and Shuqiang Jiang. Rethinking the optimization of average precision: Only penalizing negative instances before posi- tive ones is enough. arXiv preprint 2rXiv:2102.046440 2021.
12

---

[42] Chaoyue Liu, Libin Zhu, and Mikhail Belkin. Loss landscapes and optimization in over- prramearamteri non-linear systems and neural networks. Applied and Computational Harmonic Analysis, 2022.
[43] Hongye Liu, Yonghong Tian, Yaowei Wang. Lu Pang. and Tiejun Huang. Deep relative distance learning: Tell the difference between similar vehicles. In IEEE/CVF Conference on Computer Vision and Pottern Recognition, pages 2167-2175, 2016.
[44] Donald Metzler and Bruce Croft. A markov random field model term dependencies. In Interna- tional ACM SIGIR Conference on Research and Development Information Retrieval, pages 472-479, 2005.
[45] Pritish Mohapatra, CV Jawahar, and M Pawan Kumar. Efficient optimization for average precision svm. Advances in Neural Information Processing Systems, 27:2312-2320, 2014.
[46] Pritish Mohapatra, Michal Rolinek, CV Jawahar, Vladimir Kolmogorov, and M Pawan Kumar. Efficient optimization for rank-based loss functions. In IEEE/CVF Conference Computer Vision and Pottern Recognition, pages 3693-3701, 2018.
[47] Wenlong Mou, Liwei Wang, Xiyu Zhai, and Kai Zheng. Generalization bounds of sgld for non-convex learning: Two theoretical viewpoints. Conference on Learning Theory, pages 605-638. PMLR, 2018.
[48] Hyun Oh Song, Yu Xiang, Stefanie Jegelka, and Silvio Savarese. Deep metric learning via lifted structured feature embedding. In JEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 4004- 401 2, 2016.
[49] Kemal Oksuz, Baris Can Cam, Emre Akbas, and Sinan Kalkan. A ranking-based. balanced loss function unifying classification and localisation in object detection. In Advunces in Neural Information Processing Systems, 2020.
[50] Brice Ozenne, Fabien Subtil, and Delphine Hancort-Boulch The precision-recall curve overcame the optimism of the receiver operating characteristic curve in rare discases. Journal of clinical epidemiology, 68(8):855-859, 2015.
[51] Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. Pytorch: An imperative style, high- performance deep learning library. Advances in Neural Information Processing Systems, 32:8026-888 8027, 2019.
[52] Marin Vlastelica Pogančić, Anselm Paulus, Vit Musil, Georg Martius, and Michal Rolinek. Differentia- tion of blackbox combinatorial solvers. In International Conference on Learning Representations, 2019.
[53] Tomaso Poggio and Christian R Shelton. On the mathematical foundations of learning, American Mathe- matical Society, 39(1):1-49, 2002.
[54] Qi Qi, Youzhi Luo, Zhao Xu, Shuiwang Ji, and Tianbao Yang. Stochastic optimization of areas under precision-recall curves with provable convergence. Advances in Neural Information Processing Systems, 34, 2021.
[55] Tao Qin, Tie-Yan Liu, and Hang Li. general approximation framework for direct optimization of information retrieval measures. Information Retrieval, 13(4)3375-397, 2010.
[56] Tao Qin, Xu-Dong Zhang, Ming-Feng Tsai, De-Sheng Wang, Tie-Yan Liu, and Hang Li. Query-level loss functions for information retrieval. Information Processing & Management, 44(2):838-855, 2008.
[57] Vijay Raghavan, Peter Bollmann, and Gwang S Jung. A critical investigation of recall and precision as measures of retrieval system performance. ACM Transactions on Information Systems, 7(3):205-22,, 1989.
[58] Jerome Revaud, Jon Almazán, Rafael S Rezende, and Cesar Roberto de Souza. Learning with average precision: Training image retrieval with listwise loss. In International Conference on Computer Vision, pages 3107-51166 2019.
[59] William H Rogers and Terry Wagner. finite sample distribution free performance bound for local discrimination rules. The Annals of Statistics, pages 506-514, 1978.
[60] Olga Russakovsky, Jia Deng, Hao Su, Jonathan Krause, Sanjeev Satheesh, Sean Ma, Zhiheng Huang. An- drej Karpathy, Aditya Khosla, Michael Bernstein, et al. Imagenet large scale visual recognition challenge. International Journal of Computer Vision, (15(3):21-2255) 2015.
13

---

[61] Timothy Sauer. Numerical analysis. Addison-Wedt Wesley Publishing Company, 2011.
[62] Shai Shalev-Shwartz, Ohad Shamir, Nathan Srebro, and Karthik Sridharan. Learnability, stability and uniform convergence. Journal of Machine Learning Research, 11 11:2635-2670, 2010.
[63] Yang Song, Alexander Schwing, Raquel Urtasun, et al. Training deep neural networks via direct loss minimization. In International Conference on Machine Leurning, pages 2169-2177. PMLR, 2016.
[64] Viet-Anh Tran, Romain Hennequin, Jimena Royo-I.ctelier, and Manuel Moussallam. Improving collah- orative metric learning with efficient negative sampling. In International ACM SIGIR Conference on Research and Development in Information Retrieval, pages 1201-1204, 2019.
[65] Evgeniya Ustinova and Victor Lempitsky. Learning deep embeddings with histogram loss. In D. Lee, Advances in Neural Information Processing M. Sugiyama, U. Luxburg, Guyon, and R. Garnett, Advances Systems, volume Curran Associates, Inc., 2016.
[66]
Leslie G Valiant. theory of the learnable. Communications of the ACM, 27(11:1133331111 1984.
[67]
Aad W Van der Vaart. Asymptotic statistics, volume 3. Cambridge university press, 2000.
[68] Grant Van Horn, Oisin Mac Aodha, Yang Song, Yin Cui, Chen Sun, Alex Shepard, Hartwig Adam, Pictro Perona, and Serge Belongic. The inaturalist species classification and detection dataset. In IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 8769-8778, 2018.
[69] Bokun Wang and Tianbao Yang. Finite-sum coupled compositional stochastic optimization: Theory and applications. In International Conference on Machine Learning, pages 23292-23317, PMLR, 2022.
[70] Guanghui Wang, Ming Yang. Lijun Zhang, and Tianbao Yang. Momentum accelerates the convergence of stochastic aupre maximization. In International Conference on Artificial Intelligence and Statistics, pages 3753-3771, PMIR, 2022.
[71] Xun Wang, Xintong Han, Weilin Huang, Dengke Dong, and Matthew Scott. Multi-similarity loss with general pair weighting for deep metric learning. IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 5022-5030, 2019.
[72] Xun Wang, Haozhi Zhang, Weilin Huang, and Matthew Scott. Cross-hatch memory for emhedding learning. In IEEF/CVF Conference on Computer Vision and Pottern Recognition, pages 6388-6397, 2020.
[73] Zitai Wang, Qianqian Xu, Ke Ma, Yanghangyan Jiang, Xiaochun Cao, and Qingming Huang. Adversarial preference learning with pairwise comparisons. In ACM International Conference Multimedia, pages 656 664, 2019.
[74] Fen Xia, Yan Liu, Jue Wang, Wensheng Zhang, and Hang Li. Listwise approach to learning to rank: theory and algorithm. In International Conference Machine Learning, pages 1192-1199, 2008
[75] Tianbao Yang. Algorithmic foundation of deep x-risk optimization. arXiv preprint arXiv:2206.00439, 2022.
[76] Zhiyong Yang, Qianqian Xu, Shilong Bao, Xiaochun Cao, and Qingming Huang. Learning with mul- ticlass Theory and algorithms. IEEE Transactions Pattern Analysis and Machine Intelligence, 2021.
[77] Yisong Yue, Thomas Finley, Filip Radlinski, and Thorsten Joachims. A support vector method for op- timizing average precision. International ACM SIGIR Conference on Research and Development in Information Retrieval, pages 271-278, 2007.
14

---

Checklist
For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] Please Sec. 6.
(c) Did you discuss any potential negative societal impacts of your work? [No] We haven't found any negative societal impact of our work.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yss]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proof's of all theoretical results? [Yes]
3. If you experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either the supplemental material or as URL.)? [Yes]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes]
(c) Did you report eтror bars (c.g.. with respect the random seed after running experi-
ments multiple times)? [No] Because it would be too computationally expensive.
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes]]
(b) Did you mention the license of the assets? [Yes]
(c) Did you include any new assets either the supplemental material or as URL? [Yes]
(d) Did you discuss whether and how consent obtained from people whose data you're using/curating? [No] Assets we used are open source.
(c) Did you discuss whether the data you are using/curating contains personally identifi- able information or offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid participants and the total amount spent on participant compensation? [N/A]
15


Reviews:
[{"review_id": "qF_y9WIJ1V1", "reviewer": "Reviewer_RxCi", "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.", "questions": "Please see the weaknesses for my main concerns. Some minor issues are given as follows:\n- The performance gain is more significant in iNaturalist than SOP. What’s the difference between these two datasets?\n- How to determine the prior $\\pi$ in the image retrieval task?\n", "limitations": " The limitations and potential negative societal impact have been described.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- 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.\n- Formal theoretical interpretation of the components of the proposed method. This may inspire future work along this line.\n- The extensive experiments have validated the proposed method. The ablation studies clearly present the effect of each component.\n\nWeaknesses:\n- The experiment details of the competitors need to be more specific to ensure fair comparisons.\n- 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?", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "kq61ulbapb6", "reviewer": "Reviewer_8mrY", "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.", "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?\n2. 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", "rating": 7, "confidence": 5, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The theoretical results of this paper are solid in the following aspects:\n1. 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.\n2. 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.\n3. By jointly considering the convergence and the generalization, this work provides guidance to find the trade-off between convergence and generalization of AUPRC optimization.\n4. The main results are well presented and clearly proved.\n\nMy 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.\n\nOverall, this paper addresses some important theoretical issues of AUPRC optimization, and I tend to accept this paper.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "8bwgJYFnrdb", "reviewer": "Reviewer_qm2w", "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.", "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.", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "I consider this work novel and sound in three aspects:\n1) 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.\n2) 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.\n3) The main claims are properly verified on both simulation and real-work data.\n\nThe main weakness of this work is missing explanations/analyzes of some techniques:\n1) 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.\n2) The time consumption of the proposed score interpolation is $O(N^+)$. It might slow down the training process.\n\nTo sum up, this paper looks solid on both technical and theoretical parts. The presentation is overall well organized. Therefore, I recommend accepting this paper.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept