Generalization Guarantee of SGD for Pairwise Learning
Authors: Yunwen Lei
Mingrui Liu
Yiming Ying
Venue: NeurIPS 2021 Poster (2021)
Keywords: Pairwise Learning
Algorithmic Stability
Generalization
SGD

Abstract: Recently, there is a growing interest in studying pairwise learning since it includes many important machine learning tasks as specific examples, e.g., metric learning, AUC maximization and ranking. While stochastic gradient descent (SGD) is an efficient method, there is a lacking study on its generalization behavior for pairwise learning. In this paper, we present a systematic study on the generalization analysis of SGD for pairwise learning to understand the balance between generalization and optimization. We develop a novel high-probability generalization bound for uniformly-stable algorithms to incorporate the variance information for better generalization, based on which we establish the first nonsmooth learning algorithm to achieve almost optimal high-probability and dimension-independent generalization bounds in linear time. We consider both convex and nonconvex pairwise learning problems. Our stability analysis for convex problems shows how the interpolation can help generalization. We establish a uniform convergence of gradients, and apply it to derive the first generalization bounds on population gradients for nonconvex problems. Finally, we develop better generalization bounds for gradient-dominated problems.

Generalization Guarantee of SGD for Pairwise Learning
Yunwen Lei'
Mingrui Liu? Yiming Ying²
1 School of Computer Science, University of Birmingham, Birmingham B15 2TT, United Kingdom Department Computer Science, George Mason University, Fairfax, VA 22030, USA Department of Mathematics and Statistics, State University of New York at Albany, USA y mei@bham.cc ac. singruil@gmu. edu yyingäalbany. edu
Abstract
Recently, there is growing interest in studying pairwise learning since includes many important machine learning tasks as specific examples, e.g., metric learning, AUC maximization and ranking. While stochastic gradient descent (SGD) is an efficient method, there is lacking study on its generalization behavior for pairwise learning. this paper, we present systematic study on the generalization analysis of SGD) for pairwise learning to understand the balance between generalization and optimization. We develop a novel gigh-probabilitty generalization bound for uniformly-stable algorithms to incorporate the variance information for better generalization, based on which we establish the first nonsmooth learning algorithm to achieve almost optimal high--robbbbility and dimension-indepeedder excess risk bounds with On)) gradient computations. We consider both convex and nonconvex pairwise learning problems. Our stability analysis for convex problems shows how the interpolation can help generalization. We establish uniform convergence of gradients, and apply it to derive the first excess risk bounds on population gradients for nonconvex pairwise learning. Finally, we extend our stability analysis pairwise learning with gradient-dominated problems.
Introduction
Many machine learning problems can be formulated as learning with pairwise loss functions, where the performance of the associated models needs to be quantified on a pair of training examples.
Representative problems include AUC maximization [14] 25 42
63 66), metric learning (8) 31].
ranking 13 and learning with minimum error entropy loss functions 22 For example, in supervised metric learning we wish to find distance function between pairs of examples so that examples within the same class are relatively close while examples from different classes are far apart from each other. In ranking, we aim to find function to predict the ordering of examples. This motivates the recent growing interest in a unifying study of these problems, under the framework of pairwise learning 29
32
40 58).
Stochastic gradient descent (SGD) is a workhorse for machine learning due its cheap computation complexity, simplicity and efficiency 7 220 49 53 62 65). SGD iteratively updates the model based on stochastic gradients computed on one or several randomly selected training examples, which can achieve sample-size independent iteration complexity for a prescribed optimization accuracy. This is especially attractive for pairwise learning as the objective function involves O(n²) terms for problems with n training examples. An important problem on SGD is to understand its generalization performance, i.e., how the models trained by SGD would behave on testing examples. While there are some interesting work the generalization analysis of SGD for pointwise learning 9
10 28 36 39
there much less work on SGD for pairwise learning. A notable difference between pairwise learning
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

and pointwise learning is that the objective function in pairwise learning involves O(n²) dependent terns, which introduces a difficulty in handling this dependency. For example, one needs to decouple this dependency to apply concentration inequalities established for independent data. Furthermore, for algorithmic stability analysis, a perturbation of the training dataset by single example can change ((n) terms in the objective function, which is more challenging than stability analysis of pointwise learning. To our best knowledge, the only work on generalization analysis of SGD for pairwise learning are [40] 55 59]. However, their analysis requires restrictive assumptions on convexity, smoothness and Lipschitz continuity of loss functions. Furthermore, they fail to incorporate the interpolation (low noise) assumption into their generalization guarantee.
In this paper, we initialize a systematic generalization analysis of SGD for pairwise learning under general assumptions. Our contributions are listed as follows.
1. We develop a novel high-prohability generalization bound for uniformly-stable algorithms, which incorporates the variance information to improve the learning performance. We apply this result to develop the first -nndpeenonnndeeeeennt prgb-prbbbbility bound O(1/ vn) (up a log factor) for an algorithm with (n) gradient computations to solve nonsmooth learning problems.
2. We study the stability and generalization guarantee of SGD for pairwise learning with convex loss functions, covering both smooth and nonsmooth problems. Our analysis suggests an early-stopping strategy for getting excess population risk bounds of the order O(1/ /T)) and O(1/ for convex and o-strongly convex problems, respectively. Under an interpolation or a low noise assumption, we improve our excess risk bounds to ((1/n) by exploiting the smoothness assumption.
3. We provide the first generalization analysis of SGD for pairwise learning with nonconvex loss functions. We establish uniform convergence of empirical gradients to population gradients by showing its connection to Rademacher chaos complexities. We then apply this uniform convergence to develop high--robabillity generalization guarantees for general nonconvex pairwise learning. Under a gradient dominance assumption, our stability analysis gives dimension-inndeeeddent bounds.
The paper is organized as follows. We survey the related work in Section 2 and give the problem formulation in Section B We study convex and nonconvex pairwise learning in Section 4 and Section 5 respectively. Conclusion is given in Section In the appendix, we present all the proofs, specific examples of pairwise learning and preliminary experimental results.
2 Related Work
We first review the related work on algorithmic stability. Algorithmic stability is an important concept in statistical learning theory (SLT) with close connection to learnability (52 The modern framework of stability analysis was established in a seminal paper [3]. where the important uniform stability was introduced. This stability measure was extended to study randomized algorithms in [18] and motivates several concepts including argument stability [39 43), Bayes stability [41] and on-average stability [39 54). Algorithmic stability has shown its remarkable effectiveness in deriving dimension-indepeenenn generalization bounds for various domains including stochastic
optimization 10
36
51 structured prediction 44 transfer learning (37 and differential
privacy 33 48 Recent progress shows tradeoff between optimization and stability 55], and its
applications to yield almost optimal high- probabiiiyy generalization bounds 6 22
We now review the related work on pairwise learning. There are two popular approaches to studying the generalization performance of pairwise learning: the uniform convergence approach and the algorithmic stability approach. The idea of uniform convergence is to control the uniform deviation between training errors and testing errors over a hypothesis space. The complexity measures of function spaces play an important role in this approach, including VC dimension, covering num- bers [7 (58 60) and Rademacher complexities [8 32). Furthermore, one needs to use concentration
inequalities to handle the associated U-statistics and U-processes [13] 16 50). Algorithmic sta-
bility of ranking [I] and metric learning [31 [57] was studied for strongly convex objectives [30]. High-probability bounds of the order ( log n + 1/vn) were recently developed for e-uniformly stable pairwise learning algorithms (40. A nice property of stability analysis is its ability to yield dimension-independeen bounds, while a square-root dependency on the dimension is inevitable
for uniform convergence analysis when considering general problems (1]. However, algorithmic stability generally requires convexity assumption which is not required for the uniform convergence

---

approach. Other than the above two approaches, several researchers have studied the generalization behavior of pairwise learning using the algorithmic robustness
T2 and integral operators [19] 27
Before we move on, we add more discussions with a very related work on generalization analysis of pairwise learning 13 [5]_ The work (50) considers very general problem setting for SGD with K K-saplle U-statistic of degrees (d1...., dx) ), which includes our algorithm as a special case with K = and dj = 2. shows the advantage of reducing variances using gradient estimates through incomplete U-statistics over that through complete U-statistics based on subsamples. We sketch the difference as follows. First, the generalization analysis in Papa et al. [50] requires smoothness and strong convexity assumptions. As a comparison, we also consider nonsmooth problems (Section 4.2) and nonconvex problems (Section 5). Second, the work [50] studies generalization via the uniform convergence approach and requires a complexity assumption. As a comparison, we also study generalization via a fundamentally different algorithmic stability approach. The classical work 13 focuses on the exact solution of empirical risk minimizer for pairwise learning from the perspective of uniform convergence. As a comparison, we study the excess risk of SGD via both an algorithmic stability approach and an uniform convergence approach, for which we also consider the tradeoff between optimization and generalization.
3 Problem Formulation
3.1 Pairwise Learning and Stochastic Gradient Descent
Let p be a probability measure defined on Z X' y with an input space X' and an output space V. Let S = {zi...., J be drawn independently according to p. from which we aim to learn a prediction function h : X' + R or h X X' + R. We consider parametric models where the prediction function w can be indexed by an element w E W, where W is a d-dimensional Hilbert space. We consider pairwise learning problems where the performance of a model low on an example pair (z, 2') can be measured by a nonnegative loss function f(w; z, z'). This is in contrast to standard pointwise learning (e.g., classification and regression) where we can measure the quality of a model via its behavior on an individual point. Two notable examples of pairwise learning include ranking and supervised metric learning. For ranking, we build a function hw : X + ) to rank instances in way consistent with the outputs, i.c., (z) < hw(2')) (x") if y y for two example pairs 2 = (a. y). 2' = (z', v²). Then we can formulate ranking as a pairwise learning problem with f(w; 2') (ssg((yy (/w (z) h='))))) ()),)) where sgn is the sign function and s can be either the hinge loss (+)) = max (1 - 0, or the logistic loss (t)) = log(1 + exp(- find distance function under which examples with the same label are similar while examples with different labels are apart from each other. A popular distance function takes the form hww (1, x²) = (w, (x z' x')T> ) where E Rd is positive definite. We can formulate supervised metric learning as pairwise learning with f(w 2, 2/) = ( //) (2, x²) ))), where T(y, y') = 1 if y = 5/ and -1 otherwise.
For supervised metric learning with y' [-1,+1},
[f(w; Z, Z'), where Ez,2' denotes The population risk of w in pairwise learning is F(w)= = E,,, [f(w;
the expectation with respect to (w.r.t) Z, Z' ~ p. The empirical risk of w is
Fs(W)= = n(n
1
Σ i E.E
(w;
where [n] = (I....,m). Let w = arg wew Fs(w) and w" = arg win F(w). For a randomized algorithm A, we use ASS) to denote the output model produced by applying A to the dataset S. We are interested in the excess risk F(A(S)) - F(w"). which measures the relative behavior of A(S) as compared to the best model. A standard approach to handle F F(A(S)) F(w") is to use the following error decomposition
Es,A (F((S) - F(w")] ES,A (F(((S)) - -Fs +Es. - (s(w")) )} (3.1) where the first term F(A(S)) Fs()))) is called the generalization error and the second term (A()) - (s(ww) is the optimization error. These two errors can be handled by tools in SLT and optimization theory, respectively. We are interested in the specific SGD for pairwise learning.
Definition (SGD for Pairwise Learning). Let w1 = 0 E Ied and {nc}e be a stepsize sequence. Let V f( 2i, zj.) ) denote the gradient of f w.r.t. the first argument. At the f-th iteration, we first draw (e)) from the uniform distribution over all pairs ((1.)) : ( E [m], i o j} and then update
W++1 W. T/ V f(w: Bigy 23,)
(3.2)
3

---

Note our problem setting is totally different from some online learning setting where the streaming examples are assumed to be drawn from the true probability measure p [T5]. Indeed, we consider the offline setting where the dataset is given beforehand and during the optimization process we actually randomly draw an example from the empirical measure. This necessitates the consideration of the generalization gap which is not touched in the online learning setting [15]- An advantage of SGD is that its computational complexity to achieve an accuracy is independent of the number of pairs, which is particularly attractive for pairwise learning (gradient descent requires On²²) gradient computations per iteration). We describe SGD(S, T, J. {me } in Algorithm of SGD with dataset S, iteration number T, loss function f and stepsize {m J. Algorithm was also studied in [40], which however requires restrictive assumptions on convexity, smoothness and Lipschitz continuity. We significantly extend their discussions by considering either nonconvex, nonsmooth non-Lipschitz loss. Moreover, our analysis can clarify the effect of interpolation on generalization.
Algorithm 1: SGD(S, f.
Input: initial point W learning rates {ne),, and dataset S ,
for / = 1, 1.2....,7 do
draw (4,, uniformly over all pairs [(i.)) = E [m], + j}
update W according to Eq. (3.2)
4 end
Below we introduce necessary definitions and assumptions. Let || ||2 be the Euclidean norm and (:,) be the associated inner product. Let 6 = supz,z'ez f(0; 2, and = supz, f| 2, 2 1l2
We denote B x B if there absolute constants e₁ and 62 such that ei B < B S B. We collect the notations of this paper in Table A.
Definition 2. Let g : W + R, L, G 0, 0.
1. We say g is L-smooth if VV((w) Vg(w')ll2 S L// w for for w, w' E W.
We say g is G-Lipschitz continuous [g(w) - g(w)) S Gl[ w'lla for all w, w' W.
3. We say g is o-strongly convex w.r.t. |1. if for all w, w' E W. We say g is convex g is --strongly convex with a = 0. Assumption 1 (Convexity). Assume for all z, x' E Z, the function w f(w;z, is convex.
Vg(w"))) 2 o||w w w/1B/2
Assumption 2 (Boundedness of Gradients). Assume for all 2, and w E W. IV/ 2, z2)lla S G. Assumption 3 (Smoothness). Assume for all 2, + f(: 2') is nonnegative and L-smooth.
3.2 Algorithmic Stability and Generalization
A fundamental concept in SLT is the algorithmic stability, which measures the sensitivity of an algorithm w.r.t. the perturbation of the training dataset. Various stability measures have been introduced in the literature, including uniform stability
(5). hypothesis stability 18), argument stability [43] and on-average stability [54]. We focus on uniform stability and on-average stability here. The following on-average loss stability was introduced in 40) while the on-average argument
stability was motivated by similar concept in pointwise learning (39 Let S = (Z1, -.,,,, } S'
(z(,..., ",,} be independently drawn from p. We denote
S: { [Z...... Zi- 24,
Zn
Vi [n].
(3.3)
= (21, Zy- 2/1 3 1, 1z 25y0 Z5t1..... )n), Vi Vikj E [m].
(3.4)
Definition 3 (Algorithmic Stability). Let S {21, {.1,..., Zn. and S' independently from p. For any i.j E [m], denote S. as (3.3) and S as 3.4 { 2 be drawn
1. We say a deterministic algorithm A n + W is euniformly stable if for any datasets S,S E 2 that differ by at most a single example have sup,,se2 [f((S)); 2, 2) (A((S); 2) S
2. We say randomized algorithm A is on-average (loss) e-stable if
Σ
Es.s - Se.
( 1)

---

3. We say is on-average argument e-stable B. 1 E |IA(S) A(S)) Se..
The following theorem establishes the connection between on-average stability and generalization in expectation for pairwise learning. Part (a) was due to [40], while Part (b) was motivated by a similar result in pointwise learning 339. The proof is given in Appendix B
Theorem 1. (a) If A is on-average (loss) e-stable, then [B[((A(S) Fs(A(S)) S.
(b) If A is on-average urgument e-stable and Assumption 3 holds, then for any 7 > we have
B[F(A(S)) - Fs(A(S)) < 2(L + 7))" Ly L[
Remark 1, We can choose y x (AS) in Part (b) and get the bound E[F(A(S)) Fs(A())) 0 + bounds better than Oe)). In particular, if [B["s(((S)) O which much faster than (c)) in Part (a).
Therefore, if (FF(((S))) is small, Part (b) can imply
O(e²) the bound in Part (b) becomes
Theorem 2 estaablihes the connection between uniform stability and generalization with high prob- ability for pairwise learning. The proof is given in Section[C] whose novelty is to use decoupling techniques to address the coupling among O(n²) terms in the objective function of pairwise learning.
Theorem 2. Let A be an e-uniformly stable and deterministic algorithm.
Let B f(w"; Z, 27)
sup,,2' 2,=² [Es (A 2, f(w') 22,22) z²) and ob = Ez,z's (f((()); Z, Z')
For any 5 E (0, 1), the following inequality holds with probability at least 1
2B 2B log(2/8)
20 log (2/5) [n/2]
598v log n log(2e/0)+
3 ]|n/2]
Note we only impose a bounded loss assumption on A(S). which can be achieved by truncating the value of the output function. Theorem pointwise learning, high-probability generalization bounds of the order O log were developed for e-uniformly stable algorithms under a further Bernstein condition on the variance-expectatioo relationship (34) High-probability bounds O log n + 1/ 1/v/) were also developed for e-uniformly stable algorithms in pairwise learning [40]. We refine these results by developing generalization bounds OE log n + Voğ/n). where oß the variance of the excess loss at the output model. If this variance is small, then our bounds can be much better than that in 40 For example, if F is --strongly convex, then one can show that this variance can be bounded by O (E(F(A(())
Remark 2.
2 was motivated by the recent work [34 For
F F(w"))//) /l/)), and in this case the term v / in our bound would be o(n 3) instead of O(n 5) in [40]. As we will show, Theorem 2 can imply almost optimal excess risk bounds for an algorithm with (n)) gradient computations to solve nonsmooth problems (Theorem 8), for which the existing high-probability
analysis can only imply bounds of the order O(n
40
4 Pairwise Learning with Convex Loss Functions
In this section, we study the generalization performance of SGD for pairwise learning with convex loss functions. We consider conver/strongly-coneex and smooth/nonsmooth problems.
4.1 Convex and Smooth Problems
We first consider stability and risk bounds for convex and smooth pairwise learning problems. The proofs of results in this subsection can be found in Section E Theorem 3 gives the bounds for on-average argument stability of SGD. Note we do not require the loss functions to be Lipschitz continuous. nice property is that the upper bound involves the empirical risk of Wj- Since we are minimizing the empirical risk by SGD, it is reasonable to assume that Fs(w,) would become smaller and smaller along the learning process. It should be mentioned that a similar result was derived for pointwise learning [39]. A key difference in the stability analysis for pairwise learning that a change of z, would influence 2(n - 1) pairs (zz; 2,); (2i, 2,) for j # i. We need to use the U-structure of the empirical risk to prove this result.
5

---

Theorem 3 (Stability bound). Let Assumptions 0 3 hold. Let A be SGD (Algorithm with njj I L. Then with iiterations is an-averege argument e-stable with e²
16/(1+2//m)e Σj=1 F(w,))
Based on Theorem we get error bounds for pairwise learning with convex and smooth functions.
Theorem 4 (Excess risk bound). Let Assumptions 7 hold. Let {we} be the sequence produced by
SGD (Algorithm) 1 dataset of size with π = 2 Then for WT = + Σ 1 We and any 7 2 we have the following inequality for all w independent of A (can depend on S)
B(F(wr) Fs((w))))) - (0()+) 1 (( + T n
E B(Fs(w)))
7
n
E w
7m(1
T (4.1)
Tn
notable property of the above bound is that holds for any w independent of A. If E w Il is finite, we can choose =w3 in Eq. 441) and get bound involving F[Fs w })}. Furthermore, if we are in an interpolation or overparameterized setting 45 then E (( = o(1/ (1/ and
the generalization will improve according to (4.1. Therefore, our stability analysis provides an explanation on how innerpolaionnoverrraaatttttiiiie
can help in generalization. Note SGD has an implicit bias to choose model with small norm and therefore it is reasonable to assume Elllss [12] < 0o. We can also choose w = w in Eq. 44. y to get optimistic bounds in the sense of involving F(w*). which decay fast if F(w*) is small [56] 60). Indeed, the following corollary gives the bound O(1/ in the general case and improves to O(1/n) F(w") = O(1/n). Note here the assumption F(w") O(1/n) just show that we can get improved bound under low noise conditions. The term F(w*) should be independent of n.
Corollary 5. Let Assumptions in Theorem hold.
(a) We can choose T); = = 1/VT and xn to get ([F( -[(") =0
(b) (F(w")=0(11 choosing 7i = n S 2/L and x n yields -
Remark 3. Stability and excess risk bounds of the order O(1/ were studied for SGD applied to pairwise learning [40 (55. However, these discussions require the loss functions to be smooth, Lipschitz continuous and convex. As comparison, we remove the Lipschitz continuity assumption. Furthermore, their discussion can only imply non-optimistic bounds of the order O(1/vn). As comparison, our discussions can fully exploit the property of F(w*) to imply fast bounds (1/n)).
4.2 Convex and Nonsmooth Problems
We now turn to pairwise learning with convex and nonsmooth functions. Theorem 6 gives the argument stability bounds based on which we develop excess risk bounds Theorem The proofs of results in this subsection are given in Section
Theorem 6 (Stability bounds). Let Assumptions 7
2 hold. Let S = (21,...; :.......,]] and S' = {z(...., 2 be two datasets that differ by a single point. Let {we), (w(( be the sequence pro- duced by SGD (Algorithm 2 w.r.t. S and S' with = respectively. Then
E[[ - -'4 < 4G + 4t 4t/n²)n?
(4.2)
For any 8 E (0, 1) with probability at least 1 - 8 we have
| w1+1 < 4G 17 + (2t/n + log(1/5) + / Atn log(1/6) 1)
Theorem 7 (Excess risk bounds). Let Assumptions 1 hold. Let }w,} be the sequence produced by SGD with 7): > T- IfT = n², then E[F(
F(w*) (n-z)) $).
Remark 4. As compared to the stability bounds in the smooth case (Theorem 3) the stability bounds
in 4.2) are worse in the sense that we do not have a factor of 1/n in 4.2p Therefore, one needs
to choose very small stepsizes to let the right-hand side of (4.2) vanish to O. Indeed, Theorem 7
suggests 1), x 3 which are much smaller than the 7), T 2 in the smooth case. As result,

---

require to run SGD with T x n² to get the optimal excess risk bounds (n)/vn). Note we also give high-prohin probaabiyyyl bounds on the argument stability Theorem 6 It should be mentioned that the stability of a variant of SGD as Wt+1 = W. - 2 V Wri 2i, Zi,) was recently studied for pairwise learning with convex and nonsmooth loss functions [59]. Note this update requires O(t)
gradient computations at the t-th iteration, while (3.2) only requires a single gradient computation.
Algorithm 2: Iterative Localized Algorithm for Pairwise Learning
Input: initial point Wo parameter Y > 0, k: for i 1,2,..... k do set T; n, = 2 7 2. 1/: I+1
[ logz n
DiRS & N.f(w; f(:: + T:m;
|| w
draw a sample St of size n, independently from P
apply SGD(S;, J. (m+)) to minimize the following problem and get
Fs. (w) == ni(n; =,
1
Σ
f(w;2,z') + 7044
w w
(4.3)
end
Note SGD requires the undesirable Onn²) gradient computations to achieve the bound OLL/ /n) for nonsmooth problems. The following theorem shows one can also achieve the bound O(1/ with (nn) gradient computations by considering Algorithm 2 Algorithm (a is motivated from the iterative localization approach established in pointwise learning [23], which was also used to develop efficient differentially private algorithms [2] Note the choice y = n | [[ depends on the unknown ||w*|2 However, one can get the bound O(D/ vn) by choosing ? D/vn ||w" S D.
Theorem 8. Let Assumptions 7 2 hold and ō E (0, 1). Let wy be produced by Algorithu and B for some > 0. we we choose 7 x n [/w]]] //'l.. then with = (Iog(loggn)))) (lo) n)] /// 2l2// (n). Moreover. Algorithm 2 requires only ((n) gradient computations to achieve this excess risk bound.
assume sup [W[ 2, z z']]l
probability at least we have F(wx)-F(())
Remark 5. Iterative localization approach was developed in [23 35 to develop novel algorithms with (n) gradient computations and O(L/vá) excess risk bounds for nonsmooth pointwise learning problems. We extend this technique to the pairwise learning setting. Furthermore, the excess risk are stated expectation. As comparison. we use the novel pros-hptbbbblityy bounds for uniformly stable algorithms established in Theorem 2 to develop high- nigh-probability bounds of the order (log" nt) Vn. which has not been developed even for pointwise learning (the best high-probabillty excess risk bound for SGD with nonsmooth loss functions requires (nn2) gradient computations 33.. Note that the sample size nu X vn in the k-th epoch, and therefore the high-
bounds in 23 35
probability bounds in 40 can only yield bounds (m 3) = O(n=t) for Algorithm 2 As a comparison, Theorem applied to the ERM of Fs, yields the bounds O(n + O(n b)
(ERM of Fs. is "/k -x-nifoorlly stable and the last term the bound in Theorem is dominated), This demonstrates the advantage of our high-probabie probability bounds in Theorem 2 for developing almost optimal bounds with O(n) gradient computations. Another difference is that we apply iterative localization framework with & [ log, n instead of k'' flog2 n epochs in [3 357. The
underlying reason is that the high-probability bounds for ERM of Fss, involve niz + + while the bounds in expectation only involve 7/ [40]. Since ny x 1, our high-probability analysis only implies vacuous bounds (1) if we use k [log2 n. epochs.
4.3 Strongly Convex Problems
We now turn to strongly convex cases. Theorem gives bounds for smooth problems, while Theorem gives excess risk bounds for nonsmooth problems. Note Tnd which give general relationship between excess risks and optimization errors. One can plug the optimization error bounds for any algorithm to immediately derive the corresponding excess risk bounds. The proofs of results in this subsection are given in Section G
to any algorithm,
7

---

Theorem 9 (Strongly Convex and Smooth Problems), Let Assumption Soold Assume for all S E Z", Fs is o-strongly convex W.E..
||
112. Let A be randomized algorithm and on 2 8L. Then
16L
_ no
2L [[[[((((5))) - -
B[F(A(S)) - S 128L
+
n²
Remark 6. The above bound involves two components. The first component ((1/(ng) depends only on the landscape of the learning problem. The second component involves optimization errors, shows that optimization is always beneficial to improve generalization for strongly convex problems. Furthermore, also shows that one can stop the algorithm once we achieve the optimization error bounds O(1/n) since further optimization would not improve essentially the generalization. Theorem 9 also implies bounds of the order o(1/(1a)) Fs(w") is small.
Theorem 10 (Strongly Convex and Nonsmooth Problems). Assume J lakes a structure as [ww 2, 2) = f(w; 2, z') + r(w). Assume for all z', the mup - f(w;,,z') is G-Lipschitz. Assume for all S E 2", Fg a-strongly convex w.r.l. 1112- For any algorithm we have
SG
2E Ps(A(S)) - -s(w3)]
B[F(A(S)) F(w*) + +
We present the specific applications of the above results to SGD in Corollary
G.2
(Section
G
5 Pairwise Learning with Nonconvex Loss Functions
In this section, we consider excess risk bounds for pairwise learning in nonconvex setting. In this case, the excess population risk not a reasonable measure since we cannot guarantee that the algorithm can find a global minimizer. We therefore use the norm of gradients at A(S) to measure the performance of A 126 68). In a general nonconvex setting, SGD requires to choose T)t = O(1/t) for meaningful stability bound (28) for which the optimization errors would decay logarithmically w.r.t the number of iterations 226. Then, stability analysis fails to trade-off the stability and optimization for model with good generalization performance in general nonconvex problem. Therefore, turn to different uniform convergence approach in a general nonconvex sctting [38) After that, we
study stability of SGD for nonconvex problems under a further PL condition.
5.1 Uniform Convergence of Gradients for Pairwise Learning
Our first result for nonconvex pairwise learning is a uniform convergence of gradients. Specifically, we show that the uniform deviation between population gradients and empirical gradients over a space can be bounded by the associated Rademacher chaos complexity. Let Wn {w E W: ||w||2 S R} for O. The proofs of results in this subsection are given in Section
Definition 4. Let F == ( : 21 + R. be a function class and S { 2. Let (e.]1 18
be independent Rademacher variables with Pr(e; 1} Prfc: = -1] = 1/2. The empirical Rademacher chaos complexity for F w.r.t. S' is defined as
Us(F)=
1
sup SEF
Σ
1SKJSHH
Theorem 11 (Uniform Convergence of Gradients). Let E (0, 1), R
> 0 and S = :21,...,2y, be drawn independently from p. If Assumption 3 holds, then with probability at least - we have
|VV - VFs(w)) 2 (2 + Vlo(1188)
Us(FR)
sup wEWn
+4V
Vn
n
where
FR= (21, 22, 23, 24) + (VI(w; V/
([(; : W E WR).
We can apply the entropy integral to control the above Rademacher chaos complexity 16 61 and get the following result. Note d is the dimension of the space W.
8

---

Corollary 12. Under Assumptions of Theorem 17
with probability at least 1 we have
2/2(LR 8)
[FF[w))VFs(w)]] - wEWR
sup
2+ 966 log 2 + (llg))))) + Mlg(1 1og(1/6)
vn
The above uniform convergence rate involves square-root dependency on d. We show that this dependency can be avoided we consider a special class of functions with a specific structure
z(; <b( (w, o(x, m²)), rl,,
(5.1)
where @: x X W is feature map, 1/ R x R TR. is T-g-smooth the first argument and т :: x D + R. Loss functions of the structure (5.1) have wide applications in robust optimization and generalized linear models [24 46). We assume x supz,z' ||Ø(x, x2)12.
Corollary 13. Ler 8 E (0, 1), R 0 and S fzr,.... 2n} be examples drawn independently from Suppose f: W x 2² R takes the form (5.I) with sb being Læ-smooth w.r.f. the first argument. Then the following inequality holds with probability at least 1
VF(()- - VFs(w))l2 42
log((18)
sup wEWn
+
Vn
Remark 7. Uniform convergence of gradients was studied for pointwise learning based on covering
numbers [46] 64] and Rademacher complexities (24.. We extend these results to the pairwise learning setting. A key difference between pointwise learning and pairwise learning is that the empirical gradients for pairwise learning can be no longer written as a summation of i.i.d. terms. Indeed, the n(n - terms in FFs() are correlated, which introduces difficulties in applying concentration inequalities. We need to apply decoupling techniques in U-process to handle this correlation.
5.2 Smooth Problems
We now study the generalization performance of SGD) for pairwise learning based on the uniform con- vergence of gradients developed in the previous subsection. We first introduce necessary assumptions. Since тhe is always small (a typical choice is т/t x 1/vT),, Eq. (5.2) is milder than a bounded gradient assumption. Eq. (5.3) imposes a bounded variance assumption on stochastic gradients, which is standard assumption for the analysis of SGD 22 36 67].
Assumption 4. Assume the existence of G > 0 and 01 > 0 such that
z, x 1| G, v4 N, 2, z' E Z, Ei [ f 2,, 2z.) V (w)) [ S of W N.
(5.2)
(5.3)
Theorem 14 gives high-probability bounds on the norm of population gradients. Our basic idea is to use the following error decomposition
F (w.))l < 21IVF(w.) - (w. + +2/VFs
We refer to the first term on the right-hand side as the generalization error for nonconvex pairwise learning, which can be bounded by the uniform convergence of gradients established in Theorem IT] The second term is the optimization error and can be addressed by techniques in optimization theory. The proof is given in Section !
Theorem 14 (Smooth Problems). Let Assumptions aand Ahold. Let { [We]e be the sequence produced by (3.2) with nh n/ T and 7 S. vT (2L) Then for any d E (0, 1), we can choose T x nd to derive the following inequality with probability at least 1-8
1 T
IVF((,))
10g (1
(5.4)
Furthermore, if takes the specific structure inequality with probability at least -
5.1 we can choose x n derive the following
T
(WF( 0 (n=t log log²(1/6))
(5.5)

---

Remark 8. It is clear that the bound in (5.4) is crneensoon-depeneen which is due to the use of the uniform convergence approach. Eq. (5.5) further shows that this dependency on the dimension can be avoided for problems of a specific structure. Note the optimization enrors of SGD with T iterations for nonconvex problems satisfy + E (w: = O 26 This is consistent with the error bounds + Ee= (w: = On - log (1/8)) in 55. by noting T x n. Therefore, our analysis shows that the extension from optimization to generalization comes for free.
5.3 Gradient Dominated Problems
We now study the stability and generalization of SGD for pairwise learning with gradient-dominated objectives (or PL. condition). PL. condition is widely used nonconvex learning [24 33 and was shown to hold true for deep (linear) and shallow neural networks [10]. Intuitively speaking, PL condition means that the suboptimality measured by function values can be bounded by gradients.
Condition). Denote Fs wn Fs(w"). We assume F's satisfies PL or pradient-dominate condition (in expectation) with parameter / > 0, i.e.,
Assumption
1 Es [VVFss)))]]]
Es [Fs(w) Fs] - 2,3
V W.
(5.6)
Under the PL condition, we can get excess population risk bounds based on the stability analysis. The proof of Theorem 15]s given in Section J
Theorem 15 (Gradient Dominated Problems), Let Assumptions 2
hold. Assume [] [[w::[/] 2') S
B for all w E 2, E 2. Let {wite be the sequence produced by with T)
21+1 Then 23(++1)7
E [(F(WT)) F(w")((ww)))) 0
T D+C (0(T (
+ +0(1/(T33).
(5.7)
n
We can choose T x n 12277 3
TI3L7U
to get EE [F(WT)] - "(w")= 17279 B
21/8 T13L70)
Remark 9. Note the above bounds depend on the condition number cond L/B. If cond z 1, then we get EE [[(W)] F(w") = O(n 3). As cond increases, the bound increases to O(n 3)
6 Conclusion
In this paper, we present systematic study on the generalization performance for pairwise learning. We develop novel high- proobabiiiyy bounds for uniformly stable algorithms, and apply them to develop algorithms with optimal bounds with (n) gradient computations for nonsmooth problems. We conduct the stability analysis for various convex problems including smooth, nonsmooth and strongly convex objectives, and get optimal excess population risk bounds of the order 0(1/ for convex problems and ((1/(na)) for o-strongly convex problems, respectively. We conduct the uniform convergence analysis for general nonconvex problems, which imply the bounds of the order O(1/ Vn) for population gradients. We further study the stability and generalization for nonconvex pairwise learning with gradient dominated objectives. Our discussions can clarify the effect of interpolation on generalization. In Section L we present preliminary experimental results to verify our stability bounds.
It would be interesting to study the stability of SGD in general nonconvex case for getting dimension- independent bounds. would also very interesting study other stochastic optimization methods for pairwise learning, including variance reduction variants and momentum technique.
Acknowledgments
We are also grateful to the anonymous reviewers and area chairs for their insightful and constructive comments. Yiming's 's work is supported by National Science Foundation (NSF) under grants DMS- 2110836, 181622,, IIS-110546, 113-2103450.
10

---

References
[1] S. Agarwal and P. Niyogi. Generalization bounds for ranking algorithms via algorithmic stability. Journal of Machine Learning Research, 10(Feb):441477,, 2009,
[2] H. Asi, V. Feldman, T. Koren, and K. Talwar. Private stochastic convex optimization: Optimal rates in & geometry. arXiv preprint
16, 2021.
[3] R. Bassily, V. Feldman, C. Guzmán, and K. Talwar. Stability of stochastic gradient descent on nonsmooth convex losses. Advances in Neural Information Processing Systems, 33, 2020.
[4] A. Bellet and A. Habrard. Robustness and generalization for metric learning. Neurocomputingg
151:259-267, 2015,
[5] O. Bousquet and A. Elisseeff. Stability and generalization. Journal of Machine Learning Research, 2:499-526, 2002.
[6] O. Bousquet, Y. Klochkov, and N. Zhivotovskiy, Sharper bounds for uniformly stable algorithms. In Conference on Learning Theory, pages 610-626, 2020.
[7] R. Camoriano, T. Angles, A. Rudi, and L. Rosasco. Nytro: When subsampling meets early stopping. In Artificial Intelligence and Statistics, pages 4413-1411. PMLR, 2016. [8] Q Cao, Z.-C. Guo, and Y. Ying. Generalization bounds for metric and similarity learning. Machine Learning, 102(1):115-132, 2016.
[9] L. Carratino, A. Rudi, and L. Rosasco. Learning with sgd and random features. In Advances in Neural Information Processing Systems, pages 10213-10224, 2018.
[10] Z. Charles and D. Papailiopoulos. Stability and generalization of learning algorithms that converge to global optima. In International Conference on Machine Learning, pages 744-753, 2018.
[11] Y. Chen, C. Jin, and B. Yu. Stability and convergence trade-off of iterative optimization algorithms. arXiv preprint 1rXiv:1804.01619 2018.
[12] A. Christmann and D.-X. Zhou. On the robustness of regularized pairwise learning methods based on kernels. Journal of Complexity, 37:1-33, 2016.
[13] S. Clémençon, G. Lugosi, and N. Vayatis. Ranking and empirical minimization of U-statistics.
The Annals of Statistics, pages 844-874, 2008
[14] C. Cortes and M. Mohri. AUC optimization vs. error rate minimization. In Advances in Neural Information Processing Systems, pages 313-320, 2004.
[15] A. Cutkosky. Anytime online-to-bated optimism and acceleration. In International Conference on Machine Learning, pages 1446-1454. PMLR, 2019.
[16] V. De Pena and E. Giné. Decoupling: from dependence to independence. Springer Science
Business Media, 2012.
[17] M. Dong, X. Yang, R. Zhu, Y. Wang, and J. Xue. Generalization bound of gradient descent for
non-convex metric learning. In Advances in Neural Information Processing Systems, 2020.
[18] A. Elisseeff, T. Evgeniou, and M. Pontil. Stability of randomized learning algorithms. Journal of Machine Learning Research, 6(Jan):55-79, 2005.
[19] Fan, T. Hu, Q. Wu, and D.-X. Zhou. Consistency analysis of an empirical minimum error entropy algorithm. Applied and Computational Harmonic Analysis, 41(1):164-189, 2016.
[20] B. Fehrman, B. Gess, and A. Jentzen. Convergence rates for the stochastic gradient descent method for non-convex objective functions. Journal of Machine Learning Research, 21, 2020.
[21] V. Feldman. Generalization of erm in stochastic convex optimization: The dimension strikes back. In Advances in Neural Information Processing Systems, pages 3576-3584, 2016.
[22] V. Feldman and J. Vondrak. High probability generalization bounds for uniformly stable algorithms with nearly optimal rate. In Conference on Learning Theory, pages 1270-1279, 2019.
[23] V. Feldman, T. Koren, and K. Talwar. Private stochastic convex optimization: optimal rates in linear time. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, pages 439-449, 2020.
[24] D. J. Foster, A. Sekhari, and Sridharan. Uniform convergence of gradients for non-convex learning and optimization. In Advances in Neural Information Processing Systems, pages 8759 8770, 2018
[25] W. Gao, R. Jin,, S. Zhu, and Z. Zhou. One-pass auc optimization. International Conference on Machine Learning, pages 906-914, 2013.

---

[26] S. Ghadimi and G. Lan. Stochastic first-and zeroth-order methods for nonconvex stochastic programming. SIAM Journal on Optimization, 23(4):2341-2368, 2013.
[27] Z.-C. Guo, D.-H. Xiang, X. Guo, and D.-X. Zhou. Thresholded spectral algorithms for sparse approximations. Analysis and Applications, 15(03))433-455, 2017.
[28] M. Hardt, B. Recht, and Y. Singer. Train faster, generalize better: Stability of stochastic gradient
descent. In International Conference on Machine Learning, pages 1225-1234, 2016.
[29] T. Hu, J. Fan, Q. Wu, and D.-X. Zhou. Regularization schemes for minimum error entropy principle. Analysis and Applications, 13(04))437-455 2015.
[30] 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.
[31] R. Jin, S. Wang, and Y. Zhou. Regularized distance metric learning: Theory and algorithm. In Advances in Neural Information Processing Systems, pages 862-870, 2009.
[32] P. Kar, B. Sriperumbudur, P. Jain, and H. Karnick. On the generalization ability of online learning algorithms for pairwise loss functions. In International Conference on Machine Learning, pages 441-449, 2013.
[33] H. Karimi, J. Nutini, and M. Schmidt. Linear convergence of gradient and proximal-gradient methods under the polyak-tojasiewice condition. In European Conference on Machine Learning, pages 795-811, 1, 2016.
[34] Y. Klochkov and N. Zhivotovskiy. Stability and deviation optimal risk bounds with convergence rate O(1/n). arXiv preprint arXivv2103. 100.2244, 2021.
[35] J. Kulkarni, Y. T. Lee, and D. Liu. Private non non-smooth empirical risk minimization and stochastic convex optimization in subquadratic steps. arXiv preprint arXiv:2103. 100.:2223.555,, 2021.
[36] Kuzborskij and C. Lampert. Data-dependent stability of stochastic gradient descent. In International Conference on Machine Learning, pages 2820-2829, 2018.
[37] I. Kuzborskij and F. Orabona. Stability and hypothesis transfer learning. In International Conference on Machine Learning, pages 942-950. PMLR, 2013.
[38] Y. Lei and K. Tang. Learning rates for stochastic gradient descent with nonconvex objectives. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2021. doi: 10.1109/TPAMI 0021130681.0 15468154.
[39] Y. Lei and Y. Ying. Fine-grained analysis of stability and generalization for stochastic gradient descent. In International Conference on Machine Learning, pages 5809-5819, 2020.
[40] Y. Lei, A. Ledent, and M. Kloft. Sharper generalization bounds for pairwise learning. In Advances in Neural Information Processing Systems, volume 33, pages 21236-21246, 2020.
[41] J. Li, X. Luo, and M. Qiao. On generalization error bounds of noisy gradient methods for non-convex learning. In International Conference on Learning Representations, 2020.
[42] M. Liu, X. Zhang, Z. Chen, X. Wang, and T. Yang. Fast stochastic AUC maximization with
O D(I/))-convergene rate. In International Conference on Machine Learning, pages 3195-3203, 2018.
[43] T. Liu, G. Lugosi, G. Neu, and D. Tao. Algorithmic stability and hypothesis complexity. In International Conference on Machine Learning, pages 2159-2167, 2017.
[44] B. London, B. Huang, and L. Getoor. Stability and generalization in structured prediction. The Journal of Machine Learning Research, 17(1):808-7859, 2016.
[45] S. Ma, R. Bassily, and M. Belkin. The power of interpolation: Understanding the effectiveness of sgd in modern over- wer-parametrized learning. In International Conference on Machine Learning. pages 3325-3334, 2018. 8.
[46] S. Mei, Y. Bai, and A. Montanari. The landscape of empirical risk for nonconvex losses. The Annals of Statistics, 46(6A):2747-2774, 2018
[47] W. Mou, L. Wang, X. Zhai, and K. Zheng. Generalization bounds of sgld for non-convex learning: Two theoretical viewpoints. In Conference on Learning Theory, pages 605-638, 2018.
[48] L. Oneto, M. Donini, M. Pontil, and J. Shawe-Taylor Randomized learning and generalization of fair and private classifiers: From pac-bayes to stability and differential privacy. Neurocompating,
4 416:231-243, 2020.
[49] Orabona. A modern introduction to online learning, arXiv preprint arXiv: 19t.:19922.12133.. 2019.
12

---

[50] G. Papa, S. Clémençon, and A. Bellet. SGD algorithms based on incomplete U-statistics: large-scale minimization of empirical risk. In Neural Information Processing Systems, pages 1027-1035, 2015.
[51] V. Patel, B. Tian, and S. Zhang. Global convergence and stability of stochastic gradient descent. arXiv preprint arXiv:2110.01663 2021.
[52] A. Rakhlin, S. Mukherjee, and T. Poggio. Stability results in learning theory. Analysis and
Applications. 3(04):397-417, 2005.
[53] N. L. Roux, M. Schmidt, and F. Bach. A stochastic gradient method with exponential convergence rate for finite training sets. In Advances in Neural Information Processing Systems, pages 2663-2671, 2012.
[54] S. Shalev-Shwartz, O. Shamir, N. Srebro, and K. Sridharan. Learnability, stability and uniform convergence. Journal of Machine Learning Research, 11:2635-2670, 2010.
[55] W. Shen, Z. Yang. Y. Ying, and X. Yuan. Stability and optimization error of stochastic gradient descent for pairwise learning. Analysis and Applications, pages 1-41, 2019.
[56] N. Srebro, K. Sridharan, and A. Tewari. Smoothness, low noise and fast rates. In Advances in Neural Information Processing Systems, pages 2199-2207, 2010.
[57] B. Wang, H. Zhang, P. Liu, Z. Shen, and J. Pineau. Multitask metric learning Theory and algorithm. In International Conference on Artificial Intelligence and Statistics, pages 3362-
3371, 2019.
[58] Y. Wang, Khardon, D. Pechyony, and R. Jones. Generalization bounds for online learning algorithms with pairwise loss functions. In Conference on Learning Theory, volume 23, pages
13-1, 2012.
[59] 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 PMLR, 2021.
[60] H.-J. Ye, D.-C. Zhan, and Y. Jiang. Fast generalization rates for distance metric learning. Machine Learning, 108(2):267-2955 2019.
[61] Y. Ying and C. Campbell. Rademacher chaos complexities for learning the kernel problem. Neural computation, (2(11):2858 2886, 2010.
[62] Y. Ying and D.-X. Zhou, Online regularized classification algorithms. IEEE Transactions on Information Theory, 52(1 1):4755-4788, 2006.
[63] Y. Ying. L. Wen, and Lyu. Stochastic online AUC maximization. In Advances in Neural
Information Processing Systems, pages 451-459, 2016.
[64] L. Zhang, T. Yang, and R. Jin. Empirical risk minimization for stochastic convex optimization: O(1/n) ([adn) D(1/n2) )-tpe of risk bounds. In Conference on Learning Theory, pages 1954- 1979, 2017.
[65] T. Zhang. Solving large scale linear prediction problems using stochastic gradient descent algorithms. International Conference on Machine Learning, pages 919-926, 2004.
[66] Zhao, S. C. Hoi, R. Jin, and T. Yang. Online AUC maximization. In International Conference on Machine Learning, pages 233 24-2 2011.
[67] Y. Zhou, Y. Liang, and H. Zhang. Generalization error bounds with probabilistic guarantee for SGD in nonconvex optimization. arXiv preprini arXiv: (XXiv:/802 1802.06923 2018.
[68] Y. Zhou, B. Karimi, J. Yu, Z. Xu, and P. Li. Towards better generalization of adaptive gradient methods. Advances in Neural Information Processing Systems, 33, 2020.
13


Reviews:
[{"review_id": "q2WlR8B_TCr", "reviewer": "Reviewer_NxFE", "summary": "The paper analyzes the generalization ability of SGD for pairwise learning problems. The authors prove better generalization error bounds incorporating some variance term or the optimal error. They also provide a new SGD with O(n) computation per trial whose generalization bound is state-of-the-art. Furthermore, they show results for strongly convex losses and non-convex losses. \n", "questions": "", "limitations": "", "rating": 7, "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 writing of the paper is excellent in general. In particular, every theorem comes with a remark, which is helpful to understand the technical improvement to related work.\nThe paper is technically solid. \n\nMy concern is about concrete examples of loss functions and motivating problems. For example, AUC maximization is closely related to the paper. However, generalization error of AUC would involve conditional distributions on positive and negative instances and the generalization error defined in this paper seems not appropriate to the AUC problem. Then I wonder what concrete problems are subjects of the formulation of the paper.  \n\nCorollary 5 (b) assumes that F(w^*) is O(1/n), but this assumption seems not natural since F(w^*) is independent of the sample size and does not decrease when sample size n increases. So I feel that statement (b) is not meaningful. Furthermore, in Remark 3, the authors insist on the advantage of Theorem 4 to previous work [37][53] based on the corollary. I feel the statement is not fair as it is based on a weird assumption and should be removed.\n\nThe technical results of Theorem 8 (improving n^2 to n in computation time per trial) and Corollary 13 (extension of the previous approach to pairwise non-convex learning) are non-trivial and impressive. In particular, Coro. 13 needs to overcome the difficulty caused by dependent pairs in the analysis. \n\nOverall, my impression of the paper is rather positive and the paper is better evaluated if my concerns raised above are resolved.\n\nMinor Comments:\nLine 145: Does the expectation is also taken w.r.t. the randomized algorithm A?\n\n\nAfter reading other reviews and author responses, I raised my score a bit since the raised issues are resolved.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "N/A", "review_text": "", "extra_scores": {"ethical_concerns": "N/A", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3 hours"}, "extra_text": {}}, {"review_id": "iJsZxln1J7p", "reviewer": "Reviewer_xcch", "summary": "The paper seeks to develop new generalization and excess risk bounds for pairwise learning using SGD. The goal is to achieve error rates with near-optimal dependence in the number of gradient evaluations. To this end, stability properties of SGD are analysed and used to obtain the generalization/excess risk bounds. ", "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": "When it comes to deriving generalization and excess-risk bounds, the authors argue that pairwise learning is more difficult than point-wise learning due to the non-i.i.d. nature of the training examples of the former. This then motivates the approach taken by the authors, which involves studying the stability properties of SGD and applying some decoupling tricks (to overcome issues that come with the non-i.i.d. nature of the problem).\n\nIt seems to me that the authors have missed some highly relevant work in point-wise learning that should lead to optimal excess-risk rates (both in expectation and high probability) when applied to pair-wise learning. In fact, modern online-to-batch-conversion techniques---see e.g. Theorem 1 in http://proceedings.mlr.press/v97/cutkosky19a.html---reduce the problem of deriving excess risk bounds to that of getting regret bounds in an online learning setting. The data need not be i.i.d., and so this is applicable to pair-wise learning. Furthermore, SGD is essentially just OGD in the online learning setting, for which regret bounds are well studied for non-smooth/smooth and convex/strongly convex cases. Therefore, applying Theorem 1 in http://proceedings.mlr.press/v97/cutkosky19a.htm to the setting of pair-wise learning, and plugging in the regret bound of OGD, should recover, or even improve the excess-risk result of the current paper. \n\nThe current paper might still have some novel contributions when it comes to generalization bound (not excess-risk bounds) since I do not really know how these can be obtained using the online learning framework.\n\nThe paper is a little dense and still contains many inconsistencies and typos. I now mention some of them:\n- It seems that the authors talk about generalization bounds when they mean excess-risk bound (see e.g. Theorem 7). Please fix this.\n- The use of 'linear time' is not correct. A linear time rate in n is something line exp(-O(n)).\n- Lines 102-104, you mention a randomized algorithm A, but you are not taking the expectation when you write F(A(S))\n- In thm1, it should be F(A(S)) and not F(S)\n- In thm3, mention that A is given a training dataset of size n\n- The statement of Thm 4 is a little strange. How do you define a w that is independent of the algorithm A yet dependent on S? Furthermore, to call the result of Thm 4 a generalization bound, you technically need w = A(S). But the current theorem statement does not allow this.\n- Another instance of confusing the concepts of generalization and excess-risk is in Remark 3: you start talking about generalization, then switch to talking about F(w_\\star)\n- In lines 246-247: the claim that a log n^2/\\sqrt{n} bound has not been derived before for point-wise learning needs more explanation. Can you point to the best-known rate for this case?\n- In Thm 9, what is w_s^*? Define it explicitly.\n- Missing bracket in F_S(A(S) in thm 10.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "No negative social impact", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3 hours"}, "extra_text": {}}, {"review_id": "EmA7Dmu2lTt", "reviewer": "Reviewer_mXiM", "summary": "The paper proposes generalization for pairwise learning, based on assumptions of algorithmic stability.\nIt shows different bounds that depend on assumptions on the smoothness of the pairwise function.", "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": "I did not delve into the math in detail.\nI think the most interesting part of the publication is how they can propose stronger assumptions to derive bounds in $O(n^{-1})$ for the SGD algorithm, without any noise assumption on the data distribution (as do generalization results in $O(n^{-1})$ for U-statistics do, see [13]), but only using assumptions on the pairwise function $f$. You say you incorporate the variance in the analysis to derive faster bounds, which is exactly the purpose of the Mammen-Tsybakov (sometimes known as Bernstein) conditions for instance based (not pairwise) learning use in generalization bounds. [13] shows that we can bound the variance at a lower cost when dealing with U-statistics, as the analysis relies on the second Hoeffding decomposition (writing a U-statistic as an standard empirical process and a degenerate U-statistic) and the Hajek projection used to obtain the standard empirical process is a variance-reducing transformation of the original U-statistic. Your results propose fast bounds that are derived from the shape of the function $f$ rather than by an assumption the data, which is novel in my opinion (I looked at [37] and they seem to only propose $O(n^{-1/2})$ and in my opinion is a good result to extend with your SGD analysis.\nI think the paper seeks to cover too much ground for the format of the conference, which obscures the message, and should recenter the paper on one meaningful message.\n\nAlso, ref [a1] below is proposing guarantees for SGD for the minimization of U-statistics (pairwise functions), which is exactly what you are doing. Their analysis assumes only convexity (l. 41-42) and a VC-assumption. I believe that your contributions should be compared to theirs.\n\n[a1] SGD Algorithms based on Incomplete U -statistics: Large-Scale Minimization of Empirical Risk, Papa et al, NeurIPS 2015\n\n----- AFTER READING THE REVIEWS AND REBUTTAL\n\nI thank the authors for a serious response to the concerns of the reviewers.\nI am very familiar with uniform convergence generalization bounds but not that familiar with algorithmic stability.\nWhile my reject rating was motivated by the fact that the paper overlaps with existing work, the authors have successfully underlined the differences between their work and [a1]. For these reasons, I raised my rating to weak reject, as I would accept the paper if its results were put in perspective with already existing pairwise generalization bounds. I did not raise it further as integrating them is a significant undertaking.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Nothing to declare", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper makes a good contribution to pairwise learning problems by providing better generalization error bounds for stochastic gradient descent (SGD) applied to these problems, and providing analysis for both convex and non-convex problems.
Decision: Accept (Poster)