Generalization Bounds for Regularized Pairwise Learning

1 Introduction

Recently, there is a growing interest in studying a large family of machine learning problems called pairwise learning problems. Unlike traditional learning problems whose loss functions depend only on a single example (e.g., classification and regression), pairwise learning refers to learning tasks for which the associated loss function involves a pair of examples. Specifically, for any two examples (x, y), (˜x, ˜ y) ∈ Rd ×R, the loss function for pairwise learning often takes the form V (h, (x, y), (˜x, ˜ y)) for a hypothesis function h : Rd × Rd → R. Many learning tasks can be cast into the framework of pairwise learning, including ranking [Rejchel, 2012; Kriukova et al., 2016], metric learning [Xing et al., 2003; Cao et al., 2016], AUC maximization [Cortes and Mohri, 2004; Gao and Zhou, 2015; Gao et al., 2013; Zhao et al., 2011], gradient learning [Mukherjee and Zhou, 2006] and learning under minimum error entropy criterion [Hu et al., 2015], etc. For example, supervised metric learning aims to find a Mahalanobis metric dw(x, ˜x) = (x - ˜x)⊤w(x - ˜x) encoded by a semi-positive matrix w ∈ Sd×d to bring examples with similar labels together while keeping examples with different labels apart [Xing et al., 2003], where Sd×d is the class of all positive semi-definite matrices in Rd×d . In this case, a common loss function V (dw, (x, y), (˜x, ˜ y)) = g(y ˜ y(1 - dw(x, ˜x))) involves two examples (x, y), (˜x, ˜ y), where g : R → R+ is convex for which a typical choice is the hinge loss g(t) = max(1 - t, 0) [Cao et al., 2016].

Motivated by growing interests in pairwise learning, generalization analysis of different pairwise learning machines has been conducted to better understand their practical behavior [Kar et al., 2013; Ying and Zhou, 2016; Christmann and Zhou, 2016; Cl´emenc¸on et al., 2008; Rejchel, 2012]. A difficulty in learning theory analysis of pairwise learning consists in the fact that the empirical error can not be written as a summation of independent and identically distributed (i.i.d.) random variables, rendering standard techniques in the i.i.d. case not applicable in this context [Sridharan et al., 2009; Bartlett et al., 2005]. For these learning problems with coupled examples, existing studies use either techniques in U-process to derive uniform convergence bounds [Rejchel, 2012; Cl´emenc¸on et al., 2008; Cao et al., 2016; Zhao et al., 2017; Lei and Ying, 2016] or algorithm stability/robustness to establish algorithm-specific bounds [Bellet and Habrard, 2015; Jin et al., 2009; Agarwal and Niyogi, 2009]. However, existing studies on pairwise learning problems are not quite satisfactory in the following three aspects. Firstly, these generalization bounds are mostly derived for different specific instantiations of pairwise learning problems, and a unified framework to study generalization errors for regularized pairwise learning is still lacking. Secondly, most of these discussions only consider estimation errors. Thirdly, these estimation error bounds either are slow [Jin et al., 2009; Bellet and Habrard, 2015; Agarwal and Niyogi, 2009; Cao et al., 2016] or require capacity assumptions on hypothesis spaces and Bernstein conditions for an application of Talagrand's inequality [Rejchel, 2012; Cl´emenc¸on et al., 2008].

In this paper, we provide a unified analysis for regularized pairwise learning by showing that the regularized generalization error of the estimator would converge to the optimal value at a rate of the order O(1/n), where n is the number of training examples. Our discussion requires neither Bernstein conditions on the bias and variance nor capacity assumptions on the hypothesis spaces. The property that the empirical error is a U-statistic makes the argument in the i.i.d. case not applicable to our context, and we bypass this obstacle by resorting to established techniques in the U-process. Based on this, we develop generalization error bounds for regularized pairwise learning which also take approximation errors into consideration. We apply our general results to metric learning and ranking, for each of which our general analysis can imply generalization bounds tighter than the state of the art.

2 RelatedWork

Here, we review related work on generalization analysis of pairwise learning algorithms based on different approaches.

Generalization error bounds were established for regularized metric learning [Jin et al., 2009] and ranking [Agarwal and Niyogi, 2009] based on algorithmic stability. The basic idea is to use strong convexity of the objective function in regularized pairwise learning problems to show that the learned model would change slightly if a single training example is replaced by another one. Based on this, McDiarmid's inequality is applied to establish generalization bounds. However, this approach can only yield a suboptimal estimation bound O(1/(λ√n)), where λ is the regularization parameter.

The tool of U-process was also used in generalization analysis of regularized metric learning [Cao et al., 2016] and ranking [Cl´emenc¸on et al., 2008; Rejchel, 2012]. The basic idea is to use symmetry of U-statistics to control supremum of a U-process in generalization analysis by the supremum of a Rademacher process, the latter of which can be bounded by standard techniques in the i.i.d. setting. However, existing studies with this approach either imply a suboptimal estimation bound O(1/(√λn)) or require both Bernstein conditions and capacity assumptions for a fast learning rate.

Integral operator was used to establish learning rates for regularized least squares ranking [Zhao et al., 2017]. The basic idea is to show that the involved optimization problem has a closed-form solution in terms of integral operators, which, however, applies only to the least squares loss.

Recently, regret bounds for online pairwise learning algorithms were established based on online-to-batch conversion together with covering numbers [Wang et al., 2012] and Rademacher complexities [Kar et al., 2013]. The convergence rates of the last iterate for online pairwise learning algorithms were studied based on convex analysis [Ying and Zhou, 2016; Guo et al., 2016; Lin et al., 2017], which, however, as we will show below, are suboptimal.

3 Problem Setup andMain Results

3.1 Regularized Pairwise Learning

Let ρ be a probability measure defined over the sample space Z = X × Y ⊂ Rd × R, where X and Y are the input and output space, respectively. Let z = {zi = (xi, yi)}ni=1 be a sequence of examples independently drawn from ρ. Let W be a Hilbert space with the associated inner product 〈·, ·〉 and ‖ · ‖, ||| · ||| be two norms defined in W. Let φ : X ×X → W be a feature map and τ : Y × Y → R. The definition of τ(y, ˜ y) depends on the specific application domain (See Examples 1, 2 below). From the feature map φ, one can define a Mercer kernel K : (X × X) × (X × X) → R satisfying K((x1, ˜x1), (x2, ˜x2)) = 〈φ(x1, ˜x1), φ(x2, ˜x2)〉 for the reproducing Kernel Hilbert space W [Cl´emenc¸on et al., 2008; Rejchel, 2012]. For any two examples z = (x, y), ˜ z = (˜x, ˜ y) and a prediction rule h : X × X → R, we use the loss function of the form V (h, z, ˜ z) = ℓ(τ(y, ˜ y), h(x, ˜x)) to measure the quality of h on z and ˜ z, where ℓ : R×R→R+ is convex with respect to (w.r.t.) the second argument. We assume V is symmetric in the sense that V (h, z, ˜ z) = V (h, ˜ z, z). The generalization error of any h : X × X → R is defined as E(h) := Ez,˜ z[V (h, z, ˜ z)], where Ez,˜ z denotes the conditional expectation w.r.t. z and ˜ z. We omit the subscript z, ˜ z if the expectation is taken over all random variables. We consider prediction rules of the form hw(x, ˜x) := 〈w, φ(x, ˜x)〉,w ∈ W, and we search the estimator wz,λ by minimizing the empirical error plus a regularization term to avoid overfitting

where λ > 0 is a regularization parameter and we use the notation Nn = {1, . . . , n}. The regularized generalization error of the prediction rule hw is defined as

We denote by wλ the model minimizing Fλ(w) over W and by hρ the model minimizing the generalization error over measurable functions defined on X × X , respectively

The framework of pairwise learning covers many machine learning problems as specific examples. Here we clarify how the distance metric learning and ranking can be recovered with specific instantiations of ℓ, φ and τ. We denote (t)+ := max(t, 0) and x⊤ the transpose of x ∈ Rd .

Example 1 (Supervised metric learning). Assume Y = {±1}. Supervised metric learning aims to find a Mahalanobis metric dw(xi, xj) = 〈w, (xi - xj)(xi - xj)⊤〉,w ∈ Sd×d such that two examples with the same label are close to each other, while two examples with different labels are apart from each other. A common loss function used in metric learning takes the form Vm(dw, z, ˜ z) = g(y˜ y(1 - dw(x, ˜x))) [Jin et al., 2009], where g : R → R+ is a convex function for which a typical choice is g(t) = (1 - t)+. This scheme falls into the pairwise learning framework if we define τ(y, ˜ y) = y˜ y, φ(x, ˜x) = (x - ˜x)(x - ˜x)⊤, ℓ(a, b) = g(a(1 - b)) and hw(x, ˜x) = 〈w, φ(x, ˜x)〉,w ∈ Sd×d . That is, we have Vm(dw, z, ˜ z) = ℓ(τ(y, ˜ y), 〈w, φ(x, ˜x)〉).

Example 2 (Ranking). In ranking problems, we use the output yi to indicate the ordering between instances, i.e., the instance xi is considered to be better than xj if yi > yj. The task is to predict the ordering between the objects based on observations by constructing ranking rules h : X × X → R, and predict y > ˜ y if h(x, ˜x) > 0 [Rejchel, 2012; Cl´emenc¸on et al., 2008]. A common pairwise loss function used in ranking problems takes the form Vr(h, z, ˜ z) = g(sign(y - ˜ y)h(x, ˜x)), where g : R → R+ is a convex function which can be either the exponential cost function g(t) = e-t , the "logit" function g(t) = log(1 + e-t ) or the "hinge loss" g(t) = (1 - t)+ [Cl´emenc¸on et al., 2008]. Here sign(t) denotes the sign of t ∈ R. The above formulation of ranking problems falls into our framework of pairwise learning by taking τ(y, ˜ y) = sign(y - ˜ y), ℓ(a, b) = g(ab) and ranking rules of the form hw(x, ˜x) = 〈w, φ(x, ˜x)〉, w ∈ W. That is, we have Vr(hw, z, ˜ z) = ℓ(τ(y, ˜ y), 〈w, φ(x, ˜x)〉).

3.2 Main Results

We now present our main result, showing that the uniform deviation of the population sub-optimality Fλ(w) - Fλ(wλ) from the empirical sub-optimality Fz,λ(w) - Fz,λ(wλ) decays with the rate O(1/n), provided that Fλ is strongly convex w.r.t. the norm ‖ · ‖, the dual norm of which is denoted by ‖·‖∗. Introduce the notation X∗ = supx,˜x∈X ‖φ(x, ˜x)‖∗. For any w ∈ W, we refer to Fλ(w) - Fλ(wλ) as the excess regularized generalization error (ERGE) of w. Let e = exp(1).

Definition 1 (Strong Convexity). A function f : W → R is said to be β-strongly convex (β > 0) w.r.t. ‖·‖ if ∀w, ˜w ∈ W and ∀α ∈ (0, 1), we have f(αw + (1-α) ˜w) ≤ αf(w) + (1-α)f ( ˜w) - β2 α(1-α)‖w - ˜w‖2 .

Theorem 1 (Main theorem). Let L > 0 and β > 0. Assume the loss function ℓ is L-Lipschitz continuous in the sense

Assume that Fλ(w) defined in Eq. (2) is β-strongly convex w.r.t. the norm ‖ · ‖. Let wλ be defined as Eq.(3) and any ρ0 > 0. Then, for any 0 < δ0 < 1/e, with probability at least 1 - 2δ0 the following inequality holds for all w ∈ W

In particular, for wz,λ in Eq.(1), we have the following inequality with probability at least 1 - 2δ0 for all 0 < a < 1

Note the norm |||·||| in the definition of regularization algorithm (1) is not necessarily equal to the norm ‖ · ‖ w.r.t. which Fλ is strongly convex. In learning theory, we often refer to the termD(λ) := E(wλ)-E(hρ)+λ|||wλ|||2 as the approximation error. It is a standard assumption that the approximation error admits a polynomial decay rate [Smale and Zhou, 2003; Ying and Zhou, 2016; Zhao et al., 2017]. In particular, if hρ ∈ W then D(λ) ≤ λ|||hρ|||2 [Guo et al., 2016]. Throughout the paper we use the abbreviation E(w) := E(hw).

Assumption 1. We assume the approximation error D(λ) enjoys a polynomial decay rate with exponent 0 < α ≤ 1 in the sense D(λ) ≤ cαλα, ∀λ > 0, where cα > 0 is a constant.

Theorem 2. Suppose that the assumptions in Theorem 1 and Assumption 1 hold. Then, for any 0 < δ0 < 1/e, with probability 1 - 2δ0 there holds

Proof. Plugging a = 12 in Eq. (6) and recalling Fλ(w) = E(w) + λ|||w|||2 , with probability at least 1 - 2δ0 we can upper bound the term E(wz,λ) - E(hρ) + λ|||wz,λ|||2 by

The stated bound can be derived by plugging Assumption 1 into the above inequality.

Remark 1. The regularization parameter λ should be chosen according to β and n to achieve optimal generalization bounds. Convergence rates O(log(n)/(nβ2 )) were established for the n-th iteration of online regularized pairwise learning algorithms [Guo et al., 2016], which are suboptimal to (6) if β ≪ 1. For example, under conditions of Theorem 2 with β ≍ λ, Theorem2 with λ ≍ n- 1 α+1 implies the learning rate O(n- α α+1 ) with high probability, while the discussions in [Guo et al., 2016] and [Lin et al., 2017] can only imply the rate O(n- α 2(α+1) log(n)) and the rate O(n- α 1+2α log(n)) in expectation, respectively. Here, A ≍ B means there are universal constants C1,C2 > 0 with C1A ≤ B ≤ C2A. In Section 4, we will apply Theorem 2 to improve the existing bounds for metric learning and ranking.

Remark 2. Another term of interest in the literature of regularized pairwise learning is E(wz,λ) - Ez(wz,λ). We now relate this to E(wz,λ)-E(hρ)+λ|||wz,λ|||2 . On the one hand, by Theorem 8.3 in [Cucker and Zhou, 2007] and |||wλ||| ≤ √D(λ)/λ, we have E(wz,λ) - E(hρ) + λ|||wz,λ|||2 = O(λ α-1 2 n- 1 2 )+E(wz,λ)-Ez(wz,λ)+D(λ) with high probability, where Ez(w) = Fz,λ(w) - λ|||w|||2 is empirical error (without regularizer). On the other hand, we can take w = wz,λ in (5) to get E(wz,λ) - Ez(wz,λ) ≤ E(wλ) - Ez(wλ) + E with high probability, where E is last term in (5) with w = wz,λ. Taking ρ0 in (5) as the right-hand side of (6) and using (6) we get E = O(1/(nβ)). This, together with E(wλ) - Ez(wλ) = O(λ α-1 2 n- 1 2 ), allows us to derive E(wz,λ) - Ez(wz,λ) = O(λ α-1 2 n- 12 +1/(nβ)), which improves the bound O(1/√nλ) based on the U-process approach [Cao et al., 2016] and the bound O(1/(λ√n)) based on the stability approach since we often have 1/n ≪ β ≍ λ ≪ 1 (for example, Theorem 2 suggests λ ≍ n- 1 α+1 ).

4 Applications

We now apply Theorem 2 to distance metric learning and ranking. We always assume g : R → R+ is convex.

4.1 Regularized Distance Metric Learning

As clarified in Example 1, an established regularization framework to learn the Mahalanobis distance metric can be reformulated as a regularized pairwise learning problem (1) with some specific instantiations of W, τ, φ and ℓ. Some interesting regularizers in metric learning include the ℓ1-norm regularizer favoring the element-wise sparsity [Cao et al., 2016], the mixed (2, 1)-norm regularizer encouraging the column-wise sparsity [Ying et al., 2009] and the trace-norm regularizer encouraging low-rank [Cao et al., 2016], etc. For any w ∈ Rd×d , we define the Schatten-p norm ‖w‖S(p) as the ℓp-norm of σ(w), p ≥ 1, where σ(w) is the vector of all singular values of w and the ℓp-norm of a = (a1, . . . , ad) ∈ Rd is defined as ‖a‖p = [∑dj=1 |aj|p ]1/p . For any w = (w1 ,w2 , . . . ,wm) ∈ Rn×m, the mixed (p, q)-norm of w is ‖w‖(p,q) := ∥∥(‖w1 ‖p, . . . , ‖wm‖p )∥∥q , ∀p, q ≥ 1. It is known that the dual norm of ‖ · ‖p,q is ‖ · ‖(p∗ ,q∗ ), and the dual norm of ‖ · ‖S(p) is ‖ · ‖S(p∗ ), where p∗ is the conjugate exponent of p satisfying p-1 + (p∗ )-1 = 1. For brevity, we introduce some notations X(p,q) = supx,¯x∈X ‖(x - ¯x)(x - ¯x)⊤‖(p,q), XS(p) = supx,¯x∈X ‖(x - ¯x)(x - ¯x)⊤‖S(p), Xp = supx,¯x∈X ‖x - ¯x‖p. Denote ˜ d = log d log d-1 .

We now apply Theorem 2 to study regularized metric learning with the regularizer involving various norms, including the mixed (p, q)-norm, the mixed (p, ˜ d)-norm, the S( ˜ d)- norm, and the S(p)-norm. Since ‖ · ‖2(p,1) , ‖ · ‖2S(1) are not strongly convex, we use the strongly convex regularizers ‖ · ‖2(p, ˜ d) and ‖ · ‖2S( ˜ d) [Kakade et al., 2012] to mimic the effects of the mixed (p, 1)-norm based regularizer and the Schatten-1 norm based regularizer, respectively. We hide the linear dependency on log δ-1 0 in the big O notation.

Corollary 3. Consider the regularized metric learning (1) with W = Sd×d , τ (y, ˜ y) = y˜ y, φ(x, ˜x) = (x - ˜x)(x - ˜x)⊤ and ℓ(a, b) = g(a(1 - b)). Let p, q ∈ (1, 2] and 0 < δ0 < 1/e. Assume (4) and Assumption 1 hold. If we choose λ ≍ X 2 α+1 ∗ n- 1 α+1 , then with probability 1 - 2δ0 we have E(wz,λ) - E(hρ) + λ|||wz,λ|||2 =

Proof. It was shown in [Kakade et al., 2012] that r(M) := λ‖M‖2(p,q) is 2λ (p-1)(q-1) p+q-2 -strongly convex w.r.t. the norm ‖ · ‖(p,q). Therefore, Theorem 2 shows that, with probability 1 - 2δ0, the term E(wz,λ) - E(hρ) + λ‖wz,λ‖2(p,q) can be upper bounded by

Eq. (7a) then follows by taking λ ≍ (Xp∗Xq∗) 2 α+1 n- 1 α+1 and noticing X(p∗ ,q∗ ) = Xp∗Xq∗ .

Eqs. (7b), (7c) and (7d) can be derived in a similar way. We omit the deduction for brevity.

Remark 3 (Comparison with the state of the art). We now compare our learning rates to the state-of-the-art bounds for regularized metric learning. We complement the existing estimation error bounds with approximation error bounds under Assumption 1. Jin et al. [2009] studied regularized distance metric learning (1) with τ (y, ˜ y) = y˜ y, φ(x, ˜x) = (x- ˜x)(x˜x)⊤ and ||| · ||| being the Frobenius norm, and derived the error bound E(wz,λ) - E(hρ) + λ|||wz,λ|||2 = O(( X4 2 λ + √ dλ )√ log δ-1 0 n + λα). Taking λ ≍ X 4 α+1 2 n- 1 2(α+1) , this bound becomes O(X 4α α+1 2 n- α 2(α+1) +√dn- 2α+1 4(α+1) ), which is worse than the bound O(X4 2 n-1 ) α α+1 in (7a) with p = q = 2. For regularized metric learning (1) with a general regularizer, with probability 1 - δ0 the term E(wz,λ) - E(hρ) + λ|||wz,λ|||2 was upper bounded in [Cao et al., 2016] by

where {σi}i∈Nn is a sequence of independent Rademacher variables taking the value +1 or -1 with equal probability. The term Ez,σ sup|||w|||≤1 ∑ni=1 σi〈w, xix⊤⌊ n2 ⌋+i 〉 is closely related to the Rademacher complexity for metric learning in [Cao et al., 2016] and can be estimated by the seminal complexity bound of linear prediction with specific instantiations of strongly convex functions [Kakade et al., 2012]. In Table 1, we list the best generalization error bounds derived by choosing appropriate regularization parameters λ to minimize (8). It is clear from Table 1 that our generalization analysis yields the bounds O(n- α α+1 ), which significantly improve the bound O(n- α 2α+1 ) in [Cao et al., 2016].

4.2 Regularized Ranking

As shown in Example 2, a regularized ranking problem is a specific regularized pairwise learning problem with some specific instantiations of τ and ℓ. In this subsection, we assume both || · || and ||| · ||| are the norm induced by the inner product 〈·, ·〉 in W, i.e., ||w|| = √〈w,w〉 for any w ∈ W. The following corollary follows directly from Theorem 2 by noting the (2λ)-strong convexity of λ‖ · ‖2 w.r.t. ‖ · ‖. We omit the proof due to the space constraint.

Corollary 4. Consider the regularized ranking (1) with ℓ(a, b) = g(ab) and either τ (y, ˜ y) = sign(y-˜ y) or τ(y, ˜ y) = y - ˜ y. Assume (4) and Assumption 1 hold. If we choose λ ≍ X 2 α+1 ∗ n- 1 α+1 , then with probability 1 - 2δ0 we have E(wz,λ) - E(hρ) + λ|||wz,λ|||2 = O((X2 ∗ n-1 ) α α+1 ).

Remark 4 (Comparison with the state of the art). Fast learning rates were established for unregularized ranking in a compact hypothesis space satisfying a capacity assumption with the loss function satisfying an assumption on the modulus of convexity [Rejchel, 2012]. These error bounds are stated only for the estimation error (ignoring the approximation error), and can be as slow as O(n- 1 2 ) if the capacity assumption is removed. Agarwal and Niyogi [2009] studied the generalization performance of regularized ranking algorithms based on a stability approach, and derived the bound E(wz,λ) - E(hρ) + λ|||wz,λ|||2 = O( 1 λ√n + λα). If we take λ ≍ n- 1 2(α+1) , then this bound becomes O(n- α 2(α+1) ), which is improved to O(n- α α+1 ) in Corollary 4 without capacity assumptions on the hypothesis spaces. Zhao et al. [2017] derived generalization bounds O(nϵ- α 1+α ) for a specific regularized ranking problem (1) with τ(y, ˜ y) = y - ˜ y and ℓ(a, b) = (a - b)2 . Here ϵ is a positive constant. Therefore, even for this specific regularized ranking problem, our general error bound for regularized pairwise learning (1) is able to imply a tighter bound than existing bounds derived exclusively for a specific regularized ranking algorithm using the least squares loss. It should be mentioned that the bound O(nϵ- α 1+α ) in [Zhao et al., 2017] can be improved if a further capacity assumption on the hypothesis space is imposed.

5 Proof of the Main Theorem

In this section, we present the proof of the main theorem (Theorem 1). The key idea in our deduction is to partition the hypothesis space into a sequence of subsets according to the value of ERGE, using the idea of peeling [Bartlett et al., 2005]. The strong convexity of the regularized objective then implies that the infinity-norm of functions in each sub-class can be bounded by the maximal ERGE associated to that subclass, which allows us to conduct the localization analysis to control the uniform deviation between the ERGE and its empirical counterpart in each sub-class by the local ERGE. For any w ∈ W, define the excess loss function by

Let ρ0 > 0 and 0 < δ0 < 1/e be any two fixed number. We construct two geometric sequences ρk = 2k ρ0, δk = 2-k δ0, k = 1, 2, . . .. For brevity, we set ρ-1 = 0. We group those w whose ERGEs belong to (ρk-1, ρk] into the class Wk

We denote by ⌊x⌋ the largest natural number not larger than x. We begin our deduction with the following lemma controlling the infinity-norm of functions in Hk.

Lemma 5. If (4) holds and Fλ is β-strongly convex, then suphλw ∈Hk ‖hλw‖∞ ≤ 2LX∗√ ρk β .

Proof. For any hλw ∈ Hk, ‖hλw‖∞ can be upper bounded by

where the first inequality follows from the Lipschitz property of the loss function ℓ and the second inequality is due to the definition of dual norm together with the definition of X∗. According to the definition of wλ and the strong convexity of Fλ, the following inequality holds for all w ∈ W

which, together with the assumption hλw ∈ Hk, implies

We prove Theorem 1 in four steps. For any f defined over Z×Z, we use ˆEzf = 1 n(n-1) ∑i,j∈Nn,i̸=j f(zi, zj) to denote the empirical average of f. In the first and second step, we conduct localization analysis in each sub-class Hk and get a bound with probability 1-δk for suphλw ∈Hk [E[hλw]-ˆEz[hλw]] in terms of ρk. In the third step, we show both δ-1 k and ρk can be bounded by ERGE, which together with union bounds, implies a probability inequality on ERGE in terms of a square root of ERGE. In the last step, we solve this probabilistic inequality to get the stated bound. The intuitive observation is that both the reciprocal of confidence and the constant in the bounded difference property for the application of McDiarmid's inequality in each sub-class can be controlled by ERGE associated to that sub-class, which allows us to get bounds on ERGE in terms of a square root of ERGE.

Proof of Theorem 1. Our proof consists of four steps.

Step 1. We first apply the McDiarmid's inequality (Theorem D.3 in [Mohri et al., 2012]) to control the deviation of suphλw ∈Hk [E[hλw] - ˆEz[hλw]] from its expectation. To this aim, we need to show that functions in Hk satisfy the bounded difference property. Indeed, for any z = {z1, . . . , zt-1, zt, zt+1, . . . , zn} and ¯z = {z1, . . . , zt-1, ¯ zt, zt+1, . . . , zn}, we have

where the last inequality follows from Lemma 5. Applying McDiarmid's inequality (Theorem D.3 in [Mohri et al., 2012]) with increments bounded by 8LX∗ n √ ρk β implies that with probability at least 1 - δk the term suphλw ∈Hk [E[hλw] - ˆEz[hλw]] can be upper bounded by

Step 2. We now use techniques in U-process to bound the expectation in (10). Specifically, Lemma A.1 in

[Cl´emenc¸on et al., 2008] with qw(zi, zj) = E[hλw] -

hλw(zi, zj) and the index set W allows us to derive Ez suphλw ∈Hk [E[hλw] - ˆEz[hλw]] ≤ Ez suphλw ∈Hk [E[hλw] -

samples independent of z and let {σi}i∈Nn be a sequence of independent Rademacher variables. According to Jensen's inequality and a standard symmetrization technique, the term Ez suphλw ∈Hk [E[hλw] - ˆEz[hλw]] can be upper bounded by

where the second inequality uses the fact that wλ is a fixed element and the last inequality follows from a contraction property of Rademacher averages (Lemma 4.2 in [Mohri et al., 2012] with the Lipschitz composition operator t ↦→ ℓ(τ (yi, y⌊ n2 ⌋+i), t), i = 1, . . . , ⌊ n2 ⌋).

The function ¯ Fλ(w) := Fλ(w) - Fλ(wλ) is β-strongly convex. Note that any w ∈Wk satisfies ¯ Fλ(w) ≤ ρk. Moreover, the definition of wλ implies that infw∈W ¯ Fλ(w) = 0. Therefore, the conditions of Theorem 7 in [Kakade et al., 2012] are satisfied and we can apply it here to show

Plugging it back into Eq. (11) gives

Step 3. We now present probabilistic bounds for supw∈W[E[hλw] - ˆEz[hλw]]. For any hλw ∈ Hk, k ≥ 1, we have ρk 2 = ρk-1 ≤ Fλ(w) - Fλ(wλ). Therefore,

ρk ≤ max{ρ0, 2(Fλ(w)-Fλ(wλ))}, ∀w ∈ Wk, k ∈ N∪{0}. Moreover, it can be directly checked that

According to the definition of Fλ and Fz,λ given in (1) and (2) together with the definition of hλw, we derive

Combining the above identity, (10), (12) and (13) together, with probability 1 - δk the following inequality holds uniformly for all hλw ∈ Hk

The stated inequality (5) follows directly if we apply union bounds over H0,H1, . . . with confidence δ0, δ1, . . . (notice that ∑∞k=0 δk = 2δ0).

Step 4. Finally, we present probabilistic bounds for the estimator wz,λ. According to the definition of wz,λ, we have Fz,λ(wz,λ) ≤ Fz,λ(wλ) and therefore (5) implies

Take the assignment ρ0 = 256L2X2 ∗ nβ . If Fλ(wz,λ) - Fλ(wλ) ≥ ρ0 2 , the term Fλ(wz,λ) -Fλ(wλ) can be further upper bounded by

For the assignment ρ0 = 256L2X2 ∗ nβ and any 0 < a < 1, the term nβ(Fλ(wz,λ)-Fλ(wλ)) 128L2X2 ∗ can be upper bounded by (note (a + b)2 ≤ 2(a2 + b2 ), ∀a, b ∈ R)

where the last inequality follows from log a ≤ ab + log 1b - 1, ∀a, b > 0. Solving the linear inequality (14) directly yields the stated bound (6) with probability at least 1 - 2δ0. If Fλ(wz,λ) - Fλ(wλ) ≤ ρ0 2 , it is clear that (6) holds.

6 Conclusions

We develop a unified generalization bound for pairwise learning, and apply it to improve existing results. It would be interesting to study pairwise learning by exploiting the smoothness of loss functions [Zhang et al., 2017] and consider distributed pairwise learning algorithms [Lin and Zhou, 2018].

Acknowledgments

This work was supported in part by the National Key Research and Development Program of China (Grant No. 2017YFB1003102), the National Natural Science Foundation of China (Grant Nos. 61672478, 61502342), and the Science and Technology Innovation Committee Foundation of Shenzhen (Grant No. ZDSYS201703031748284).