Simple Stochastic and Online Gradient Descent Algorithms for Pairwise Learning
Authors: Zhenhuan Yang
Yunwen Lei
Puyu Wang
Tianbao Yang
Yiming Ying
Venue: NeurIPS 2021 Poster (2021)
Keywords: Pairwise Learning
Online (Stochastic) Gradient Descent
Stability and Generalization
Differential Privacy

Abstract: Pairwise learning refers to learning tasks where  the loss function depends on a pair of  instances. It instantiates many important machine learning tasks such as bipartite ranking and metric learning. A popular approach to handle streaming data in pairwise learning is an online gradient descent (OGD) algorithm, where one needs to pair the current instance with a buffering set of previous instances with a sufficiently large size and therefore suffers from a scalability issue. In this paper, we propose simple stochastic and online gradient descent methods for pairwise learning. A notable difference from the existing studies  
is that we only pair the current instance with the previous one in building a gradient direction, which is efficient in both the storage and computational complexity. We develop novel stability results, optimization, and generalization error bounds for both convex and nonconvex as well as both smooth and nonsmooth problems. We introduce novel techniques to decouple the dependency of models and the previous instance in both the optimization and generalization analysis. Our study resolves an open question on developing meaningful generalization bounds for OGD using a buffering set with a very small fixed size. We also extend our algorithms and stability analysis to develop differentially private SGD algorithms for pairwise learning which significantly improves the existing results.

Simple Stochastic and Online Gradient Descent Algorithms for Pairwise Learning
Zhenhuan Yang!*
Yunwen Lei Puyu Wang? Tianbao Yang* Yiming Ying' University at Albany, SUNY, Albany, NY University of Birmingham, Birmingham CCity University of Hong Kong, Hong Kong *University of lowa City, IA zyang6@ albany.edu, y. @ hhbam.cc.u, puyuwang @cityu.edu.hk, tianbao-yang @ uiowa.edu, vying@albanyy
Abstract
Pairwise learning refers learning tasks where the loss function depends on a pair of instances. It instantiates many important machine learning tasks such as bipartite ranking and metric learning- popular approach to handle streaming data in pairwise learning is an online gradient descent (OGD) algorithm, where one needs to pair the current instance with a buffering set of previous instances with sufficiently large size and therefore suffers from scalability issue. In this paper, we propose simple stochastic and online gradient descent methods for pair- wise learning. A notable difference from the existing studies is that we only pair the current instance with the previous one in building a gradient direction, which is efficient in both the storage and computational complexity. We develop novel stability results, optimization, and generalization error bounds for both convex and nonconvex as well as both smooth and nonsmooth problems. We introduce novel techniques to decouple the dependency of models and the previous instance in both the optimization and generalization analysis. Our study resolves an open question on developing meaningful generalization bounds for OGD using a buffer- ing set with a very small fixed size. We also extend our algorithms and stability analysis to develop differentially private SGD algorithms for pairwise learning which significantly improves the existing results.
Introduction
Many important learning tasks involve pairwise loss functions which are often referred to as pair- wise learning. Such notable learning tasks include AUC maximization [5
2
28
37
46
48),
metric learning 4 24 39
41 44], and a minimum error entropy principle 19] For in-
stance, AUC maximization aims rank positive instances above negative ones which involves with σ, E X S Rd and y.y/ E y = {=1}. The aim of metric learning is to learn a distance function hw (2)
a loss f(w: (I. y), (a', v/)) = (1 w (x x')) Igy=
(ar - "((r -x)) where w positive semi-definite matrix in Rdxd A typical pairwise loss where T(y,y") = =1 if = y and -1
can be f(w; (x, (x', = (1 otherwise. Given a training data S = {2, (I U.) E X' x Vii [m]] where [m] (1. n). the ERM formulation for pairwise learning is defined as minwew n(n-I Lije(m),yy] f(w; 2, 2i) where W denotes the parameter space. This scheme has been well studied theoretically using al- gorithmic stability I and U-statistics tools [0] At the same time, there are considerable interests on developing and studying online gradient descent (OGD) stochastic gradient descent (SGD) algorithms for pairwise learning due to their scalability in practice.
"quual contributions. The corresponding author is Yiming Ying.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

The critical issue for designing such stochastic algorithms is to construct interseeting pairs of in- stances for updating the model parameter upon receiving individual instances. For the offline (finite- is available, one natural approach to, at each time I, randomly select a pair of instances ( z3.) from ni(n - 1)/2 pairs and update w based on the gradient of the local error fw,,-15 =i. 2gg The excess generalization and stability was nicely established in [27]. One popular approach [22] BSJ 45 48 is to consider the online set- ting where the data is continuously arriving. This approach pairs the current datum 2n (Iz, Vs), which is received at time i, with all previous instances S = {z1....................... 3 and then performs the update based the gradient of the local error ((Wi-1;S(-1)
sum) setting where the prescribed training data S = (..,.... En)
Σ >Es,,, f(W-1:: 2,, 2). re- quires a high gradient complexity (t)) (i.e. the number of computing gradients) which is expensive when t becomes large. To mitigate this potential limitation, [22 37 48 proposed to use a buffering set - S S of size s and the local error f(w,-1; B
E f( 2) which
reduces the gradient complexity to Oss). The excess generalization bound O + (t) was (2 using the online-to-batch conversion method H which only meaningful for very large In particular, this bound tends to zero only when s = s(n) tends to infinity as n tends to infinity. was mentioned in [22] (see the discussion at the end of Section 7 there) as an open question on how to get a meaningful bound for a fixed constant s.
tablished in
In this paper, we show that optimal generalization bounds can be achieved for simple SGD and OGD algorithms for pairwise learning where, at time t, the current instance 2, is only paired with the previous instance 2.-1. This is equivalent to the In-st--n-First-ee Out (FIFO) buffering strategy [22] 37 while keeping the size 8 of the buffering set B,- to be s = 1. where, in this FIFO policy, the data 2n arriving time i > 1 is included into the buffer by removing (12) from the buffer. In particular, our main contributions are summarized as follows.
We propose simple SGD and OGD algorithms for pairwise learning where the f-th update of the model parameter is based on the interacting of the current instance and the previous one which has a constant gradient complexity (1))
We establish the stability results of the proposed SGD algorithms for pairwise learning and apply them to derive optimal excess generalization bounds O(1/V)) for the proposed simple SGD algorithm for pairwise learning with both convex and nonconvex well as both smooth and nonsmooth losses in the offline (finite-sum) setting where the training data of size n is given. We introduce novel techniques to decouple the dependency of the current SGD iterate with the previous instance in both the generalization and optimization error analysis, which resolves the open question in 2 how to develop meaningful generalization bounds when the buffering set of FIFO has a very small size.
We further develop a localization version of our SGD algorithms under (c, -diffferential privacy (DP) constraints, and apply the obtained stability results to derive an optimal utility (excess generalization) bound Ó(1/Vá + /d/nc). In contrast to the existing work [2] which requires the loss function to be smooth and an at least quadratic gradient complexity, our proposed DP algorithms only need linear gradient complexity ((n) for smooth convex losses to achieve the optimal utility bound and can also be applied to non-smooth convex losses.
The paper is organized as follows. Section 2 reviews the related work and Section 3 describes the proposed algorithms. In Section gl we present excess generalization bounds, stability results, and optimization errors of our algorithms. Section 5 is devoted to the differentially private SGD for pairwise learning and its utility bounds. Section provides experimental validation of theoretical findings. The paper is concluded in Scction 7
All the main proofs are postponed to the Appendix.
2 Motivating Examples and Related Work
In this section, we list examples of pairwise learning and discuss some related work.
2.1 Motivating Examples
AUC maximization. Area under the ROC curve (AUC) of prediction function hw is the prob- ability that the function ranks a random positive example higher than random negative example. The empirical risk of AUC maximization is given by Fs(w) min-iy Ei.se(h,,ss e(h (x,)

---

hw (xx) 10, = 11 (1:---1)1 I], where the loss E(.) can be the least square loss 2(t) = (1 t)² or the hinge loss {(t) = (1
Minimum error entropy principle. Minimum error entropy (MEE) is principle of information theoretical learning [T9 201. which aims to find a predictor h X' + y by minimizing the infor- mation entropy of the variable E Y h(X). The Rényi's entropy of order 2 for E is defined as (E) = - log (e)e. Here PE is probability density function and can be approximated by Parzen windowing Pa(e) my
1 Ei=1 G( 2/
(e=e))) where & = y/ - h(xz), and 7 > 0 is an
MEE scaling parameter and G IR + Rt is windowing function. The approximation of Rényi's entropy is given by its empirical version = - log n² Ei.jemn G( ( The maximization
of H then leads to a pairwise learning problem since each loss function involves a pair of training examples TT]
Metric learning. Metric learning aims to fine a distance metric ho X' x X' ト> RR consistent with some supervised information, e.g., examples within the same class are close while examples from
different classes are apart from each other under the learnt metric. If y = { {=1}. 3. the performance of
h on example pair z, z' can be quantified by loss function of the form f(w; x') E(yy' (1
hwi x, x²) x²)), where IR + R, is decreasing function for which some typical choices include the
hinge loss É(L) = (1 1)+ and the exponential function E(() loog1 + exp( (xp( Then one can minimize the training error Fs(w) = n(n-1j Ei.jE(n):t f(w; 24, 2ÿ) to learn a distance metric.
Another closely related learning task to metric learning is constrastive learning [10 30 351 40
which has become very popular recently for learning visual representations without supervision.
2.2 Related Work
The work 22
38 48 assumed the online learning setting in which a stream of i.i.d. data
{21, 22, 2t.....,....... .t.. is continuously arriving. Upon receiving 2, at time is paired with all pre- vious instances and then the model parameter is updated based on the local error F; (1,
provided the first excess generalization bound for online learning methods by obtaining online-to-batel conversion bounds [ using cover- ing numbers of function classes. Kar et al. [22] significantly improved the results using the so-called symmetrization of expectations which reduce excess risk estimates to Rademacher complexities. To further reduce the expensive gradient complexity (tt) at a large time f, the work [22 38 48) pro- posed to use buffering set B.-1 with size s instead of all previous instances. It was shown that such OGD algorithms have an excess generalization bound O O + vn) for convex and Lipschitz-
- - J(W;,1;;,, 2j). In particular, the work 37 3
continuous losses. In the offline learning setting where the training data S {2), 22. .2....... 2n) of
size n is fixed, the work [3 considered the stochastic version of the algorithm in 122 3yl where, at time f, random instance zi, with random index i, {l,..., n) is paired with all previous instances (Z),...,, J. They derived stability and generalization results of such algorithms in expectation.
Lei et al. 17 considered the offline learning setting and, at time t, the algorithm there randomly picks a pair of instances (Zi, from all (?) pairs of instances. An excess risk bound ((1 Vn) with high probability was derived for convex, Lipschitz and strongly smooth losses. Here the no- tation (-) means (-) up to some logarithmic terms. In the particular case of AUC maximization with the least square loss, 4 considered the online learning setting and reformulated the problem as a stochastic saddle point (min-max) problem which decouples the pairwise structure. From this reformulation, efficient SGID-type algorithms
29 4z
have been developed.
Recently, differentially private pairwise learning has been studied where the construction of pairs of instances follows 22
or all pairs are used at each iteration. In particular, Huai et al. 21 considered both online and offline learning settings and the pairs of instances at time follow They provided a utility bound O(vd/(Vrit) for convex and smooth loss functions. also paired the current instance with all previous ones and showed that SGD with output perturbation for pairwise learning has a utility bound Ō Ö(Vd/(vTie) for nonsmooth convex losses. The work [42 showed that private gradient descent using all possible pairs can achieve a utility bound ((1 vd/(ne)) for strongly smooth and convex losses.
57 4%
22
37
48
The study 4
3

---

3 Proposed Algorithms for Pairwise Learning
In this section, we describe the proposed algorithms in two common learning settings for pairwise learning: offline and online learning settings. Let be probability measure defined on Z := X' x 3 where X' is an input space and y' an output space. In pairwise learning, the performance of w is measured on pair of instances (z, 2') by nonnegative loss function f(w; 2, z"). Denote by [n] = (1.2....,7) n for any n E N.
Algorithm SGD for Pairwise Learning
Algorithm 2 OGD for Pairwise Learning
1: Inputs: S= [z:: E [r]] and step sizes (n:}
1: Inputs: learning rates {Te}
2: Initialize: Wo E W. let w-1 Wo and ran-
2: Initialize: Wo E W, let w-1 = wo and re-
domly select ig [n]
ceiving datum 20.
3: for tort= = 1, 2, .., do
3: for f 1, .., . do 4: Receive data point 2t
4: Randomly select 8, [n]]
5: w. wllllw (W.-1 1/2 V (Wr-1; Figs Ri )
5: W; = II (w--1 Ti V (w:- 21, 2-1))
6: Outputs: WT = Σソ= ny 2-2 Σド=
6: Outputs: Wr Σ ny ny Σラ=1 f]j
Offline Learning (Finite-Sum) Setting. The first is the finite-sum setting where the training data S = {== (si, Mk) Z : E [n]] are drawn independently according to p. In this context, one
aims to solve the following empirical risk minimization (ERM):
W argmin w NEW
Σ Fs(w) = n(n A.E
f(w:21,2))
(I)
Our proposed algorithm solve ① is described in Algorithm I The notation (ly(-) there denotes the projection operator to W. In particular, at iteration f. it randomly selects one instance 2;, from the uniform distribution over [n] and pairs it only with the previous instance 2 and then do the gradient descent based on ff(w.-1; Rbe, 1) This is in contrast to the classical SGD for
pairwise learning in [22] 37 4 where the present instance 2,, is paired with all previous instances
{Zi, Big...... Zi._, }. Note W depends on 2;,,; and then [f(w;-1; Pis: =i,-1) is not an unbiased
estimate of (W: Therefore, the standard analysis of SGD does not apply. We introduce
novel techniques to handle this dependency in our analysis (see more details in Section ET
Online Learning Setting. In the online learning setting where the data {=o, 21, 22, is assumed i..dd from an unknown distribution on Z, the number of iterations of an online algorithm is identical to the size of available data. In the same spirit to Algorithm D the pseudo code is given in Algorithm 2 Specifically, upon receiving a datum 2₁ at the current time f. we pair it with 2-1 which was revealed at the previous time 1 and then perform gradient descent based on the gradient V V.(w,- Z4, 1). It aims to minimize the population risk which is defined as F(w) E2,z. [f (w; Z, Z. Here Ez,z' denotes the expectation with respect to (w.r.t.) Z, Z' ~ p.
in general does not require the i.i.d. as- sumption on the data and study the regret bounds. In this paper, we mainly consider the statistical performance, measured by excess generalization bounds, of the output Wr of Algorithm 2 where the streaming data (=0, #1, - } is i.i.d. from the population distribution p.
worth pointing out that online learning 18 31 52
Remark 1. As discussed above, OGD for pairwise learning was proposed and studied in 22 37 where the current instance 2, paired with a buffering set B, S. {#1...., 21-1). However, the resultant excess generalization bound is in the form of O
v which indicated that the buffer
size needs to be large enough in order to achieve good generalization. Their analysis does not apply to our case since the buffering set B, = [ with size s = for Algorithm P As we show soon in Section 4 we can prove that Algorithm which pairs the current instance žt with the previous instance 1 still enjoys optimal statistical performance (1/vn).
The work [27] studied the stability and generalization of an SGD-type algorithm for pairwise learning by randomly generating pairs of instances. Specifically, at time t. randomly gen- (z.
Remark 2.
[n|] and the subsequent update is given by W. w M/ V (w, 2i 2j.). ). In contrast, our algorithm, i.e. Algorithm μ updates the model parameter based on the pair of the current random instance and the random
erating a pair (zi, 2j,) from given set of training data
one generated at the previous time 1, i.c. (Zi,, 24,1). Furthermore, work here significantly

---

differs from [27] in the following aspects. Firstly, the algorithm there by randomly selecting pairs of instances does not work in the online learning setting while ours can seamlessly deal with the streaming data stated in Algorithm 2 Secondly, regarding the technical analysis, our algorithms are more challenging to analyze than the algorithm in [27]- Indeed, V V/(w,-1; Zá, F5,) not an un- biased estimate of V (w,11) 1) due to the independency between W,-1 and (e). Therefore, the optimization error analysis of the algorithm 27 is the same as the SGD for pointwise learning. As comparison, V f(w,,1i 24, _i,_1) is biased estimate of V (w; due to the coupling between W and 1. We introduce novel techniques to handle this coupling for both the optimization and generalization analyses. Thirdly, we will soon below that we provide generalization results for nonsmooth, nonconvex losses and also use Algorithm to develop novel differentially private pair- wise learning algorithmss while 27 focused on the smooth convex losses in the non non- non-private setting.
Remark 3. If let & (ir, f--1) in Algorithm then ( N) forms Markov Chain &
only depends on ε-- but not on Chain SGD which was studied in [36] Despite this similarity, our results differ from 36 in two important aspects. Firstly, we are mainly interested in stability and generalization of Algorithm ! while 36) focused on the convergence analysis of the Markov Chain SGD, One cannot apply the results in [36] to obtain excess generalization bounds for Algorithm | in terms of the population risk we will show soon in the next section. Secondly, directly applying Theorem in [36] only yields a convergence rate of O(1/t' with some 1/2 < q < in the convex setting, Our proof for the convergence analysis of Algorithm D is much simpler and direct which can yield faster convergence rate (11/Vl) as shown in Section 4.3
Hence, Algorithm [ can be regarded as a Markov
4 Generalization Analysis
The aim for the generalization analysis of Algorithm and Algorithm is the same, i.e. to analyze the excess generalization error F(w) F(w") of a model w measuring its relative behavior w.r.t. the best model w arg minwew F(w).
For Algorithm D where the training data S with n datum is given beforehand, the excess general- ization involves the generalization error and optimization error. Specifically, one has the following error decomposition for WT
E [(()) F(w")= E ((F(W) Fs(WT)) + [Fs(ww)) -Fs(w")
(2)
Here, the expectation is taken w.r.t. the randomness of Algorithm i.e., {it} and the randomness of data S which is i.i.d. from on Z. We refer to the first term E. F (wr) - [wr]] as the general- ization eтror and E B(Fs(Wr) - Fs( as the optimization error. We will use algorithmic stability to handle its generalization error in Subsection 4.2 for smooth and nonsmooth losses. The estima- tion of the optimization error is given in Subsection 4.3 for both convex and nonconvex losses. For Algorithm 2 there no generalization error as the data {z1, (2,,22...... 2T} is arriving in a sequential manner with T increasing all the time which does not involve the training data. The randomness of Algorithm 2 is only from the i.i.d. data. Therefore, the optimization error in this setting is exactly the excess generalization error F F(WT)= F(w") which is estimated in Subsection 4.3
4.1 Excess Generalization Error
In this subsection, present excess generalization error bounds of Algorithm 1 in terms of the sample size, iteration number and step size, which shows how to tune these parameters to get a model with good generalization. Our analysis requires the following assumptions.
Assumption. Let W Z x Z + IR+ and let || ||2 denote the Euclidean norm.
(A1) Assume, for any z' and w E W, that f(;2,2) is G-Lipschitz continuous, i.c. ((w'22,z') < G|[w - w/ ||2-
(A2) Assume, for any 2. E E, the map w F f(w 2, 2') is L-strongly smooth, i.e. f(w; 2, 2,2²) f(w';
[f((w'2,,'' w w') < |ww w'1
- (A3) Assume, for any 2, E 2, f( z') is a-strongly convex, i.e. -(w',, z') (Vf(w'zz, w w') > w w/ | The case of a is identical to convexity.
5

---

(A4) Assume Fs satisfies the
(PL) condition with parameter μ>> 0, i.e., for W E arg wew Fs(W). there holds (Fs(w) - (w = V for all w E W.
The PL condition (A4) means that the suboptimality in terms of function values can be bounded by gradients [23]. Functions under the PI. condition have found various applications including neural networks, matrix factorization, generalized linear models and robust regression (see, e-g-- (23). In particular, AUC maximization problem with the classifier given by a one hidden layer network satisfies the PL condition as shown in 29
We first study smooth and non-smooth problems for the convex case, and derive the excess gener- alization bounds of the order (11/v in both cases. We use the notation B x B if there exist constants Ci C2 > such that e, - I Bz The proof' are given in Section
Theorem (Nonsmooth Problems). Let w-1 = Wo and {we :t E [T]] be produced by Algorithm
with nu 17 > O. Let WT = -i= //W222/ Ei=1 nue Let (Al) and (A3) hold true with a O. Then, we have
[ - -0
O -
Ty
1 1+ + T1j
(3)
n
Furthermore, selecting T x n² and 1) x 2 yields that Es Al
F(w')) = OL///n)
Theorem 2 (Smooth Problems). Let (AI), (A2) and (A3) hold true with 0. Let W-1 Wo and
{w, t E [T]} be produced by Algorithm with 17. = 17 S 2/ L. Let Let Et= T/WW-2/ Σi= nh.
Then, there holds
Es.A(F(wr)) - F(w*) = ( T' +
1 1 TT?
(4)
TT
Furthermore, choosing T x and rj x T implies that Es (. (WWT) =(w")=((\/v)))
Remark 4. Notice that the gradient complexity (i.e. the number of computing gradients) of Algo- rithm[]is is identical to the number of iterations 7'. The above results show, to get excess generalization bounds (1// vn), that Algorithm requires a gradient complexity O(n²) for nonsmooth problems, and (n) for smooth problems. This matches the existing generalization analysis for pointwise learning 3 17 [2). In Appendix El additional results are provided where we propose Algorithm g based on the iterative localization technique |B] in order to reduce the gradient complexity O(n") required in Theorem [ to (nr) for nonsmooth problems.
Remark 5. As stated in the introduction, Algorithm I can be considered as specific case of the classic pairwise learning algorithm [22] with a FIFO buffering set B of size s 1. key difficulty in the generalization analysis is that w;-1 depends on B which renders the stan- dard martingale analysis not applicable. Kar et al. 22 proposed to remove this coupling effect by considering supw [f( B(-1)= - Fs(w)), which is why they only derived the excess gener- alization error bound O(1/ V We introduce novel techniques to handle the coupling in both generalization analysis and optimization error analysis. For the generalization analysis, our strat- egy is to write the stability as deterministic function of several indicator functions whether we select the different point in neighboring datasets, and then finally consider the randomness of these indicator functions. This delay of considering expectation successfully decouples the cou- pling between w,-1 and B,-1. For the optimization error analysis, our novelty is to observe that f(w--1; 2i, ) = f(w,-2; 2i, zi,-;) ) + (n+-1), which removes the decoupling since w is now independent of both & and 4-11. Since the additional term O (nt-1) )) here is a term of smaller magnitude, the coupling effect is removed without incurring any additional cost.
Finally, we study nonconvex pairwise learning under the PL condition. The proof is in Section
Theorem 3. Let (A/), (A2) and (A4) hold true. Let au, B > O. Let w-1 and (w, : E t}}
be produced by Algorithm 7 with nj = 2/ (uli + 1)). If E [IV ( 24,=a) [13] < a
and sup,,e' f(W,32, x²) & B for any j. then
[[F(WT)] FF(-=F((--)))) = 0( T TzL
+ OOI((TT)))
n
Furthermore, choosing T x n 3644 μ
yields that E [[F(WT)] F F(w") = n aL*r 4 -t-F.
26th

---

Remark 6. As pointed out before, there is no generalization enror for the OGD algorithm, i.c. streaming manner and the iteration number equals the
Algorithm 2 as the i.id. data is given number of the available data (i.e. I. = n). In this setting, the optimization error is identical to the excess generalization error, which will be estimated in Subsection
4.2 Stability and Generalization Errors
We study generalization errors by algorithmic stability, which measures the sensitivity of the output of an algorithm w.r.t. the perturbation of the dataset. Below we give the definition of uniform argument stability. We say S, 5" are neighboring datasets if they differ at most by a single example. Definition A (randomized) algorithm for pairwise learning is called e-uniformly argument stable if for all neighboring datasets S, S' E Z" we have ((()) A(S') [2] S.
is clear e-unfform argument stability implies Ge-uniform stability i.e., sups, BA(f(A(S), z, z')- J(A(S") 2, x Ge for Lipschitz losses 77 The connection between the uniform stability for pairwise learning and its generalization has been established in the literature [1 34).
Lemma 1. If algorithm A for pairwise learning is s-uniformly stable for some have (Bs.(Fs(A((S) - F ([A(S))] < 2E.
O, then we
We develop uniform argument stability bound of Algorithm T and apply it together with Lemma T to establish the following generalization bounds. Theorem handles nonsmooth problems, while Theorem handles smooth problems. The detailed proofs for them can be found in Section A
Theorem 4. Let w-1 wo and (wj : E ]1} be produced by Algorithm ! with ny - 7, Let (AI)
and (A3) hold with = 0. Then, Algorithm is / (v5l
2t
-uniformly argument stable and m
21
(F Fs(())) W (V56+
Ti
Theorem 5. Let W-1 Wo and {wy : E {t]} be produced by Algorithm with nj = S 2/L. Let (AI), (A2) and (A3) hold true with O. Then, Algorithm
4G
Mi umiformly argument Σ
stable and the generalization error satisfies TE (Fs.((((w))) Fs w.
For Algorithm 2 there is no generalization error the data (=1, { 22,-..y 2r) is assumed to arrive in a sequential manner with T increasing all the time which does not involve the training data.
4.3 Optimization Error
In this subsection, we establish the convergence rate, i.c., optimization eтror, of Algorithm for convex, nonconvex and strongly convex problems. We consider both bounds in expectation and with high probability. Our analysis is based on the key observation f[W;-1; =i, 25 f(w.-2; By, ) + (1)-)). The proofs of results in this subsection are given Section B
Below we only present optimization error bounds for Algorithm [ here in the offline (finite-sum) fixed, and the optimization error is measured by F's (w -inf wew Fsw We emphasize that all our optimization error bounds hold true for Algorithm streaming data {21..... ".....} } is assumed to be i.i.d according to the population distribution p, and the bounds for the optimization error in this case is given for the excess generalization error (excess population risk), i.e. F(W,)) - infwew F(w).
setting where the training data of size n, denoted by S [2),..... Zn
the online learning setting with exactly the same analysis where the
Theorem 6. Let w -1 = wo and (w; j E [t]] be produced by Algorithm I hold true with 2 0. Then, for any independent of A we have the following convergence rates:
Let (AI) and (A3)
(a) Assume f is convex, i.e. a Then, we have
Ea(Fs(W:)] - Fs(W) |Wo
w/
+
G2 E/=1 (2n,m111 +1))
(5)
2 2
(b) Let f be a-strongly convex with > and njj
-
ab5t) Then, there holds EE [F(Fs(W:.)
Fs(w) (O00 (at)).
7

---

Remark 7. The above convergence rates match those in the pointwise learning [5]. Furthermore, 7h 7, then Eq. 1 becomes Fx(Fs(W,)) Fs( ((1/(tn) + 1)) and one can choose 7 x 1/V0 to get (wi))s(w.)) - (s((W) = (11/vt). We can extend our convergence analysis to a more general update as We = -wwwwwww (WL1 n: Ej=1 Vf(W(-1 S..+ 20,,)) )) for E N. Indeed, one can use the observation f(w,-1i Riss Ric_.)= = f(wi-s-i Rig Ri._. + O Ej=1 Tt-z) to derive the convergence rate OVV3/V)).
Below we present high-probabiline bounds understand the variation of the algorithm. We need to take conditional expectation of f(W2j-2i: Bigs Rizz-1) w.r.t. (12g. f2z-1) to get Fs(W2j-2) However, there a coupling between (72z. 125-1) and (i2)-1; (2)-2). Therefore, one can not di- rectly apply concentration incqualities for martingales to handle Σ/=1 (f(w2)-2; Riz (
(w 2)). We introduce a novel decoupling technique handle this coupling. Note that the high-prut bogb-probability bounds match the bounds in expectation up to a constant factor.
Theorem 7. Let w-1 = wo and (w; : E [1]] be produced by Algorithm 7 hold true with a and supw f(w; 2, 2) I B for some B > O. Let d E (0, IT.
Let (AT) and (A3)
(a) Assume f is convex, iee. a = and let w. = Σj= 73 w Eÿ= 75- Then, for any w E W, with probability at least 1 the following inequality holds
(2B Fs(W:) (Fs(W) S Σj= MJ
2 ==1
# + - log(2/)))
Σ
(1) (1)-199;+ 2 ))
5=1
(b) Assume f is cr-strongly convex with or >> O and nij ab+t Let w. / Ej= Then, with probability at least 1 8, we have Fs(w.,) - Fs(w) O log(11)1////00 (1))(1/1)/())))))) (al))
Finally, we study the convergence of Algorithm D associated with nonconvex functions. We first consider general smooth problems. Since cannot find global minimum in this setting, measure the convergence rate in terms of gradient norms [16]. The following theorem establishes the convergence rate O(I/VF) for minj=1....., FA 11)
Theorem 8. Let = We and [w,:3 :j E [d] be produced by Algorithm 2 with =
Let (A2) hold true and 1 V (wyi 41 2,,22) ) 11 S for some on and any j. Then,
Fs(wo) 8LMag 2
EA (Fs((
in
Furthermore, choosing 7 x 1/v2 implies that [IVF O(1/v).
E
We now turn to nonconvex problems under PL condition. Theorem D gives convergence rates of the order (1/tt,, which match the existing results for standard SGD in pointwise learning 23
Theorem 9. Assume (A2) and (A4) hold true and E, 12 [[] f 2lyes ) S ag for some Og and any j. Let w = wo and {w; j E [t] be produced by Algorithm with f = 2/(u]++1) Then
32La
1
+ log(et)
BA(Fs(w.)) Ps(ws)) S
1+1
pl(( ([(1+1)
5 Application: Differentially Private SGD for Pairwise Learning
We now use Algorithm D and our stability analysis (i.e. Theorem 5 to develop a differentially
private algorithm for pairwise learning. Let us start with the definition of differential privacy [12]
Definition 2. A (randomized) algorithm A is called (e, J)-differenniallly private (DP) if, for all neigh- boring datasets S, S' and for all events O in the output space of A, one has P(A(S) E O s e'P[A(S') e 0] 5.
8

---

Algorithm 3 Differentially Private Localized SGD for Pairwise Learning
1: Inputs: Dataset 5 (2, ; E [r]]], parameters e, > 0, and learning rate 7/ initial point wo
2: Set K = [log, n and divide S into K disjoint subsets
where |Sk = =, 2 "n.
3: for k
K do
4: Set 1/k 4-
5: Compute wi by Algorithm based on S₃ and initiated at W for [nn (4/5)] steps.
6: Set Wg Wx + 4r where Ug (00 of la) with og 12Gr, log(4/6) 220g2)/////
7:
Outputs: WK
Our proposed DP algorithm for pairwise learning is described in Algorithm g which is inspired by the iterative localization technique [33 for pointwise learning. The privacy and utility guarantees are given by the following theorem. Here D denotes the diameter of W.
Theorem 10.
Let (AI), (A2), and (A3) hold true with o = O. Let {wx k [K]} be produced by
Algorithm with 17 0 min log(1/6)
12 12 (6) /2dlog(2.5/8/ S L. Then, Algorithm satisfies
vn
(e, ODD and, with gradient complexity O(n log (1/8)), we have the utility bound that
B[F(WK) F(w")((w=)))) - - + vdlog (1/0))
The main difference from the pointwise setting in 13 is that Algorithm 3 involves the coupling dependency between {ūe, 11 at time / in Algorithm I and (4 } at time (- which renders the direct application of the standard concentration inequalities infeasible. We propose a novel decomposition circumvent this hurdle (see more detailed proof for Theorem I0 in Appendix D
Remark 8. The above bound matches the lower bound given in 2 for (c, differrretilll private pointwise learning up to a log(1 (gg())) term. Our utility bound improves over the previous work [21] which has the bound O(y d (og((/o)) log(n/6)/ (vr)).. During the preparation of this work, we notice a very recent paper 4 also studied the private version of pairwise algorithm by using the localization technique. Their algorithm establishes the optimal rate (1/v/ + v /dlog(L/))/(en)) which, however, needs an expensive gradient complexity O( 1og(1/8)). As a comparison, we achieve nearly optimal utility bound with linear gradient complexity O log(1)6)
Remark 9. In Appendix we further remove the smoothness assumption (A2) required in The- orem 10 and propose private algorithm (stated as Algorithm 5 there) that achieves the optimal
rate ((1 // + (/lllo(()))((e))) with gradient complexity Onn log(1/5)). Such bound im- proves over the previous known results with nonsmooth losses 4 where the utility bound was O(y logg((/) (Vne)).
6 Experimental Validation
We now report some preliminary experiment on AUC maximization with f(w; (x, w), (x',x')) where is surrogate loss function, e.g., the hinge loss {(t) = (1-t)+-
[(w (x- (x=x))]
The purpose of our first experiment is compare algorithm, i.e. Algorithm I against four
existing algorithms for pairwise learning in terms of generalization and CPU running time on several datasets available from the LIBSVM website Н. These algorithms are: 1) OLP [2]] uses a buffer B₁ updated by variant of Reservoir sampling with replacement where the buffer size is chosen to be 200 in order to guarantee the maximum AUC score as indicated in p2] 2) OAM tailored for AUC maximization with the hinge loss which uses buffers by Reservoir sampling. The buffer size set to be 100 for both positive and negative buffers as suggested in that paper: 3) SGD pair [27] randomly pick a pair from (?) pairs by uniform distribution; 4) SPAUC (26). where AUC maximization problem with the least square loss was reformulated as stochastic saddle point (min-max) problem. Note that SPAUC and OAM can only apply to AUC maximization problem with the least square loss and hinge loss, respectively.
44] is
The source codes are available at https///ggtuu..cc//hhbuaaeeeeeee
pairwise

---

Table 1: Average AUC score + standard deviation across multiple datasets. Our best results highlighted in bold.
Algorithm
diabetes
german
ijcan1
letter
mnist
usps
Oura
.831 1 .030
.793
001
.934 4 .002
.810 + .007 .932 _ .001
.926 E .006
SGD prase
27
.830 = .028
.794 = .023
.934
.003
.811 _ .008
.932 - .001
.925 = .006
OLP
20
.825 + .02
.787
.028
.916 -003
.808 + .010
.927 + .003
.917 + .006
OAMgra
48
.828 + .026
.785
029
.930 + .003
.806 = .008
.988 - .002
.916 = .005
SPAUC
26
.828 + .031
.799 + .266
.932 +: .002
.809 + 0088
.977 + .002
.923 + .005
To validate the generalization ability, the surrogate loss for Algorithm I SGDpair and OLP is chosen to be the hinge loss. Average AUC scores of different algorithms are listed Table | where we see that algorithm yields competitive generalization performance with OAM and OLP using large buffering set. Detailed experimental setup, data statistics and more results such as comparison with OLP and OAM with the size of the buffering set
1 are listed in Appendix
sjemml
Letter
uspe
100
3.14
AUC
0.70
AUC
00
aet
1pt
37"
18-1
1071
CPU running kione (ing scaale)
CPU rumning time (og scade)
running cims (log scale)
Figure I: CPU running time (log scale) versus the AUC score
To fairly compare the CPU running time, we apply the following uniform setting across all algo- rithms: 1) W is an lg ball with the same diameter; 2) the step sizes = which is tuned by cross validation. We report the results in Figure for the hinge loss. We can see that CPU running time for our algorithm and SGD pair are similar while OLP and OAM needs more time to converge. The possible reason behind this is that they have high gradient complexity (s)) at each iteration while ours is (()). More results on comparison for the least square loss and for differentially private algorithms are given in Appendix
7 Conclusion
In this paper, we propose simple stochastic and online gradient descent algorithms for pairwise learning The key idea is to build gradient estimator by pairing the current instance with the pre- vious instance, which enjoys favorable computation and storage complexity. We leverage the lens of algorithmic stability to study its generalization and apply tools in optimization theory to study its convergence rates for various problems including convex/nonconvex and smooth/nonsmooth set- tings. We also use our algorithms and stability analysis develop a new DP algorithm for pairwise learning with differential privacy constraints which significantly improves the existing results. The main difference from pointwise learning in the analysis the coupling between models and previous instances, which is handled by introducing novel decoupling techniques.
For future work, it would be interesting to see whether the analysis and results still hold true if the current example z, in Algorithm | is paired with one arbitrary previous example (e.g., Z,, ). Other future work would be a systematic extension of our algorithms using other acceleration schemes such as momentum and variance reduction techniques.
Acknowledgmentss
The authors are grateful to the anonymous reviewers for their constructive comments and sug- gestions. Tianbao Yang is partially supported by NSF Career Award #1844403 and NSF Award #0115 Yiming Ying supported by NSF under grants DMS-21 10836, IIS- 1816227, IIS- 21 2110546 and 11--2003450.
10

---

References
[1] S. Agarwal and P. Niyogi. Generalization bounds for ranking algorithms via algorithmic sta- bility. Journal of Machine Learning Research, 10(Feb):441-41) 2009.
[2] R. Bassily, A. Smith, and A. Thakurta. Private empirical risk minimization: Efficient al- gorithms and tight error bounds. In 2014 IEEE 55th Annual Symposium on Foundations of Computer Science, pages 4644773. IEEE, 2014.
[3] R. Bassily, V. Feldman, C. Guzmán, and K. Talwar. Stability of stochastic gradient descent on nonsmooth convex losses. Advances Neural Information Processing Systems, 33, 2020.
[4] A. Bellet, A. Habrard, and M. Sebban. A survey on metric learning for feature vectors and 2013.
structured data. arXiv preprini
[5] L. Bottou, F. E. Curtis, and J. Nocedal. Optimization methods for large-scale machine learning. SIAM Review, 60(2):223-11, 2018.
[6] S. Boucheron, G. Lugosi, and P. Massart. Concentration Inequalities: Nonasymptotic Theory
of Independence. Oxford university press, 2013.
[7] O. Bousquet and A. Elissefff. Stability and generalization. Journal of machine learning re- search, 29M5r): 2002.
[8] N. Cesa-Bianchh,, A. Conconi, and C. Gentile. On the generalization ability of on-line learning algorithms. IEEE Transactions on Information Theory, 50(9):2050-2057) 2004.
[9] C.-C Chang and C.-J. Lin. LIBSVM: library for support vector machines. ACM Trans- actions Intelligent Systems and Technology. 2:27:1-27:27, 2011. Software available at http://www. csie. ntu edu. tx/" http//jllinnniieeee
[10] T. Chen, S. Kornblith, M. Norouzi, and G. Hinton. A simple framework for contrastive learning of visual representations. In International conference machine learning, pages 1597-1607. 2020.
[11] S. Clémençon, G. Lugosi, and N. Vayatis. Ranking and empirical minimization of U-statistics.
The Annals of Statistics, pages 844,874, 2008
[12] C. Dwork, A. Roth, al. The algorithmic foundations of differential privacy. Foundations and Trends@ in Theoretical Computer Science, (0-44):111-077, 2014.
[13] V. Feldman, T. Koren, and K. Talwar. Private stochastic convex optimization: optimal rates in linear time. Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, pages 439-449, 2020.
[14] D. Foster, A. Sekhari, and K. Sridharan. Uniform convergence of gradients for non-convex learning and optimization. In Advances in Neural Information Prucessing Systems, pages 8759-8776 2018.
[15] W. Gao, R. Jin, S. Zhu, and Z.-H. Zhou. One-pass auc optimization. In International Confer- ence on Machine Learning, pages 906-914, 2013.
[16] S. Ghadimi and G. Lan. Stochastic first-and zeroth-order methods for nonconvex stochastic programming. SIAM Journal on Optimization, 23(4):2341-2366 2013.
[17] M. Hardt, B. Recht, and Y. Singer. Train faster, generalize better: Stability of stochastic gradient descent. In International Conference on Machine Learning, pages 1234, 2016.
[18) F. Hazan. Introduction to online convex optimization. Foundations and Trends@ in Optimiza- tion, 2(3-4):157-325, 2016
[19] T. Hu, Fan, Q. Wu, and D.-X. Zhou. Learning theory approach to minimum error entropy criterion. Journal of Machine Learning Research, 14(2), 2013.
[20] T. Hu, J. Fan, Q. Wu, and D.-X. Zhou. Regularization schemes for minimum error entropy principle. Analysis and Applications, 13(0)))337-455 2015.
[21] M. Huai, D. Wang, C. Miao, J. Xu, and A. Zhang. Pairwise learning with differential privacy guarantees. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pages
694-701, 2020.
[22] P. Kar. B. Sriperumbudur, P. Jain, and H. Karnick. On the generalization ability of online learn- ing algorithms for pairwise loss functions. In International Conference on Machine Learning, pages 441-449 119,449922 2013.
[23] H. Karimi, J. Nutini, and M. Schmidt. Linear convergence of gradient and proximal-gradient methods under the polyak-tojasiewice condition. European Conference on Machine Learn ing, pages 795-811. 2016.
11

---

[24] B. Kulis et al. Metric learning: A survey, Foundations and Trends in Machine Learning, 5
(4):287-364, 2013.
[25] Y. Lei and Y. Ying. Fine-grained analysis of stability and generalization for stochastic gradient descent. In International Conference Machine Learning, pages 5809-5819, 2020.
[26] Y. Lei and Y. Ying. Stochastic proximal auc maximization. Journal of Machine Learning Research, 22(61):1-45, 2021.
[27] Y. Lei, A. Ledent, and M. Kloft. Sharper generalization bounds for pairwise learning. In Advances in Neural Information Processing Systems, volume 33, pages 21236-212444 2020. [28] M. Liu, X. Zhang, Z. Chen, X. Wang, and T. Yang. Fast stochastic auc maximization with (onvercnnee rate. In International Conference on Machine Learning, pages 3195-3203, 2018.
[29] M. Liu, Z. Yuan, Ying. and T. Yang. Stochastic auc maximization with deep neural networks. In International Conference on Learning Representations, 2020.
[30] A. v. d. Oord, Y. Li, and O. Vinyals. Representation learning with contrastive predictive coding. 2018.
arXiv preprint
[31] F. Orabona. A modern introduction to online learning. arXiv preprint arXiv:1912.132111 2019.
[32] S. Shalev-Shwartz. Online learning and online convex optimization. Foundations and Trendso)
in Machine Learning, 4(2):107-194, 2012.
[33] S. Shalev-Shwartz, O. Shamir, N. Srebro, and K. Sridharan. Stochastic convex optimization.
In COLT, 2009.
[34] W. Shen, Z. Yang. Y. Ying, and X. Yuan. Stability and optimization error of stochastic gradient descent for pairwise learning. Analysis and Applications, 18(05))887-9211 2020.
[35] K. Sohn. Improved deep metric learning with multi-class n-pair loss objective. In Advances in
neural information processing systems, pages 1857-1865, 2016.
[36] T. Sun, Y. Sun, and W. Yin. On markov chain gradient descent. Advances in neural information processing systems, 2018
[37] Y. Wang. R. Khardon, D. Pechyony, and R. Jones. Generalization bounds for online learning algorithms with pairwise loss functions. In Conference on Learming Theeoyy volume 23, pages
13-1, 2012.
[38] Y. Wang, R. Khardon, D. Pechyony, and Jones. Online learning with pairwise loss functions. arXiv preprint arXiv: 330153332, 2013.
[39] K. Q. Weinberger and L. K. Saul. Distance metric learning for large margin nearest neighbor classification. Journal of Machine Learning Research, 10:207-244, 2009.
[40] Z. Wu, Y. Xiong, S. X. Yu, and D. Lin. Unsupervised feature learning via non-parametric instance discrimination. In Proceedings the IEEE conference on computer vision and patlern recognition, pages 3733-3742, 2018
[41] E. P. Xing. M. I. Jordan, S. J. Russell, and A. Y. Ng. Distance metric learning with application to clustering with side-information. In Advances in Neural Information Processing Systems, 2003.
[42] Z. Xue, S. Yang, M. Huai, and D. Wang. Differentially private pairwise learning revisited, 2021. URL Stt.ll/tts::///ste
htttps://shacwwanggee
github. 10 htt.ai/.e/pppppe///ooooooooooarr
[43] Z. Yang, Y. Lei, S. Lyu, and Y. Ying. Stability and differential privacy of stochastic gradient descent for pairwise learning with non-smooth loss. In International Conference on Artificial Intelligence and Statistics, pages 2026 2034.033. PMLR, 2021.
[44] Y. Ying and P. Li. Distance metric learning with eigenvalue optimization. Journal of Machine Learning Research, 13:1-26, 2012.
[45] Y. Ying and D.-X. Zhou, Online regularized classification algorithms. IEEE Transactions on Information Theory, (2(11):47755-1
2006.
[46] Y. Ying. L. Wen, and S. Lyu. Stochastic online AUC maximization. In Advances in Neural Information Processing Systems, pages 451-459, 2016.
[47] T. Zhang. Data dependent concentration bounds for sequential prediction algorithms. In Con- ference on Learning Theory, pages 173-187, 2005.
[48] Zhao, S. C. Hoi, R. Jin, and T. Yang. Online AUC maximization. In International Conference on Machine Learning, pages 233 240, 2011.
12


Reviews:
[{"review_id": "vYmw8hH3r6T", "reviewer": "Reviewer_7nrA", "summary": "The paper proposed \"stochastic gradient descent\" (SGD) and \"online gradient descent\" (OGD) algorithms for pairwise learning problems. Stability results, optimization, and generalization error bounds for both convex and nonconvex as well as both smooth and nonsmooth problems are provided. The authors also develop differentially private SGD algorithms for pairwise learning. Empirical results are provided in a variety of real-world datasets.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "Originality: The novelty of the proposed pairwise model seems limited. This work is an extension of [20] by setting the buffer size of 1. The theoretical analysis is solid.\n\nQuality: This paper provides worthy, but not surprising contributions to minor problems. The theoretical analysis is technically sound. However, I have several concerns. 1) It is unclear that why the proposed method performs better than [25] both in intuition and theory. 2) Experimental results are weak and improvements are not significant, especially for [25] and [24]. 3) Besides the running time, what about the AUC score w.r.t number of training examples? \n\nClarity: The paper is clearly written and provides enough information for an expert reader to reproduce its results.\n\nSignificance: The paper will have a low overall impact in practice. It is unclear whether it is a better way than previous work.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "No. \n\nSee Main Review.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8"}, "extra_text": {}}, {"review_id": "v6Z3Dj2RDw", "reviewer": "Reviewer_nSDq", "summary": "The authors consider the pairwise learning problem in which the loss functions depends on two datapoints and not only one as in standard supervised learning. In order to address this problem, state-of-the-art methods use stochastic and online gradient descent algorithm, pairing the current datapoint with a buffering set of previous datapoints with an appropriate size. In this work, the authors propose as alternative to pair the current instance with only the previous one when building a gradient direction for the update step. This is obviously advantageous both for the storage and the computational complexity. The authors also present new stability results, optimization, and generalization error bounds for their method for convex/non-convex and smooth/non-smooth problems. The results they find is competitive to the rates for standard supervised learning. Finally, they also extend their pairwise algorithms and the corresponding theoretical analysis to a differentially private context improving state-of-the-art results.", "questions": "", "limitations": "", "rating": 7, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "The paper presents an interesting problem and it is well written and easy to follow. The results seem to be reasonable. \n\nThe main contribution of the paper is for sure the adaptation of stochastic and online learning algorithm to pairwise learning by keeping the same computational cost and convergence rate as in the (singleton) standard supervised learning setting. This is technically done by using as descent direction the subgradient of the loss function evaluated at the current point and the previous one. From the theoretical point of view, in order to provide guarantees for such a method, the authors use standard tools from stability theory, but they also need to introduce a novel technique allowing them to decouple the dependency of models and the previous instance in both the optimization and generalization analysis. It would be nice and important to describe in the main body the high-level idea used during this step.\n\nThe authors say that pairwise learning instantiates many important machine learning tasks such as bipartite ranking and metric learning. I would like to see a more extensive justification about the possible applications of pairwise learning, explaining to the reader why pairwise learning could be interesting for the machine learning community.\n\nThe experiments seem to be exhaustive. The authors test the performance of their algorithms on a AUC maximization problem by comparing the proposed algorithm to four existing algorithms for pairwise learning in terms of generalization and CPU running time on several datasets from the LIBSVM website.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "yes", "review_text": "", "extra_scores": {"ethical_concerns": "no ethical issue in my opinion", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "48"}, "extra_text": {}}, {"review_id": "ZskeHctcJZ_", "reviewer": "Reviewer_7Peg", "summary": "This paper introduces a simple algorithm for online and offline pairwise learning, pairing the current sample only with the previous one. This is a more challenging setting than previously studied, as the gradient estimator is biased (the current weights and previous sample are coupled). Using novel techniques, this work derives an optimal excess generalization bound for this algorithm. Furthermore, the authors introduce a differentially private version of their algorithm, and derive the corresponding utility bound. \nThe theoretical results are validated by experiments on AUC maximization on a number of classic datasets, showing excellent results both in average AUC score and CPU running time when compared to the state-of-the-art.", "questions": "", "limitations": "", "rating": 8, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "*For ease of answering, I have annotated my various points with O.1/Q.1/etc...*\n\nMy review will be quite short, as this is a very good paper. The idea proposed is conceptually very simple, but requires significant theoretical work to derive useful bounds. The paper is well written, and the authors do a great job at outlining their mathematical demonstrations. The experimental validation is thorough, with extensive further experiments in the supplementary. \n\nAccordingly, this is a **clear accept (8)**. I only have two small points below on the style & clarity of the tables, and on the lack of a discussion around limitations & future work (especially in regard of Figure G.2 of the supplementary). \n\n### Originality\nThis paper is well placed in the relevant literature, and the authors do a good job in section 2 at outlining how their work improves on the state-of-the-art. Although the algorithm proposed may look simple, all the complexity lies in providing useful bounds. Previous literature with buffering set of arbitrary size had only succeeded in providing bounds that are meaningful for very large batches.  \n\n### Quality\nThe theoretical part of this work is very solid, with a well-structured and excellent analysis. The experimental validation is equally good, comparing to a large number of methods on diverse datasets. \n\nHowever, on light of Figure G.2 of the supplementary, I do have a (small) point of criticism.\n**Q.1**: This work is very complete and leaves no question \"hanging\", but the authors could still make an effort to discuss potential limitations. It would be interesting to at least mention that methods such as SPAUC, designed for very specific losses and problems, can still be competitive (as seen in Figure G.2, and as sparsely discussed on l775 of the supplementary). \n\n### Clarity\nThis paper is well written, and the theoretical analysis is easy to follow from the outline provided. \n\nOne small point I have to make is regarding the design used for the tables presenting results (Table 1, and in Section G of the supplementary). \n**C.1**: The tables do not follow the style guidelines provided in the NeurIPS template. They use vertical rules, and too many horizontal rules. Given their density, this makes them hard to parse. Moreover, in each column, highlighting the best result in bold would make them more readable at a glance. \n\n### Significance\nThis work clearly builds upon the state-of-the-art, and provides new useful bounds that are a clear improvement over previous work. This is a very interesting result, that answers a question previously left open. The techniques used by the authors to achieve this result may also be of interest to others in the field. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "There is currently only a limited discussion of some limitations in the supplementary. This is one point I feel the authors could improve, as explained above in Q.1. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "0NVdGrrEmbf", "reviewer": "Reviewer_PEqh", "summary": "This paper proposes simple offline and online algorithms of pairwise learning which share the same idea of updating parameters based on only the current and the last seen data points. Then follow a series of generalization analysis on these algorithms under various loss function conditions. Finally simple but crucial experimental results show the feasibility of the proposed methods.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "Originality: In pairwise learning, this paper proposes to update parameters using the current data point and only the last seen data point, in both offline and online setting. Although this causes the problem of the gradient update no longer an unbiased estimate of the true gradient, authors propose two interesting methods to alleviate this: composing indicator functions and using the difference of $\\mathcal{O}(\\eta_{t-1})$ between the evaluations before and after the parameter update.\n\nQuality: Claims are theoretically sound and are well supported theoretically and empirically.\n\nClarity: This paper is very well written and easy to follow.\n\nSignificance: The proposed method reduce the gradient complexity to a surprising $\\mathcal{O}(1)$ which significantly improves its practicability in real world.\n ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Not applied.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}]

Author rebuttal:

Meta-review: All the reviewers agree upon the quality of the paper and support its acceptance. There is no argument to go against this consensus and I recommend the acceptance of this paper.

We count on the authors to take into account the small fixes recommended by the reviewers.


Decision: Accept (Poster)