Generalization Guarantee of SGD for Pairwise Learning
Year: 2022

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 excess risk bounds with O(n) 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 a 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 to pairwise learning with gradient-dominated problems.

heading: 1 Introduction
text: 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 [1, 13] and learning with minimum error entropy loss functions [29]. For example, in supervised metric learning we wish to find a 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 a 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 to its cheap computation complexity, simplicity and efficiency [7, 20, 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(n2) 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 on the generalization analysis of SGD for pointwise learning [9, 10, 28, 36, 39], there is much less work on SGD for pairwise learning. A notable difference between pairwise learning
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
and pointwise learning is that the objective function in pairwise learning involves O(n2) dependent terms, 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 a single example can change O(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-probability generalization bound for uniformly-stable algorithms, which incorporates the variance information to improve the learning performance. We apply this result to develop the first dimension-independent high-probability bound O(1/ √ n) (up to a log factor) for an algorithm with O(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/ √ n) and O(1/(nσ)) for convex and σ-strongly convex problems, respectively. Under an interpolation or a low noise assumption, we improve our excess risk bounds to O(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 a 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-probability generalization guarantees for general nonconvex pairwise learning. Under a gradient dominance assumption, our stability analysis gives dimension-independent bounds.
The paper is organized as follows. We survey the related work in Section 2 and give the problem formulation in Section 3. We study convex and nonconvex pairwise learning in Section 4 and Section 5, respectively. Conclusion is given in Section 6. In the appendix, we present all the proofs, specific examples of pairwise learning and preliminary experimental results.

heading: 2 Related Work
text: 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, 54]. The modern framework of stability analysis was established in a seminal paper [5], 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-independent generalization bounds for various domains including stochastic optimization [10, 28, 36, 47, 51], structured prediction [44], transfer learning [37] and differential privacy [3, 48]. Recent progress shows a tradeoff between optimization and stability [11, 55], and its applications to yield almost optimal high-probability generalization bounds [6, 22, 34].
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 numbers [17, 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 stability of ranking [1] and metric learning [31, 57] was studied for strongly convex objectives [30]. High-probability bounds of the order O( log n+ 1/ √ n) were recently developed for -uniformly stable pairwise learning algorithms [40]. A nice property of stability analysis is its ability to yield dimension-independent bounds, while a square-root dependency on the dimension is inevitable for uniform convergence analysis when considering general problems [21]. However, algorithmic stability generally requires a 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 [4, 12] 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, 50]. The work [50] considers a very general problem setting for SGD with K-sample U-statistic of degrees (d1, . . . , dK), which includes our algorithm as a special case with K = 1 and d1 = 2. It 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.

heading: 3 Problem Formulation

heading: 3.1 Pairwise Learning and Stochastic Gradient Descent
text: Let ρ be a probability measure defined on Z = X × Y with an input space X and an output space Y . Let S = {z1, . . . , zn} be drawn independently according to ρ, from which we aim to learn a prediction function h : X 7→ R or h : X × X 7→ R. We consider parametric models where the prediction function hw can be indexed by an element w ∈ W , where W is a d-dimensional Hilbert space. We consider pairwise learning problems where the performance of a model hw on an example pair (z, z′) 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 7→ Y to rank instances in a way consistent with the outputs, i.e., hw(x) < hw(x′) if y < y′ for two example pairs z = (x, y), z′ = (x′, y′). Then we can formulate ranking as a pairwise learning problem with f(w; z, z′) = ψ(sgn(y − y′)(hw(x)− hw(x′))), where sgn is the sign function and ψ can be either the hinge loss ψ(t) = max{1− t, 0} or the logistic loss ψ(t) = log(1 + exp(−t)). For supervised metric learning with Y = {−1,+1}, we find a 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 hw(x, x′) = 〈w, (x − x′)(x − x′)>〉, where w ∈ Rd×d is positive definite. We can formulate supervised metric learning as pairwise learning with f(w; z, z′) = ψ(τ(y, y′)(1− hw(x, x′))), where τ(y, y′) = 1 if y = y′ and −1 otherwise. The population risk of w in pairwise learning is F (w) = EZ,Z′ [f(w;Z,Z ′)], where EZ,Z′ denotes the expectation with respect to (w.r.t.) Z,Z ′ ∼ ρ. The empirical risk of w is
FS(w) = 1 n(n− 1) ∑
i,j∈[n]:i6=j
f(w; zi, zj),
where [n] := {1, . . . , n}. Let w∗S = arg minw∈W FS(w) and w∗ = arg minw∈W F (w). For a randomized algorithm A, we use A(S) 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 (A(S))− F (w∗) is to use the following error decomposition ES,A [ F (A(S))−F (w∗) ] = ES,A [ F (A(S))−FS(A(S)) ] +ES,A [ FS(A(S))−FS(w∗) ] , (3.1)
where the first term F (A(S)) − FS(A(S)) is called the generalization error and the second term FS(A(S))− FS(w∗) 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 1 (SGD for Pairwise Learning). Let w1 = 0 ∈ Rd and {ηt}t be a stepsize sequence. Let ∇f(wt; zit , zjt) denote the gradient of f w.r.t. the first argument. At the t-th iteration, we first draw {(it, jt)} from the uniform distribution over all pairs {(i, j) : i, j ∈ [n], i 6= j} and then update
wt+1 = wt − ηt∇f(wt; zit , zjt). (3.2)
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 ρ [15]. 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 O(n2) gradient computations per iteration). We describe SGD(S, T, f, {ηt}) in Algorithm 1 of SGD with dataset S, iteration number T , loss function f and stepsize {ηt}. Algorithm 1 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 or non-Lipschitz loss. Moreover, our analysis can clarify the effect of interpolation on generalization.
Algorithm 1: SGD(S, T, f, {ηt}) Input: initial point w1 = 0, learning rates {ηt}t, and dataset S = {z1, . . . , zn}
1 for t = 1, 2, . . . , T do 2 draw (it, jt) uniformly over all pairs {(i, j) : i, j ∈ [n], i 6= j} 3 update wt+1 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 b = supz,z′∈Z f(0; z, z
′) and b′ = supz,z′∈Z ‖∇f(0; z, z′)‖2. We denote B B̃ if there are absolute constants c1 and c2 such that c1B ≤ B̃ ≤ c2B. We collect the notations of this paper in Table A.1. Definition 2. Let g :W 7→ R, L,G > 0, σ ≥ 0.
1. We say g is L-smooth if ‖∇g(w)−∇g(w′)‖2 ≤ L‖w −w′‖2 for all w,w′ ∈ W .
2. We say g is G-Lipschitz continuous if |g(w)− g(w′)| ≤ G‖w −w′‖2 for all w,w′ ∈ W . 3. We say g is σ-strongly convex w.r.t. ‖·‖2 if g(w)− ( g(w′)+〈w−w′,∇g(w′)〉 ) ≥ σ‖w−w′‖22/2
for all w,w′ ∈ W . We say g is convex if g is σ-strongly convex with σ = 0. Assumption 1 (Convexity). Assume for all z, z′ ∈ Z , the function w 7→ f(w; z, z′) is convex. Assumption 2 (Boundedness of Gradients). Assume for all z, z′ and w ∈ W , ‖∇f(w; z, z′)‖2 ≤ G. Assumption 3 (Smoothness). Assume for all z, z′, w 7→f(w; z, z′) is nonnegative and L-smooth.

heading: 3.2 Algorithmic Stability and Generalization
text: 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 [5, 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 a similar concept in pointwise learning [39]. Let S = {z1, . . . , zn}, S′ = {z′1, . . . , z′n} be independently drawn from ρ. We denote
Si = { z1, . . . , zi−1, z ′ i, zi+1, . . . , zn } , ∀i ∈ [n], (3.3)
Si,j = { z1, . . . , zi−1, z ′ i, zi+1, . . . , zj−1, z ′ j , zj+1, . . . , zn } , ∀i < j ∈ [n]. (3.4)
Definition 3 (Algorithmic Stability). Let S = {z1, . . . , zn} and S′ = {z′1, . . . , z′n} be drawn independently from ρ. For any i, j ∈ [n], denote Si as (3.3) and Si,j as (3.4).
1. We say a deterministic algorithmA : Zn 7→ W is -uniformly stable if for any datasets S, S̃ ∈ Zn that differ by at most a single example we have supz,z̃∈Z ∣∣f(A(S); z, z̃)− f(A(S̃); z, z̃)∣∣ ≤ . 2. We say a randomized algorithm A is on-average (loss) -stable if
1 n(n− 1) ∑
i,j∈[n]:i 6=j
ES,S′,A [ f ( A(Si,j); zi, zj ) − f ( A(S); zi, zj )] ≤ .
3. We say A is on-average argument -stable if ES,S̃,A [ 1 n ∑n i=1 ‖A(S)−A(Si)‖22 ] ≤ 2.
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 [39]. The proof is given in Appendix B.
Theorem 1. (a) If A is on-average (loss) -stable, then E[F (A(S))− FS(A(S))] ≤ .
(b) If A is on-average argument -stable and Assumption 3 holds, then for any γ > 0 we have
E[F (A(S))− FS(A(S))] ≤ 2(L+ γ) 2 + Lγ−1E[FS(A(S))].
Remark 1. We can choose γ √ E[FS(A(S))]/ in Part (b) and get the bound E[F (A(S)) − FS(A(S))] = O( 2 + √ E[FS(A(S))]). Therefore, if E[FS(A(S))] is small, Part (b) can imply bounds better than O( ). In particular, if E[FS(A(S))] = O( 2) the bound in Part (b) becomes O( 2), which is much faster than O( ) in Part (a).
Theorem 2 establishes the connection between uniform stability and generalization with high probability for pairwise learning. The proof is given in Section C, whose novelty is to use decoupling techniques to address the coupling among O(n2) terms in the objective function of pairwise learning.
Theorem 2. Let A be an -uniformly stable and deterministic algorithm. Let B := supz,z′ ∣∣ES [f(A(S); z, z′)]−f(w∗; z, z′)∣∣ and σ20 := EZ,Z′,S[(f(A(S);Z,Z ′)−f(w∗;Z,Z ′))2]. For any δ ∈ (0, 1), the following inequality holds with probability at least 1− δ
F (A(S))−FS(A(S))−F (w∗)+FS(w∗)≤98 √ 2e log n log(2e/δ)+ 2B log(2/δ)
3bn/2c +
√ 2σ20 log(2/δ)
bn/2c .
Remark 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 2 was motivated by the recent work [34, 40]. For pointwise learning, high-probability generalization bounds of the order O( log n) were developed for -uniformly stable algorithms under a further Bernstein condition on the variance-expectation relationship [34]. High-probability bounds O( log n+ 1/ √ n) were also developed for -uniformly stable algorithms in pairwise learning [40]. We refine these results by developing generalization bounds O( log n+ √ σ20/n), where σ 2 0 is 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(S))− F (w∗)]/σ), and in this case the term √ σ20/n in our bound would be o(n − 12 ) instead of O(n− 1 2 ) in [40]. As we will show, Theorem 2 can imply almost optimal excess risk bounds for an algorithm with O(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− 1 4 ) [40].

heading: 4 Pairwise Learning with Convex Loss Functions
text: In this section, we study the generalization performance of SGD for pairwise learning with convex loss functions. We consider convex/strongly-convex and smooth/nonsmooth problems.

heading: 4.1 Convex and Smooth Problems
text: 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. A 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(wj) 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 is that a change of zi would influence 2(n− 1) pairs (zj , zi), (zi, zj) for j 6= i. We need to use the U-structure of the empirical risk to prove this result.
Theorem 3 (Stability bound). Let Assumptions 1, 3 hold. Let A be SGD (Algorithm 1) with ηj ≤ 2/L. Then A with t iterations is on-average argument -stable with 2 ≤ 16L(1+2t/n)e
n
∑t j=1 η 2 jE[FS(wj)].
Based on Theorem 3, we get error bounds for pairwise learning with convex and smooth functions. Theorem 4 (Excess risk bound). Let Assumptions 1, 3 hold. Let {wt} be the sequence produced by SGD (Algorithm 1) on a dataset of size n with ηt = η ≤ 2/L. Then for w̄T = 1T ∑T t=1 wt and any γ ≥ 1 we have the following inequality for all w independent of A (can depend on S)
E[F (w̄T )− FS(w)] = O (( η + 1
γ + γ(T + T 2/n)η2 n
) E[FS(w)] ) +O (E[‖w‖22] Tη + γη(1 + T/n)E[‖w‖22] n ) . (4.1)
A notable property of the above bound is that it holds for any w independent of A. If E[‖w∗S‖22] is finite, we can choose w = w∗S in Eq. (4.1) and get a bound involving E[FS(w∗S)]. Furthermore, if we are in an interpolation or overparameterized setting [45] then E[FS(w∗S)] = o(1/ √ n) and the generalization will improve according to (4.1). Therefore, our stability analysis provides an explanation on how interpolation/overparameterization can help in generalization. Note SGD has an implicit bias to choose a model with a small norm and therefore it is reasonable to assume E[‖w∗S‖22] <∞. We can also choose w = w∗ in Eq. (4.1) 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/ √ n) in the general case and improves it to O(1/n) if F (w∗) = O(1/n). Note here we use the assumption F (w∗) = O(1/n) just to 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 4 hold.
(a) We can choose ηt = η 1/ √ T and T n to get E[F (w̄T )]− F (w∗) = O(1/ √ n).
(b) If F (w∗) = O(1/n), choosing ηt = η ≤ 2/L and T n yields E[F (w̄T )]−F (w∗) = O(1/n). Remark 3. Stability and excess risk bounds of the order O(1/ √ n) 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 a comparison, we remove the Lipschitz continuity assumption. Furthermore, their discussion can only imply non-optimistic bounds of the order O(1/ √ n). As a comparison, our discussions can fully exploit the property of F (w∗) to imply fast bounds O(1/n).

heading: 4.2 Convex and Nonsmooth Problems
text: 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 in Theorem 7. The proofs of results in this subsection are given in Section F. Theorem 6 (Stability bounds). Let Assumptions 1, 2 hold. Let S = {z1, . . . , zn} and S′ = {z′1, . . . , z′n} be two datasets that differ by a single point. Let {wt}, {w′t} be the sequence produced by SGD (Algorithm 1) w.r.t. S and S′ with ηt = η, respectively. Then
E [ ‖wt+1 −w′t+1‖22 ] ≤ 4G2et ( 1 + 4t/n2 ) η2. (4.2)
For any δ ∈ (0, 1) with probability at least 1− δ we have ‖wt+1 −w′t+1‖22 ≤ 4G2η2e ( t+ ( 2t/n+ log(1/δ) + √ 4tn−1 log(1/δ) )2) .
Theorem 7 (Excess risk bounds). Let Assumptions 1, 2 hold. Let {wt} be the sequence produced by SGD with ηt = η T− 3 4 . If T n2, then E[F (w̄T )]− F (w∗) = O(n− 1 2 ).
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.2). Therefore, one needs to choose very small stepsizes to let the right-hand side of (4.2) vanish to 0. Indeed, Theorem 7 suggests ηt T− 3 4 , which are much smaller than the ηt T− 1 2 in the smooth case. As a result, we
require to run SGD with T n2 to get the optimal excess risk bounds O(1/ √ n). Note we also give high-probability bounds on the argument stability in Theorem 6. It should be mentioned that the stability of a variant of SGD as wt+1 = wt − ηtt−1 ∑t−1 k=1∇f(wt; zit , zik) 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 w0 = 0, parameter γ > 0, k = d 12 log2 ne
1 for i = 1, 2, . . . , k do 2 set Ti ni = d n2i e, γi = γ 2i , ηt = γini t+1 , t ∈ N,f̃(w; z, z ′)=f(w; z, z′) + 1γini ‖w−wi−1‖ 2 2 3 draw a sample Si of size ni independently from ρ 4 apply SGD(Si, Ti, f̃ , {ηt}) to minimize the following problem and get wi
F̃Si(w) := 1 ni(ni − 1) ∑
z,z′∈Si:z 6=z′ f(w; z, z′) +
1
γini ‖w −wi−1‖22. (4.3)
5 end
Note SGD requires the undesirable O(n2) gradient computations to achieve the bound O(1/ √ n) for nonsmooth problems. The following theorem shows one can also achieve the bound O(1/ √ n) with O(n) gradient computations by considering Algorithm 2. Algorithm 2 is motivated from the iterative localization approach established in pointwise learning [23], which was also used to develop efficient differentially private algorithms [2, 35]. Note the choice γ n− 12 ‖w∗‖2 depends on the unknown ‖w∗‖2. However, one can get the bound O(D/ √ n) by choosing γ D/ √ n if ‖w∗‖2 ≤ D.
Theorem 8. Let Assumptions 1, 2 hold and δ ∈ (0, 1). Let wk be produced by Algorithm 2 and assume supz,z′ |E[f(wi, z, z′)]| ≤ B for some B > 0. If we choose γ n− 1 2 ‖w∗‖2, then with probability at least 1−δ we have F (wk)−F (w∗) = O(log(log n/δ)(log n)‖w∗‖2/ √ n). Moreover, Algorithm 2 requires only O(n) gradient computations to achieve this excess risk bound.
Remark 5. Iterative localization approach was developed in [23, 35] to develop novel algorithms withO(n) gradient computations andO(1/ √ n) excess risk bounds for nonsmooth pointwise learning problems. We extend this technique to the pairwise learning setting. Furthermore, the excess risk bounds in [23, 35] are stated in expectation. As a comparison, we use the novel high-probability bounds for uniformly stable algorithms established in Theorem 2 to develop high-probability bounds of the order (log2 n)/ √ n, which has not been developed even for pointwise learning (the best high-probability excess risk bound for SGD with nonsmooth loss functions requires O(n2) gradient computations [3]). Note that the sample size nk √ n in the k-th epoch, and therefore the highprobability bounds in [40] can only yield bounds O(n− 1 2
k ) = O(n − 14 ) for Algorithm 2. As a
comparison, Theorem 2 applied to the ERM of F̃Sk yields the bounds O(n −1 k + γk) = O(n − 12 ) (ERM of F̃Sk is γk-uniformly stable and the last term of the bound in Theorem 2 is dominated). This demonstrates the advantage of our new high-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 k = d 12 log2 ne instead of k
′ = dlog2 ne epochs in [23, 35]. The underlying reason is that the high-probability bounds for ERM of F̃Sk involve n −1 k + γ −1 k , while the bounds in expectation only involve γ−1k [40]. Since nk′ 1, our high-probability analysis only implies vacuous bounds O(1) if we use k′ = dlog2 ne epochs.

heading: 4.3 Strongly Convex Problems
text: We now turn to strongly convex cases. Theorem 9 gives bounds for smooth problems, while Theorem 10 gives excess risk bounds for nonsmooth problems. Note Theorems 9 and 10 apply to any algorithm, which give a 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.
Theorem 9 (Strongly Convex and Smooth Problems). Let Assumption 3 hold. Assume for all S ∈ Zn, FS is σ-strongly convex w.r.t. ‖ · ‖2. Let A be a randomized algorithm and σn ≥ 8L. Then
E[F (A(S))]− F (w∗) ≤ 128L ( 16L n2σ2 + 1 nσ ) E [ FS(w ∗ S) ] + 2L σ E [ FS(A(S))− FS(w∗S) ] .
Remark 6. The above bound involves two components. The first component O(1/(nσ)) depends only on the landscape of the learning problem. The second component involves optimization errors. It shows that optimization is always beneficial to improve generalization for strongly convex problems. Furthermore, it also shows that one can stop the algorithm once we achieve the optimization error boundsO(1/n) since further optimization would not improve essentially the generalization. Theorem 9 also implies bounds of the order o(1/(nσ)) if FS(w∗) is small.
Theorem 10 (Strongly Convex and Nonsmooth Problems). Assume f takes a structure as f(w; z, z′) = `(w; z, z′) + r(w). Assume for all z, z′, the map w 7→ `(w; z, z′) is G-Lipschitz. Assume for all S ∈ Zn, FS is σ-strongly convex w.r.t. ‖ · ‖2. For any algorithm A we have
E[F (A(S))]− F (w∗) ≤ 8G 2
nσ +G
√ 2E [ FS(A(S))− FS(w∗S) ] σ .
We present the specific applications of the above results to SGD in Corollary G.2 (Section G).

heading: 5 Pairwise Learning with Nonconvex Loss Functions
text: In this section, we consider excess risk bounds for pairwise learning in a nonconvex setting. In this case, the excess population risk is 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 [26, 68]. In a general nonconvex setting, SGD requires to choose ηt = O(1/t) for a meaningful stability bound [28], for which the optimization errors would decay logarithmically w.r.t the number of iterations [26]. Then, stability analysis fails to trade-off the stability and optimization for a model with good generalization performance in a general nonconvex problem. Therefore, we turn to a different uniform convergence approach in a general nonconvex setting [38]. After that, we study stability of SGD for nonconvex problems under a further PL condition.

heading: 5.1 Uniform Convergence of Gradients for Pairwise Learning
text: 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. LetWR = {w ∈ W : ‖w‖2 ≤ R} for R > 0. The proofs of results in this subsection are given in Section H.
Definition 4. Let F := {f : Z4 7→ R} be a function class and S = {zi}ni=1 ⊂ Z . Let { i} bn2 c i=1 be independent Rademacher variables with Pr{ i = 1} = Pr{ i = −1} = 1/2. The empirical Rademacher chaos complexity for F w.r.t. S is defined as
US(F) = 1 bn2 c E [ sup f∈F ∑ 1≤i<j≤bn2 c i jf(zi, zi+bn2 c, zj , zj+b n 2 c) ] .
Theorem 11 (Uniform Convergence of Gradients). Let δ ∈ (0, 1), R > 0 and S = {z1, . . . , zn} be drawn independently from ρ. If Assumption 3 holds, then with probability at least 1− δ we have
sup w∈WR
∥∥∇F (w)−∇FS(w)∥∥2 ≤ 2 √
2(LR+ b′) ( 2 + √ log(1/δ) ) √ n + 4 √ US(FR) n ,
where FR = { (z1, z2, z3, z4) 7→ 〈∇f(w; z1, z2),∇f(w; z3, z4)〉 : w ∈ 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 spaceW .
Corollary 12. Under Assumptions of Theorem 11, with probability at least 1− δ we have
sup w∈WR
∥∥∇F (w)−∇FS(w)∥∥2 ≤ 2 √ 2(LR+ b′)√ n ( 2+ √ 96e ( log 2 + d log(3e) ) + √ log(1/δ) ) .
The above uniform convergence rate involves a square-root dependency on d. We show that this dependency can be avoided if we consider a special class of functions with a specific structure
f(w; z, z′) = ψ(〈w, φ(x, x′)〉, τ(y, y′)), (5.1) where φ : X × X 7→ W is a feature map, ψ : R× R 7→ R is Lψ-smooth w.r.t. the first argument and τ : Y × Y 7→ R. Loss functions of the structure (5.1) have wide applications in robust optimization and generalized linear models [24, 46]. We assume κ = supx,x′∈X ‖φ(x, x′)‖2. Corollary 13. Let δ ∈ (0, 1), R > 0 and S = {z1, . . . , zn} be examples drawn independently from ρ. Suppose f :W ×Z2 7→ R takes the form (5.1) with ψ being Lψ-smooth w.r.t. the first argument. Then the following inequality holds with probability at least 1− δ
sup w∈WR
∥∥∇F (w)−∇FS(w)∥∥2 ≤ 4κ ( 2LψRκ+ b ′) √ n + √ 8 ( Lψκ2R+ b′ )2 log(1/δ) n .
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− 1) terms in ∇FS(w) are correlated, which introduces difficulties in applying concentration inequalities. We need to apply decoupling techniques in U-process to handle this correlation.

heading: 5.2 Smooth Problems
text: We now study the generalization performance of SGD for pairwise learning based on the uniform convergence of gradients developed in the previous subsection. We first introduce necessary assumptions. Since ηt is always small (a typical choice is ηt 1/ √ T ), Eq. (5.2) is milder than a bounded gradient assumption. Eq. (5.3) imposes a bounded variance assumption on stochastic gradients, which is a standard assumption for the analysis of SGD [26, 36, 67]. Assumption 4. Assume the existence of G > 0 and σ1 > 0 such that
√ ηt‖∇f(wt; z, z′)‖2 ≤ G,∀t ∈ N, z, z′ ∈ Z, (5.2) Eit,jt [ ‖∇f(wt; zit , zjt)−∇FS(wt)‖22 ] ≤ σ21 , ∀t ∈ N. (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 (wt)‖22 ≤ 2‖∇F (wt)−∇FS(wt)‖22 + 2‖∇FS(wt)‖22. 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 11. The second term is the optimization error and can be addressed by techniques in optimization theory. The proof is given in Section I. Theorem 14 (Smooth Problems). Let Assumptions 3 and 4 hold. Let {wt}t be the sequence produced by (3.2) with ηt = η/ √ T and η ≤ √ T/(2L). Then for any δ ∈ (0, 1), we can choose T nd−1 to derive the following inequality with probability at least 1− δ
1
T T∑ t=1 ‖∇F (wt)‖22 = O ( n− 1 2 log2(1/δ) ( d+ log(1/δ) ) 1 2 ) . (5.4)
Furthermore, if f takes the specific structure (5.1) we can choose T n to derive the following inequality with probability at least 1− δ
1
T T∑ t=1 ‖∇F (wt)‖22 = O ( n− 1 2 log 5 2 (1/δ) ) . (5.5)
Remark 8. It is clear that the bound in (5.4) is dimension-dependent, 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 errors of SGD with T iterations for nonconvex problems satisfy 1T ∑T t=1 ‖∇FS(wt)‖22 = O(T− 1 2 ) [26]. This is consistent with the
error bounds 1T ∑T t=1 ‖∇F (wt)‖22 = O ( n− 1 2 log 5 2 (1/δ) ) in (5.5) by noting T n. Therefore, our analysis shows that the extension from optimization to generalization comes for free.

heading: 5.3 Gradient Dominated Problems
text: We now study the stability and generalization of SGD for pairwise learning with gradient-dominated objectives (or PL condition). PL condition is widely used in 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.
Assumption 5 (Polyak-Lojasiewicz Condition). Denote F̂S = infw′∈W FS(w′). We assume FS satisfies PL or gradient-dominated condition (in expectation) with parameter β > 0, i.e.,
ES [ FS(w)− F̂S ] ≤ 1 2β ES [ ‖∇FS(w)‖22 ] , ∀w ∈ W. (5.6)
Under the PL condition, we can get excess population risk bounds based on the stability analysis. The proof of Theorem 15 is given in Section J.
Theorem 15 (Gradient Dominated Problems). Let Assumptions 2, 3, 5 hold. Assume |f(w; z, z′)| ≤ B for all w ∈ W, z, z′ ∈ Z . Let {wt}t be the sequence produced by (3.2) with ηt = 2t+12β(t+1)2 . Then
E [ F (wT ) ] − F (w∗) = O (T LL+β n ) +O ( 1/(Tβ2) ) . (5.7)
We can choose T n 1+L/β 1+2L/β β− 2+2L/β 1+2L/β to get E [ F (wT ) ] − F (w∗) = O ( n− 1+L/β 1+2L/β β− 2L/β 1+2L/β ) .
Remark 9. Note the above bounds depend on the condition number cond := L/β. If cond ≈ 1, then we get E [ F (wT ) ] − F (w∗) ≈ O ( n− 2 3 ) . As cond increases, the bound increases to O(n− 1 2 ).

heading: 6 Conclusion
text: In this paper, we present a systematic study on the generalization performance for pairwise learning. We develop novel high-probability bounds for uniformly stable algorithms, and apply them to develop algorithms with optimal bounds with O(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 O(1/ √ n) for convex problems and O(1/(nσ)) for σ-strongly convex problems, respectively. We conduct the uniform convergence analysis for general nonconvex problems, which imply the bounds of the orderO(1/ √ n) 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 a general nonconvex case for getting dimensionindependent bounds. It would also be very interesting to study other stochastic optimization methods for pairwise learning, including variance reduction variants and momentum technique.

heading: Acknowledgments
text: We are also grateful to the anonymous reviewers and area chairs for their insightful and constructive comments. Yiming’s work is supported by National Science Foundation (NSF) under grants DMS2110836, IIS-1816227, IIS-2110546, IIS-2103450.

Review summaries:
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. 

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.