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(n,,ss e(h (x,)

---

hw (xx) 10, = 11 (1:---111 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 A- = - 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}. 1. 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-batcl 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 f2), 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 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( 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/ 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
21
-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 1 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) |W
w/
+
G2 E/ (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(w) ((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)/////00 (1))/
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 [t] be produced by Algorithm 2 with =
Let (A2) hold true and 1 V (wyj 41 2,,22) ) 11 S for some on and any j. Then,
Fs(wo) 8LMag 2
EA (Fs((
in
Furthermore, choosing 7 x 1/vt 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 (1g())))) 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///ggthu..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 structured data. arXiv preprini /rXXiv:/306.6: 2013.
[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-Bianchhi, 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://shacwvanggee
github. 10 htt.hi/.eepppppe///ooooooooooorr
[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": "_JZQNie6vH", "reviewer": "Reviewer_3zKR", "summary": "\nThe paper focuses on pairwise learning, where the loss function depends on pairs of data samples. In particular, the paper provides novel algorithms for both offline and online settings. In each iteration of these algorithms, the number of used samples is 1. This is precisely the main importance of the work, as the previous works used either all the previously used samples or a buffer with size S; the former results in high computation complexity (O(T) gradients at the T-th iteration), while the latter obtains a bound that is only useful when the buffer size (S) is large. On the contrary, the work uses a buffer size of 1, while obtaining the same generalization bound with the algorithm using all samples. Moreover, the authors provide thorough theoretical analysis of their algorithms including, generalization bounds, optimization bounds, stability results for both convex and non-convex as well as smooth and non-smooth functions. They finally provide some preliminary numerical results on AUC maximization. \n", "questions": "", "limitations": "", "rating": 9, "confidence": 4, "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 is very well-written, where all the assumptions, results, and distinction with the previous work are clearly stated. Moreover, they deliver important results on pairwise learning that is interesting in the machine learning community. The theoretical studies are thorough and include different settings, e.g., online and offline, convex and non-convex, smooth and non-smooth as well as different analysis, e.g., generalization bounds, stability, and optimization bounds. They further provide a differentially private SGD algorithm, which is interesting on its own. In overall, I find the contributions of the paper solid and quite strong. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The followings are only minor issues and typos.\n\n(a) In Line 176, it seems to me that the \"excess generalization error\" was supposed to be \"optimization error\".\n\n(b) I am personally familiar with pairwise learning and its importance, however, it might be good to discuss its applications in more details, regardless of the algorithms used for solving them.  \n\n(c) Typos:\n(c1) Line 45, \"becomes to\" --> \"goes to\"\n(c2) Line 70, \"can also apply to\" --> \"can also be applied to\"\n(c3) Line 133, \"It is worth of pointing out\" --> \"It is worth pointing out\"\n(c4) Line 153, I believe the authors meant to say that the gradient is NOT an unbiased estimator. \n(c5) Line 213, \"rends\" --> \"renders\" ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": ["I don’t know"], "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "ZQQX0pspjFc", "reviewer": "Reviewer_NJf5", "summary": "The paper is about a variant of online learning for pairwise learning. The authors select the last sample as the sample to pair the current sample with. This is different from previous algorithms that select random subsets or a random single sample. The algorithm per se is nothing really new as it can be viewed as a special case of previous algorithms. The focus of the paper is to analyze generalization capabilities of this algorithm. The authors show that it generalizes well despite being so limited which is surprising. The key obstacle is in the fact that the gradient estimators are no longer unbiased. \n\nThe main contributions of the work are in the analyses of the generalization property in the online and offline setting, and there are similar results in a differential privacy setting. ", "questions": "", "limitations": "", "rating": 7, "confidence": 5, "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": "I appreciate and value the contributions due to the fact that 1) the result is surprising due to the algorithms being very restrictive, and 2) the gradient is a biased estimator which makes any analysis tricky. \n\nThe paper is well written.\n\nThe computational experiments are somewhat superfluous. The paper is theoretical and the experiments seem to be artificial. The algorithm proposed could (should) be compared but such a comparison needs to be much more comprehensive. The current results are very limited. \n\nSome specific remarks:\n1) ERM is never defined\n2) only when s becomes to infinity as n ???\n3) \"It was mentioned in [20]\" should be \"It is mentioned in [20]\"\n4) \"when a FIFO buffering set with a very small size\" ???\n5) 128: to the size\n6) 151: does not work; Why not? I assume it select the current sample and a random previous sample. \n7) 158: analyses\n8) F is never defined. I get it that it is the population loss but this is never defined. \n10) A1: I assume G is a constant and not a function of z, z^\\prime\n11) 187: to convexity\n12) A4: unclear; Does it have to hold for any subset S? What is w_S? I assume it is w_S^*", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "yes", "review_text": "", "extra_scores": {"ethical_concerns": "no", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "6aZLakZclQy", "reviewer": "Reviewer_4Fd5", "summary": "Pairwise learning seeks to minimize objective functions that are sums (or expectations) over pairs of observations from a dataset. Online learning strategies are difficult to mix with this structure as the number of terms grows quadratically in the number of observations. This paper proposes to take as a stochastic gradient only the gradient of the term corresponding to the last pair of observations; it presents rigorous analysis of the performance of this strategy. This paper studies the generalization error of both a multi-pass SGD (Algorithm 1) and a single-pass SGD (Algorithm 2). ", "questions": "", "limitations": "", "rating": 5, "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": "This paper presents convergence results in a wide number of settings (smooth, non-smooth, under a Polyak-Lojasiewicz condition). It is thus dense but well presented. \n\nI would like to understand better the benefit of the approach of the authors. In the online framework, it is clear that using the loss over the last pair (and not over the $n-1$ new losses that involve the $n$-th observation), the computational cost per iteration is much smaller. However, this seems to come at the loss of a lot of statistical information. What does your theoretical analysis conclude on this tradeoff? Are your algorithms better than the classical \"pointwise learning\" approach?\n\nA related question is the following. Say that I set myself in the non-smooth setting, and I have $n$ observation. I can apply Algorithm 1, and by Theorem 1, after $n^2$ iterations, I get a performance of $O(1/\\sqrt{n})$. But I can also apply Algorithm 2. In that case, I use Remark 6 and the claim of l.257-261, after $n$ iterations, I get a performance of $O(1/\\sqrt{n})$. Should I be surprised that Algorithm 2 is so much faster?\n\nYour paper raises several time that the difficulty in your proof is the correlation between $w_{t-1}$ and the randomness $\\xi_t = (z_{i_t}, z_{i_{t-1}})$ that is used to build the stochastic gradient. Alternatively, the problem is that $\\xi_t = (z_{i_t}, z_{i_{t-1}})$, $\\xi_{t-1} = (z_{i_t={t-1}}, z_{i_{t-2}})$, $\\dots$ are not independent. But they form a Markov chain, that is quickly mixing ($\\xi_t$ and $\\xi_{t-2}$ are independent). I know there are papers that study SGD when the source of randomness is a Markov chain, see, e.g., https://arxiv.org/pdf/1809.04216.pdf . Have you considered this approach? Do you think you could plug-in your problem into their results (or similar results by other authors) in order to obtain the convergence of the optimization error? \n\nMinor remarks:\n- L. 272: why does the convergence rate increase with $s$? Shouldn't larger batch sizes help? \n-  L. 67: what is $d$? \n- L.190-192: do you have examples where the PL condition holds for a pairwise learning problem? \n\n=============\nAfter the rebuttal: \n\nAfter the conversation with the authors, my main concern would be whether this work is novel enough to be published at the NeurIPS conference. The algorithms, results and proofs are closed variants of the \"pointwise\" framework; the main new difficulty is the correlation between stochastic gradients, but we know from Markov chain SGD (see above) that it can be handled (some of the results of the paper can even be derived rigorously from https://arxiv.org/pdf/1809.04216.pdf). Note that I'm not an expert in pairwise learning, but rather of SGD, so I may have a biased perspective. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I am not sure whether the proposed algorithms are significantly faster than the more naive approaches, see my question above. It could be beneficial to make this more clear in the paper. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The main topic of this submission is an online and stochastic gradient method for pairwise learning (fix title of submission). There was a very constructive discussion between the reviewers and the authors, leading to clarification about the various points of the analysis.

Based on my own evaluation, I recommend to accept.
Decision: Accept (Poster)