Generalization bounds for Kernel Canonical Correlation Analysis
Authors: Enayat Ullah
Raman Arora
Venue: Accepted by TMLR ()

Abstract: We study the problem of multiview representation learning using kernel canonical correlation analysis (KCCA) and establish non-asymptotic bounds on generalization error for regularized empirical risk minimization. In particular, we give fine-grained high-probability bounds on generalization error ranging from $O(n^{-1/6})$  to $O(n^{-1/5})$ depending on underlying distributional properties, where $n$ is the number of data samples. For the special case of finite-dimensional Hilbert spaces (such as linear CCA), our rates improve, ranging from $O(n^{-1/2})$ to $O(n^{-1})$. Finally, our results generalize to the problem of functional canonical correlation analysis over abstract Hilbert spaces.

Published in Transactions on Machine Learning Research (03/2023)
Generalization bounds for Kernel Canonical Correlation Anal- ysis
Enayat Ullah
enayat
Deportment of Computer Science
Johns Hopkins University
Raman Arora
arora jhu edu
Department of Computer Science Johns Hopkins University
Reviewed on OpenReview: https: // openreview. net/ forum? id= BuW
Abstract
We study the problem of multiview representation learning using kernel canonical corre- lation analysis (KCCA) and establish non-asymplotic bounds generalization error for regularized empirical risk minimization. In particular, we give fine-grained high-probability bounds on generalization error ranging from Oln-1/6) to O(n-1/5) depending on underlying distributional properties, where n is the number of data samples. For the special case of finite-dimensional Hilbert spaces (such as linear CCA), our rates improve, ranging from O(n 0112) to O(n Finally, our results generalize the problem of functional canonical correlation analysis over abstract Hilbert. spaces.
1 Introduction
Canonical correlation analysis (CCA) is popular technique for multiview representation learning and statistical data analysis. Given a pair of random vectors, CCA finds maximally correlated linear components of the two vectors (Hotelling, 1936). CCA-based methods have recently been shown to improve unsupervised learning of low-dimensional representations of data when multiple "views" of data are available (Vinokourov et al., 2003; Hardoon et al., 2004; Arora and Livescu, 2013). The different views often contain complementary information, and CCA-based multiview representation learning methods can take advantage of this information to Icarn fcatures that are useful for understanding the structure of the data and that is beneficial for downstream tasks.
Various nonlinear extensions of these multiview learning techniques have also been proposed including kernel CCA (Lai and Fyfe, 2000; Akaho, 2001; Hardoon et al., 2004; Fukumizu al., 2007) based positive definite kernels wherein data are represented as functions in associated reproducing kernel Hilbert spaces (RKHS), and deep neural network based extensions, e.g., deep CCA (Andrew et al., 2013)
While CCA and its nonlinear extensions have enjoyed tremendous empirical success, the theoretical un- derstanding of the approaches to solving these problems has been somewhat limited. For example, only recently, were we (as a community) able to give statistical and computational complexity bounds for CCA stochastic optimization problem (aka learning problem) (Allen-Zhu and Li, 2016; Ge et al., 2016; Arora et al., 2017). In similar spirit of understanding the data analysis techniques learning problems, in this paper, we look at Kernel CCA and focus on understanding the generalization properties.
However, moving from subspace learning (i.e., linear representations, e.g., using CCA) to learning representa- tions in an RKHS has additional theoretical challenges associated with it. is then natural to rely on kernel duality, i.c., the representer thcorem reduce the empirical risk minimization (ERM) problem a finite dimensional optimization problem. Using kernel duality to formulate Kernel CCA was first studied by Lai and Fyfe (2000), Akaho (2001), Melzer et al. (2001) and Bach and Jordan (2002).

---

Published in Transactions on Machine Learning Research (03/2023)
In this work, we are interested in understanding the statistical properties of the regularized empirical risk minimizer (defined formally in the subsequent sections) using excess gemeralization ervor as the error criterion. Informally, excess generalization error of an estimator is the excess error, incurred in objective (or cost), compared to the best, with respoct to the underlying data distribution (sce Section 3 for a precise formula). This problem has been studied in prior works of (Fukumizu el. al., 2007; Fan and Lian, 2016), however their results are asymptotic (sce paragraph "Relation to prior work" for more details). Further, these works have studied Kernel CCA in terms of estimation error (or convergence in parameters), and we emphasize that studying the problem in terms of generalization error (or convergence in objective) is important for the following reasons. (Modern) machine learning is typically posed risk minimization problem where the goal is to find parameters that are good in terms of the objective (aka generalization error or population risk) rather than finding the (rue parameters (under some statistical model). Taking learning view of the KCCA problem, we therefore measure the quality of the solution in terms of the objective rather than distance from a ground truth (which may or may not be unique). This crror criterion has been used in the prior works, such Arora et al. (2017) and Wang et al. (2016), for (linear) CCA. Hence, the main goal in our work, is to give "fine-grained' non-asymptotic guarantees excess generalization error of regularized empirical risk minimizer (a widely used estimator) for kernel CCA.
1.1 Our Contributions
Our main contributions are as follows.
1.
We pose kernel CCA as learning problem and give upper bounds on excess generalization error of the regularized Empirical Risk Minimizer (ERM). Our results hold for the more general problem of functional CCA in abstract Hilbert spaces. To the best of our knowledge, this is the first work which establishes statistical rates of a finite sample estimator for functional CCA. As special cases, our results give generalization bounds for Kernel CCA and linear CCA, and for both of these special cases, we establish novel results compared to previous work (see below).
2. Under standard assumptions (sce Assumption 1), we obtain non-asymptotic bounds on excess generalization error of regularized ERM for kernel CCA, which are between On1o/) to Onn depending on properties of the underlying distribution, where n is the number of data points (see Theorem 1). In contrast, previous works only yield asymptotic guarantees. In the setting when the Reproducing Kernel Hilbert Spaces (RKHS) are finite dimensional, we obtain faster rates ranging from O (n-1/2) to On=²) (see Corollary 3). In the special case of linear CCA, our optimistic rate (i.c. 0 ()) is better that the previous result of Gao et al. (2017) and the worse case rate is better in the regime where eigengap of covariance matrix at k is o(1/vT) (see Section 4 for details).
3. Our analysis provides insights on the role that regularization parameter plays towards trading off approximation error (bias) and estimation error (variance) and in ensuring statistical consistency of the estimator. In particular, in our bounds, the regularization parameter can decay as w(n-1/2) and ensure statistical consistency of the estimator see paragraph "Regularization parameter' in Section 4 for details.
Our proof strategy is to decouple the estimation and approximation errors in the learning problem, bound them separately and balance the tradeoff (between them). To bound the estimation error, the primary tool we use is local Rademacher complexity analysis (Bartlett et al., 2002), which allows us get a spectrum of rates, from worst case optimistic (depending on how "easy" the problem is). In the context of kernel methods, these techniques have been applied to give improved rates for kernel principal component analysis (Blanchard et al., 2007), support vector machines (SVMs) with random Fourier features (Gilbert et al., 2018) and other kernel learning problems (Mendelson, 2003; Cortes et al., 2013; Ullah et al., 2018). Please see Section 5 for a detailed proof sketch.
Relation prior work. Herein, we informally discuss how our work compares with prior results. We refer the reader to paragraph "Comparison with prior works', in Section for more details. Previous work has studied the the statistical properties of Kernel CCA through the lens of statistical estimation of
2

---

Published in Transactions on Machine Learning Research (03/2023)
Problem
Error criterion
Convergence rate
Reference
Kernel CCA
Parameter
Op(1)
Fukumizu et al. (2007)
Kernel CCA
Parameter
Op(n 1/(
Fan and Lian (2016)
Kernel CCA
Objective
O(n O(n-1/0) 170) to O(n-1/o)
Ours (Corollary 2)
(Linear) CCA
Objective
( (ggap")) -
Gao et al. (2017)
[inear) CCA
Objective
(((gap/n) ") to O((gap n) Ours (Corollary 3).
Table 1: Summarizing our results in context of relevant prior works. In the table, "Parameter' and "Objective'
stand for convergence in paramcter and objective respectively (see Section for details). f: obtained under additional assumption on eigenvalues of covariance operators - see Equ. (3), and a = min(axx ay) therein. $: gap (C) A2(C) is the eigengap.
parameters. (i.e by bounding eslimalion error). In particular, the works that are most related to ours are that of of Fukumizu et al. (2007) and Fan and Lian (2016). Under standard assumptions, Fukumizu al. (2007) established statistical consistency of the regularized ERM solution if the regularization parameter À w/ss./s). More recently, Fan and Lian (2016) established minimax statistical rates for Kernel CCA under additional assumptions on the problem. The guarantees in both Fukumizu et al. (2007) and Fan and Lian (2016) are asymptotic. Fukumizu et al. (2007) show that as number of samples n - oc, the estimation error goes to 0, in probability. The work of Fan and Lian (2016) gave rates but these are also in the convergence in probubilily sense. To elaborate, they consider the event that the estimation error random variable grows faster that certain sequence in n, and show that probability of this event is limiting to 0. These notions do not give any quantitative finite sample guarantees, and are even weaker than convergence in mean. On the other hand, our guarantees are non-asymptotie- the bounds hold with probability, say at least 1 - 8, over the randomness in data for any sample size; and importantly the sample complexity bounds only has poly(log(1/O)) dependence in the failure parameter what are known as "high confidence" guarantees.
In Table 1, we give a summary of our results in context of prior works.
Organization. The rest of the paper is organized follows. We give mathematical preliminaries in Section 2. In Section 3, present functional and kernel CCA learning problems, emphasizing the role of kernel duality and regularization. In Section 4, we present our main result and discuss various implications. Finally, in Section 5, we conclude a brief sketch of the proof.
2 Preliminaries
In this section, we quickly review some mathematical preliminaries in functional analysis; a didactic treatment of random variables in Hilbert spaces, reproducing kernel Hilbert spaces and Local Rademacher complexity is presented Appendix A.
Let Fxx and (Hy, Py) be two measurable Hilbert spaces where Hx, Hy are separable spaces, Fx, Fy a-fields and px, Py probability measures. Let {o²") J ieN and (o²") Jien be orthonormal basis for Hx and Hy respectively. Let h Hx and h2, M2 E Hy. We use (h1, h4) px (h1, M)xxx as per convenience, to denote the inner product between two elements. Similarly we use | or [1 Hx for norms.
An operator D : Hy + Hx is bounded if its operator norm |DD]] defined as |D] == sup h E Hy, [bllly 1} < oc. The outer product f @L(Hy, Nxx) fı is an operator from Hy to H.x, which acts as (hr &I(Hy,Hx) h2)h = (h2, M) hn for h E Hy. The adjoint operator of D, denoted as D* H. - Hy, is defined as (7n, Dh2) (D"h,, h2)
A bounded operator is self-adjoint if D D. An operator Hy + Hx is Hilbert- Schhmd if its Hilbert-Schmine norm, denoted as ||D| [D|1 == ΣiEn [Dee || = =nJENn "e",,e"") <0. We use L(Hy, Hxx) to denote all Hilbert-Schmide operators from Hy to Hx. For the sake of brevity, we use L(Hx) to denote Silbert-Schmidl operators from Hx to Hx. An operator D Hx Hy is compact if the image of
3

---

Published in Transactions on Machine Learning Research (03/2023)
every bounded subset of H.x is relatively compact subset of Ny. A compact operator D Hxx - Hx is trace-class if ||D]] (R) == Eiz ((DD)) Hx < <00, where [D] ((xx) denotes the nuclear norm of D. An operator D Hx + Hx is positive V f E Hx, (f,Df'' 2 0. The identity operator Ix Hx + Hx is
defined as Ix A H.x
Notation. We use capital Roman letters (e.g., A) to denote matrices and operators, small Roman letters (e.g., a) for vectors and small letters (e.g., a) for scalars. Operators over the space of Hilbert-Schhidt operators are represented using capital Fraktur letters, e.g., 21 For a Hilbert-Schmidt operator D, (x denotes its 5th eigenvalue. Similarly, (D) denotes the 7th singular value D. We use Pf to denote the top rank & projection of D; for example, if the Singular Value Decomposition (SVD) of is = Σien deu; @ va then P = EE uz Ve- We use Ig R to denote k x h identity matrix. Natural numbers are denoted by N; [n] denotes natural numbers from to n.
3 Problem Setup and Background
We begin by recalling the finite dimensional CCA problem. For paired random vectors, x E X C Rdx and y e J C Rdy, with some unknown joint distribution p, Canonical Correlation Analysis (CCA) can be posed the following problem.
maximize UER VER (UVT Exy [xy such that U U Ex [xx [x L2, V By [yy V Tk.
where (A, B) = Trace(A BB) is the standard inner product on matrices.
Functional CCA. We can generalize the above formulation to abstract Hilbert spaces. In particular, when and y are random variables in Hilbert spaces Hx and Hy, respectively, the functional CCA problem can be formulated as,
(UV*, CxHy,)) such that U'CUU IR V"C,V UEL(Hx. VELLW,y
maximize
where Cx = E [x(0L()))))))) x and Cy = (Ly))(H))))) y] are auto-covariance operators, and Cxy = E @L(Hy.Hx) y] is cross-covariance operator (we refer the reader to Appendix A for definition).
Kernel CCA. Nonlinear CCA extends the problem of CCA in to a high dimensional feature space using nonlinear feature maps. Kernel CCA is one popular variant of nonlinear CCA where the feature maps are implicit in the kernel functions. It can be viewed as a special case of functional CCA with RKHS H.x and Hy over X' and y associated with kernel functions kx and ky, respectively:
Uc REE,,,, (UV*,Cx)) L(Ks, such that VC,
maximize
where Cx E (xx :) (((HX) kx 1] Oy E (Ny(y,) :) @L(HS) ky :)] are auto-covariance operators, and Cxy = E [xx :) @ @((Hy.Hx) ky() is the cross-covariance operator.
Basis transformation. An alternative equivalent formulation of CCA is obtained by rotating the compo- nents in the canonical basis. We then get the following formulation.
maximize R") (UV", NUV",x1'/C0 Cx'3Cxx L(Hy.Hx)
such that U'U II. V'V=
At first, the reformulation above seems to require that the auto-covariance operators are invertible. In the context of kernel CCA, if the feature space corresponding to the kernel function is finite dimensional (for example, when using polynomial kernels), then invertibility can hold. However, does not hold in general, for example when using a Gaussian kernel, the anto-covariance operators can no longer be trace-class. This is a problem since the standard assumption of random variables being bounded implies the corresponding
4

---

Published in Transactions on Machine Learning Research (03/2023)
auto-covariance operators are trace class and therefore we have contradiction. However, note that we instead write the above equivalently as,
maximize UEL(M,..R" (UV*, (1 s.t. CX
C/2 oo Cxy, U = LR, V*V = lg.
(1)
The existence and uniqueness of such an operator C, bounded as ||||| S 1, is established in Baker (1973, Theorem 1) and also discussed in Section 2.2 of Fukumizu et al. (2007). As in Fukumizu et al. (2007), we assume that is compact and abuse the notation to write C Cx invertible.
CC 1 Cx> even when these are not
We now discuss a final assumption. Note that since Cx and Cy are self-adjoint, spectral decompo- sition of Cx and Cy exists. Let Cx == Ei A(Cx) @1(Hx) &f and Cy := Ei= A: @r(Hy) of where {0 and {o]}, are the eigenfunctions of Cx and Cy respectively. Ni = Exy |of (((H),H) of Cxy) Liny. We assume that max,s A((x))/A(CS))
We define
my
S 1 and
maxs, Cx C Cry are bounded, and their operator norms bounded by 1. These assumptions have appeared in previons works Fukumizu et al. (2007) and Fan and Lian (2016) and ensures existence of solution to the kernel CCA problem.
1. With abuse of notation, this means that the operators Cx CxyCy
1/2 and
(((C)))(CC)))
Observe that the solution to the CCA problem in Eqn. (1) is given by the singular value decomposition and vf, vS,v,,,,, ve be the top-k left and right singular functions
(SVD) of C. In particular, let of, uu. ..... Sn of C, respectively. We define Uc R² + Hx such that Ucb = Exe buu where b E R$ and similarly Vo- The solution to the CCA problem in Eqn. (1) is UC and Vc.
Empirical Risk Minimization (ERM). We now discuss the learning problem and a finite sample estimator. Let {x)), be n data points drawn i.i.d. from p. We first define empirical counterparts of auto covariance and cross-covariance operators. We define C2 Hx + Hx and Cj: Hy + Hy as C% 1 E X @I(Hx) X and Cj 1 E @I(Hy) Ys, respectively. Similarly, the empirical cross- covariance operator C2y formulated as,
n
1 n E X, (L(HH,H)) ye. We also define C = (C*) 1/2 Cxy (C²) (03)-1/2 ERM is (1/2
(UV*, "r",""))))) ((Hs))) such that U = It, V-V = T 8+
maximize
The solution to the ERM problem above, analogously, are the singular functions of C". Lot uf uu..... up and vi, vll ......, vi be the top-k left and right singular functions of Cn respectively. We define U B Hx such that U,b = E b,uf, where b E RK and similarly Vn.
Excess Generalization error. As motivated Section 1, we are interested in studying the kernel CCA problem from the point of view of learning, i.e., generalization error. The excess generalization error of an estimator is the excess error incurred, in objective, compared to the best, with respect to the underlying distribution. The excess generalization error of ERM solutions (i.e. (Un, Vw)) is the following,
E(Un, Va) = (UcV) - U, C)
Kernel duality. Note that even if we establish statistical convergence of the estimator, we cannot talk about computational aspects as these are infinite dimensional objects. However, in the special case of RKHS, can appeal to kernel duality to guarantee efficient computation. In the context of CCA, by observing that the solution should lie in the span of data, Akaho (2001) and Bach and Jordan (2002) show that the empirical problem is equivalent to solving the following finite dimensional optimization problem.
1 (UVT, _xKKy such that
1 VTRRVV= = Te, 1 LUKKU = Tk,, n
maximize UERoxk VERRxX
n
5

---

Published in Transactions on Machine Learning Research (03/2023)
where Kx and Ky are nxn kernel matrices with (Kx)s = (x(x,, xy) and (Ky); ky) Solving this typically takes (n time and (nn²) space. However, there are faster approximate alternatives, for example, those based on approximate feature maps (Rahimi and Recht, 2007; Kar and Karnick, 2012), Nyström's method (Drincas and Mahoney, 2005) and sketching (Yang et al., 2015).
3.1 Regularization
Empirical risk minimization (ERM) is one of the most popular learning rules. However, without an appropriate inductive bias, c.g., in the form of a regularizer, the ERM solution may fail to generalize. For the ERM problem corresponding to canonical correlation analysis, a natural regularizer is a variant of Tikhonov regularization (Groetsch, 1984), which can be described as follows. Define C² := =C + XxIx, CgAA" C3 Ayly and C = (C identity operators over Hx and Hy, respectively. The regularized ERM problem for CCA (Hardoon et al., 2004; Vinokourov et al., 2002) is then given as:
(CC (C):Ar)-1//2 where xx and Ay are regularization parameters, and Ix and ly are the
maximize UEL R,,VL,, (UV*,C"AA L(Hy,Hxx such that U'U= Ir, VV=
The regularization above corresponds to shifting the spectrum of the auto-covariance operators for Xx, Ay > 0, that all eigenvalues are positive. Intuitively, we see that this regularizer biases the problem to tradeoff solutions which maximize correlation and are not along directions with small (non-zero) variance. Specifically, since for all practical purposes, we only observe finitely many samples, and so the presence of very small eigenvalues magnifies the spurious correlations observed. It is therefore imperative to minimize the effect of such small eigenvalues.
We emphasize that regularization parameters Xx and ny should be viewed as parameters dependent on n, as is standard in statistical machine learning. Moreover, in such problems, it is usually expected that the regularization paramcter decays fast with the number of samples, c.g., as poly(1/n). In Section 4, discuss the approximation and estimation error tradeoff and how to set the regularization parameters appropriately to optimize it, to have a small overall excess generalization error. In the case where the auto-covariance operators are already positive definite, i.e., their eigenvalues are lower bounded away from zero, the regularization parameters can be viewed as minimum cigenvalues of the corresponding operators. This gives us the rates for kernel CCA in finite dimensional Hilbert spaces, as presented in Corollary
4 Main Results
We first collectively state all necessary and simplifying assumptions, and then state our main theorem. All these assumptions are standard and have appeared in the previous works, and we discussed some of these in the prior section.
We assume that the Hilbert spaces Hx and Hy are separable, random variables x and y are centered and bounded as, ||ж|| S 8 and |ılllH 8 almost surely, that C, defined in Eqn. (1), is compact and the singular values of C are distinct. We assume that ||xx "xxy 1/2 < 1 and ||xx (Cx-V/2xx>C>>1//
Assumption 1.
1. Theorem (Functional CCA). Let x and y be random variables in Hilbert spaces Hx and Hy, and let p be the joint distribution over Hx Hy, and px and py denote its marginals. Under the conditions of Assumption 1, given data samples (x1, (x2. ... (x) drown i..dd. from p. with probability least 5, the encess generalization error of regularized ERM, Und Vn,d, is bounded as,
2 2)+ + 16k (VAx+ V (C(C)
(UcVC- - Un.VV VI C) L(Hs,Hx) S 4k <4K(VAx++ (Ax*+VA)))))
ox(C)
+ inf 420
12aph + 24aVT 24
k
Ex((e))
12ap + 223 log(1/0)
10a, log Axdyn
Axdyn
Axdym Vn
>xx
Axdyn
(VArdy)
6

---

Published in Transactions on Machine Learning Research (03/2023)
(x, 2','' (. V. W,, (Aa(C) Ac+1(C)) and Ex E L(L(Hy, Hx)),, defined as c= where ap (x.9)r w'op Exy [(x (L(Hy, y) (L() (x OLCHy.Hx) w)] Cxy (L(L(Hy,Hxx) Cxy.
E.
A few remarks are in order. First, for simplicity, consider the case when Xx = > the dependence on À (which should be set as 1/poly(n)), the operator e' and n, with probability at least - 5, we get the following bound,
= x. we only consider
(UcVo Un. Va. 9) H( 5o S0(VA- (VV++
log(1/8) + inf gapa (C)A2n
h (CpA Avn
Σ s(ee)) JSh
(2)
420
where (CPx ((1)) is the eigengap of C at k, which shows up in our generalization bound. We emphasise that the existence of cigengap at k as well as that the cigenvalues of C are distinct (in Assumption 1) are simplifying assumptions. The analysis goes through even otherwise; however then the dependence on gap at k is replaced by gap at pth singular value where p > k. Moreover this dependence on gap, in general, is unavoidable, as evidenced by existing lower bounds in the special case of lincar CCA(Gao et al., 2017, Lemma 20).
Spectrum decay of C², We see that the convergence rate crucially controlled by the decay of the spectrum of C², i.e the term x Σi>h Ay(C"). In the worst case, it behaves as O X ; the best is when e' is of finite rank, where it behaves as (()AAn). Furthermore, if the spectrum has an exponential decay, it is O(log n/n). We emphasize that this term is the result of the local Rademacher complexity analysis which manifests as a spectrum of convergence rates based on higher-order distributional properties.
Optimizing the Approximation Estiiiatinn error tradeoff. We call the first term on the right hand side of the inequality (2) as the bias and the second and third term, collectively, the variance. We have that bias is in O(vX) but the variance behaves differently depending the spectrum decay of C². In the worst case, the variance is in O(1-2n-1/2). Optimizing the tradeofI, we get rate of O(n-1/6) when À x= O(n In the best case, the variance decays as O(X-2=-1), which yields an optimistic rate of O 1/5) when A = θ (n 6/2).
Kernel CCA. When Hilbert spaces Hx and Hy are RKHS associated with kernel functions kx and ky respectively, then Theorem 1 gives statistical rates of convergence of empirical kernel CCA in terms of the objective. In particular, we have the following corollary.
Corollary 2 (Kernel CCA). Along with the notations and assumplions of Theorem 1, suppose that Hx and Hy are reproducing kernel Hilbert spaces associated with kernel functions kx and ky, respectively. Then, regularized ERM data points outputs Un,VV* V.A which satisfies the following with probability at least 1 8,
(UcVé - Un, C) ((H)))))) 50 Vx log(1/0)ap
hap X
Σ Exsters JDN
})
+ inf
X²n
120
Avn
where 0pp = Ex (hexx,x))kykx,,ye (Ce - Ao+1 (C)).
Comparison with prior works. Previous work of Fukumizu et al. (2007) and Fan and Lian (2016) study Kernel CCA, for & = 1, in the sense of convergence of parameters, i.e. distance between the true and the estimated solution. In particular, let v.) be the true solution of Eqn. (1) and let(ūū, fn) be a candidate solution. The error is then given by 1/2 - ún)l Hx and similarly, 1/C - 1i) We remark that this is a stronger notion of convergence and implies convergence in objective. However, (as we will discuss), their implied results are weaker than ours. Importantly, both these works only give asymptotic results, in sense of convergence probability; this mcans that the success probability over the draw of samples is not quantified, but only limiting to as n + co. In contrast, our results being non-asymptotic hold for all sample sizes. Finally, our results hold for general k opposed to the above works which are limited to k = 1.
7

---

Published in Transactions on Machine Learning Research (03/2023)
We now discuss both of these works one by one. The goal in Fukumizu et al. (2007) is to establish statistical consistency of the (regularized) ERM. They show that as n - oc, the error ||xx |Cx1/2(u ut)l = (p()), and similarly for error ||C),4/(v1 - 9 o On the other hand, as remarked earlier, we give high-confidence upper bounds on error in objective, as function of sample size n, for any n.
The other related work of Fan and Lian (2016) establishes minimax rates for Kernel CCA in the sense of convergence parameters. However, their results hold under a strict assumption on the decay of eigenvalues of Cx and Cy. In particular, there require existence of constants C, ax and dr, such that all eigenvalues of Cx and Cy are upper and lower bounded as,
(1/O)j <)x(Cx) S Cj (1/C)j S ,y(Cy) S CCj
(3)
The statistical rate then, in the sense of convergence of parameters, ||Cx - â li)
Op(max(n -00//====///xx]]]___) (1))(ay))))) As remarked before, these asymptotic guarantees do not quantify the number of samples required in terms of the confidence parameter 6, and are even weaker than convergence in mean. Moreover, there is a large regime where their additional assumptions do not hold, but our results still apply. In particular, suppose that eigenvalues decay exponentially, i.e., Ay(Cx) = e Since exponential decays faster than any inverse polynomial, so it goes below the inverse polynomial for large enough j (and we are in infinite dimensions)- this violates the condition of Fan and Lian (2016). In general, any sub-polynomial or nuper-polynomial eigenvalue value behavior of Cx or Cy violates their condition; but our results are agnostic to it. Finally, their result docsn't 't provide any insights how the regularization parameter be set to control and bias and variance, which is important from practical perspective.
Regularization parameter. Fukumizu et al. (2007) suggest setting the regularization parameter as w(n 1//3) to ensure statistical consistency of the ERM. In contrast, when we set Xx = xy X, our results showcase an improvement of the same estimator to w(n wnn-1/2), logether with high-confidencee guarantees. This follows because bias in O(V)) and variance is of the order -12=2, so both decrease with n when A wnn-1/2)
Finite dimensional Hilbert spaces. As special case, result can be applied to give guarantees for (unregularized) ERM wherein we assume that the smallest cigenvalues of auto-covariance operators Cx and Cy are lower bounded away from 0 by xx and Ay, respectively. This subsumes standard CCA problem as well as kernel CCA where the RKHS corresponding to the kernel map is finite dimensional. We obtain rates ranging from n -1/2 to -1 depending on the spectrum decay of e.
Corollary 3 (Finite dimensional kernel CCA). Along with the notations and assumptions of Corollary 2, suppose that RKHS Hx and Hy are finite dimensional with the eigenvalues of Cx and Cy lower bounded by Ax > 0 and xy > 0 respectively. Then, ERM on n training data outputs Un V which satisfies the following with probability at least 1 8,
(UoVa-Una - Un, Vo C) (i 5 log(1/0) inf gaps (C)APR
})
h
+ 1 A/n
Σ >s(er) joh
420
(C)APn
where gap, (C) - AC+1(C) is the eigengap of at k.
Linear CCA. We compare results with that of Gao et al. (2017) for the special case of the linear CCA. For 1, Gao et al. (2017) showed that ERM achieves sub-optimality with O(1 21//gap2>²) sample complexity, where gap- = A (C) - >²(C)), ignoring log factors. In comparison, our sample complexity is 0 (()/gap>2c) in the optimistic case and ( minngggg, e)) in the worst case; therefore, our optimistic case is always better than Gao et al. (2017), whereas the general/worst-cast worst-case rate better whenever gap = w (t).
See Table for a summary of our results and comparison with prior works.
OOp and op are standard asymptotic notation for rates of convergence in probability for a pair of random sequences, fn and On: we write fn Op(nn) Ja/ gal bounded in probability, and fn op(gx) if Sn/lgul converges to 0. in probahility.
8

---

Published in Transactions on Machine Learning Research (03/2023)
5 Proof Sketch
In this section, we skotch the main proof ideas underlying our analysis; full details are deferred to Appondix B. Recall that the optimal solution the population objective are given by operators Ue and Vo that correspond to the first cigenfunctions of C"C and CC*, where C = C= = CxyCy 1/22 For the sake of analysis, we introduce regularized whitened population cross-covariance operator Cx = (Cx xx)=>//Cx>>(y + Xy)-1/2, whose top k left and right singular functions are denoted by Uc.A and Vc,.- The empirical counterparts are denoted by C = (C)) (y)))) -1/?, Un and Vn, and the regularized empirical counterparts by Un. and Vn,A- We begin with the following decompasition of the excess error into approximation error, and estimation error,
C (Cy)
E(UnA VnA) = (UoVo - UnAVing C) ()
= (UoVe- UC.. C) 1
L(Hy,HHx)
Approximation
+ (UC,AVC. - UUAV n, C) L(Hg,H()) = (UcVe UC Vo, C) L(Hs
Estimation error
Approximation error
+ (UcvVos - Va,A Cx) (x) ((H)HH)))
(UCA - UnAV Cx) L(Hy.Hx)
Estimation error 2
Error 3
We can write the sum of the first two terms, Le,, the approximation error and the estimation error 2 as
VU. C) C)(HHyHN - (UC.VVG. Ca) ((N + (UnAVaa Ca C) L(H
Error
Error
We bound each of the three error terms separately. The bound Error 1 and Error 2 (sec Appendix B) holds due to the following lemma which bounds the distance between the whitened covariance operator and its regularized counterpart.
Lemma 4. Let C =
and Cx = (Cx + 1x1x)=1/2 Cxy (Cy: + AyTy) 1/2 be its regularized counterpart. Suppose that C compact, then, there difference is bounded as, ||C Cxll S 4(v Vxy).
It remains to bound Error 3; we prove the following result which follows using the local Rademacher complexity analysis of Bartlett et al. (2002).
Lemma 5 (Error 3). With probability at least 1 - 8, the Error 3 is bounded as,
12aph
+ 24a 24
(U, UnAVa Cx) (.H.9.H)
inf h20
Σxy(e)) 5iA
Axdyn
Axdyn
Vnl
Axdyy
+ 12a,
22,8 T (og((10))
10a, 1og(1/8)
+
Ax
Vixdyn
Axdyn
where ap Exyy,' w' [lo, 22 Hx (u. HHu) /(xx(C) (C))
We sketch a proof the key result in the next section.
5.1 Proof Sketch of Lemma 5
Our main tool is local Rademacher complexity analysis (Bartlett et al., 2002) of the problem, following its application in Kernel PCA (Blanchard et al., 2007). The exact statement of local Rademacher complexity result of (Bartlett et al., 2002) is stated as Theorem 10 in Appendix B. We now discuss how we apply it to our end. We first define the excess risk function class.
F ==f fuNv (z.0) (UCAVox -UV", Czu) L(Hy.Hx)
UUCYU It VCVV T
9

---

Published in Transactions on Machine Learning Research (03/2023)
where UC, = (C*** ) UC Ve.- > Ve, and Cxy = x (I(Hy,Hx) y.
1/2
1/2 VoV
We remark that we cannot directly apply the local Rademacher complexity technique to this class Theorem 10 requires that the range of functions be contained in [-1.1]. We therefore look at G = TF, where
7 == (Axdy/(2VVB) and show that it satisfies this requirement.
Vaxdy 23
Lemma 6. For any f
the runge of f is contained in [-1,1], where T
We also need to show that this function class 9 satisfies the "local' assumption of Theorem 10, i.e. the second moment is at most a multiple of mean.
Lemma 7. For any f E 9, [[ s BBIl where p = 2xxT/(xx and ap = Ex (x,x') (v.y) ((A(C)-
Next, we bound the Rademacher complexity of the star shaped hull of the function class conditioned on bounded second moment. We simplify this by considering a bigger class which contains star(g). Formally, we show that the family {9- E star(g) [o"] r) is contained in
4k S, (x= + (.= L Hx), ( Axdy
.T, ET) L(NY, S " 72)
where C¹ I(Hy, Hx) 7 L(Hy. Hx) is fourth moment operator, defined as E Exy [xx (L(Hy, Hxx y) Hxxl (x @L(Hs, u)]. A crucial technical result follows.
Lemma 8. The Rademacher complexity of S, is bounded as follows,
k
Rn,)
inf V h20
vrh+ + 2T,
Σx((e) / Xxxy jzb
where C¹ = -Cy @ Hzx)) Cxy.
A final requirement to apply Theorem 10 is that v/() (S,) is sub-root function in This simply follows from the above lemma and the fact that the pointwisc infimum of sub-root functions is a sub-root function. Furthermore, the existence of an upper bound on the fixed point is again guaranteed because it is a sub-root function. In particular, we show the following.
Lemma 9. The fized point of vb(r), denoted as r", is bounded as,
c
25 Vh
4
inf
1x(0")
+
V m
Ax 3>
200 and Op
where {
E (x")))((()""))
[xx, xx, Hx (y, (y "/,' (Aa(C)AACCC)))))))))))))) A AC)i
Xx
To finish the proof, we set = (C22)-1/2Un. and V= (C where Un, and Va, are the solutions to the regularized ERM problem. Note that [n[s(,vv S where E, expectation with respect the empirical measure. Applying Theorem 10, stated in Appendix B, and letting K + yields Theorem 1.
6 Conclusion
In this work, we established finite sample generalization bounds on regularized ERM for functional and kernel CCA. The focus here was on understanding the statistical complexity regularized ERM for kernel CCA. A promising future direction is to study the problem from an algorithmic and computational perspective, in particular when using approximate feature maps based on random Fourier features (Rahimi and Recht, 2007), Nyström's method (Drineas and Mahoney, 2005) with randomized sketching (Yang et al., 2015).
10

---

Published in Transactions on Machine Learning Research (03/2023)
References
Shotaro Akaho. A kernel method for canonical correlation analysis. In Proceedings of International Meeting on Psychometric Sociely (IMPS 2001), 2001.
Zeyuan All and Yuanzhi Li. Doubly accelerated methods for faster cca and generalized eigendecompo- sition. arXiv preprint arXi::
2016.
Proceedings of the 30th International Conference Machine Learning, pages 1247-1255, 2013. Galen Andrew, Raman Arora, Jeff Bilmes, and Karen Livescu. Deep canonical correlation analysis. In
Raman Arora and Karen Liveseu. Multi-view CCA-based acoustic features for phonetic recognition across speakers and domains. In Acoustics, Speech and Signal Processing (ICASSP), 2013 IEEE International Conference on, pages 7135 7139. IEEE, 2013.
Raman Arora, Teodor Vanislavov Marinov, Poorya Mianjy, and Nati Srebro. Stochastic approximation for canonical correlation analysis. In I. Guyon, U. V. Luxburg, S. Bengio, Н. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, editors, Advances in Neural Information Processing Systems 30, pages Curran Associates, Inc., 2017.
Francis R Bach and Michael I Jordan. Kernel independent component analysis. Journal of machine learningg research, 3(Ju)):1-48, 2002.
Charles Baker. Joint measures and cross-covariance operators. Transactions of the American Mathematical Society, 186:273 2299,2999,... 1973.
Peter L Bartlett, Olivier Bousquet, and Shahar Mendelson, Localized rademacher complexities. In International Conference on Computational Learning Theory, pages 44 4--8. Springer, 2002.
Gilles Blanchard, Olivier Bousquet, and Laurent Zwald. Statistical properties of kernel principal component analysis. Machine Learning, 66(2-3):259 294, 2007.
Corinna Cortes, Marius Kloft, and Mehryar Mohri. Learning kernels using local rademacher complexity. In Advances in newral information processing systems, pages 2760 2768, 2013.
Petros Drineas and Michael W Mahoney. On the nyström method for approximating gram matrix for improved kernel-based learning. journal of machine learning research, ((Dec):2153-2177) 2005.
Zengyan Fan and Heng Lian. Minimax convergence rates for kernel eca. Journal of Multivariate Analysis, 150:183 190, 2016.
Kenji Fukumizu, Francis R Bach, and Arthur Gretton. Statistical consistency of kernel canonical correlation analysis. Journal of Machine Learning Research, 8(Feb):361 383, 2007.
Chao Gao, Dan Garber, Nathan Srebro, Jialei Wang, and Weiran Wang. Stochastic canonical correlation analysis. Xixi preprint arXiv:1 702.06333. 2017.
Rong Ge, Chi Jin, Pranccth Netrapalli, Aaron Sidford, et al. Efficient algorithms for largo-scale generalized eigenvector computation and canonical correlation analysis. In International Conference on Machine Learning, pages 2741 2750, 2016.
Anna Gilbert, Ambuj Tewari, and Yitong Sun. But how does it work in theory? linear sym with random features. arXiu preprint arXii:1809.044 2018
CW Groetsch. The theory of tikhonov regularization for fredholm equations. 104p, Boston Pitman Publication, 1984.
David R. Hardoon, Sandor Szedmak, and John Shawe-Tayy Taylor. Canonical correlation analysis: An overview with application to learning methods. Neural computation, 16(12):2639-260) 2664, 2004.
Harold Hotelling. Relations between two sets of variates. Biometrika, (0(3/4)3321-83 377, 1936.
11

---

Published in Transactions on Machine Learning Research (03/2023)
Purushottam Kar and Harish Karnick. Random feature maps for dot product kernels. In Artificial Intelligence and Statistics, pages 583-591, 2012.
Pei Ling Lai and Colin Fyfe. Kernel and nonlinear canonical correlation analysis. International Journal of Neural Systems, 10(05):365 377, 2000.
Thomas Melzer, Michael Reiter, and Horst Bischof. Nonlinear feature extraction using generalized canonical correlation analysis. In International Conference on Artificial Neural Networks, pages 353 360. Springer, 2001.
Shahar Mendelson. On the performance of kernel classes. Journal of Machine Learning Research, 4(Oct): 759 771, 2003.
Ali Rahimi and Benjamin Recht. Random features for large-scale kernel machines. In Advances in newral informalion processing systems, pages 1177-1184, 2007.
M. Reed and B Simon. Methods of modern mathematical physics Functional analysis (academic, new york). Google Scholar, page 151, 1972.
Dino Sejdinovic and Arthur Gretton. What an rkhs?, 2012.
Enayat Ullah, Poorya Mianjy, Teodor Vanislavov Marinov, and Raman Arora. Streaming kernel pea with ö(yn) random features. Advances in Neural Information Processing Systems, 31, 2018.
Alexei Vinokourov, Nello Cristianini, and John Shawe-Taylor Inferring a semantic representation of text via cross-language correlation analysis. Advances in neural information processing systems, 15, 2002.
Alexei Vinokourov, Nello Cristianini, and John Shawe Shawe-Taylor. Inferring a semantic representation of text via cross-language correlation analysis. In Advances in neural information processing systems, pages 1497-1504, 2003.
Weiran Wang, Jialei Wang, Dan Garber, and Nati Srebro. Efficient globally convergent stochastic optimization for canomical correlation analysis. In Advances in Neural Information Processing Systems, pages 766-774, 2016.
Yun Yang, Mert Pilanci, and Martin J Wainwright. Randomized sketches for kernels: Fast and optimal non-parametric regression. Xiv preprint arxio:1501 XXi.:1501.06105 2015.
12

---

Published in Transactions on Machine Learning Research (03/2023)
Supplementary Material
A Preliminaries
A.1 Random variables in Hilbert spaces
We start with briefly discussing probability theory in Hilbert spaces. Let Fxx, px) and Fx, be measurable Hilbert spaces. A random variable in Hx is well-defined if and only if every continuous form (f,x)xx is measurable for all f E Hx. Its expectation is px E Hx if f)xx = =xx [xx, fl v f Hx. The existence and uniqueness of μxx is guaranteod if ||x] < co. We similarly consider the space (yy.Fy. Py) with random variable y. Throughout the paper, we assume that the random variable x has mean Ox Hx,, formally defined as Ex [(x, xxx ()x.f)xx = = f Hx, to simplify the presentation. Similarly, the mean of y is assumed to be Oy-
Definition (Auto-covariance operator). Let x a rundom variable a Hilbert space Hx such that Hx oc, with distribution px Then, the auto- covariance operator of x, denoted as Cx Hx + Hx is defined as, v f.g Hxx,
(f,) / (fx (9,x), xxx dpx(x).
x
Equivalently, Cx = Epx (L(())) x]. Furthermore, Cx self-adjoint, positive and trace class.
We similarly use Cy to denote the auto-covariance operator random variable in Hy.
Let Hx Hy be the product space of Hxx and Hy, and let Fx x Fy be the o-field generated by the product of elements of Fx and Fy. Let p be the joint probability measure on (Hx x Hx Fy) with its marginal/projoction cross-covariance operator (Baker, 1973).
(Hx, Fx) and Fy) being px and py respectively. We now define
Definition 2 (Cross-covariance operator). Let (x,y) be paired random variables in Hx Hy distributed P, such that ||x| Hx <0 and Iyylи, < co. The cross-covariance operator Cxy: Hy Hx is defined as
(J, (xyy)) Ep (J, (9,5)
Equivalently, Cxy == Ep [x (1(Hs.Hx) y]. The adjoint of Cxy, denoted as Crty = Cyx, which is defined similarly.
The existence and uniqueness of bounded auto-covariance and cross-covariance operators is guarantced by Riesz's representation theorem (Reed and Simon, 1972).
A.2 Reproducing Kernel Hilbert Spaces
Let X' C Rd and y C IRdy be finite dimensional data domains corresponding to the two views. Let p be the joint distribution over X y and px and Py denote the marginals. We start with definition of reproducing kernel. Our discussion is in the context of kx but it analogously holds for ky as well.
Definition 3 (Reproducing kernel (Sejdinovic and Gretton, 2012)). Let Hx be Hilbert space of real valued functions over X. A function kx X X - R is called reproducing kernel of Hx, if the following hold,
X, kx(x,) Hx
VXEX, V f Hx, (f, (x, M f(x) (Reproducing property)
The function (x( :) is the representer of the evaluation functional at x. The inner product between two elements can therefore be expressed as (kx(x,) -), (x(x'' +)r kx(xxxx). Moreover, reproducing kernels are always positive definite.
13

---

Published in Transactions on Machine Learning Research (03/2023)
A Reproducing Kernel Hilbert Space, conventionally abbreviated RKHS, is defined as the completion of the linear span of (xx((x.), E X} with respect to the inner product (kx(x,)) .), (x'xxx, = xx(xx, x'). The existence and uniqueness of a reproducing kernel for an RKHS is guaranteed by reireseaprrsnnntaoionn theorem. We point the interested reader to Sejdinovic and Gretton (2012) for more discussion on RKHS.
We now briefly discuss auto-covariance and cross-covariance operators the context of RKHS. As be- fore, we assume that supx (x,xxx)))ll < oo and sup, |Kkyl,, 1ny cc. The auto covariance operator over Hx, Cx Hx + Hx is defined as, (fi, Cx Hx Bax [x) f2(x) Vfi. E Hx equiva- lently, Cx = Epx [kx(x,)) .) BLCHX) kx Similarly, Cy Hy + Hy is defined as, (gi, Cyg2) = Epy (y) 92(v)] Vgi.g2 92 E Hx or equivalently, Cy == Epy [ky(v,-) Bi(H)) ky(y.-)] Furthermore, the cross-covariance operator Cxy : Hy - Hx is defined as, (f. Cxyal = Bp g(y)] or equivalently, Cxy Ep [kx(x,, )) (1HH..H Hy) ky(y,-)] These are easy to see from definitions 1 and 2 and applying reproducing property from definition 3.
Kernel CCA notation. In the context of kernel CCA, we selup the following notation. Let X C Rdx and V dy be finite dimensional data domains corresponding to the two views. Let be the joint distribution over X' y and fx and Py denote the marginals. Let ((x,,))),, n be n data points drawn from p. Let kx and ky be two kernel functions and Hxx and Hy be the RKHS associated with (X, kx) and ()) ky) respectively.
A.3 Local Rademacher Complexity Technique
Rademacher complexity is a data-dependent notion of complexity which captures the richness of a class of real valued functions with respect to the data distribution. It is fundamental concept in statistical lcarning theory and empirical process theory, and enables uniform convergence guarantees for the learning problem. We define it formally below.
Definition 4 (Rademacher Complexity). Let F be a set of functions over X and let px be probability distribution over X For a positive integer n, let X1....... Xn be i.i.d. samples drawn from px and let σ1, 02.02..... .,,,,,,,, on be i.id. samples drawn from Rademacher distribution. The Rademacher complexity of F, denoled by (F), defined as,
(F) = E,,x sup
Σ fxi)
fEF
Local Rademacher complexity technique a concentration of measure tool, introduced in Bartlett al. (2002), which aims to provide finer analysis of the problem. It is motivated from the claim that the hypothesis selected by a learning algorithm usually has low empirical error, and hence looking at the Rademacher complexity of the whole class is wasteful. Bartlett et al. (2002) use the variance of the empirical process to constrain the hypothesis class. In particular, if the variance is upper bounded by a constant multiple of the mean, then the empirical process is well- behaved and admits faster rates. This is formalized in Thcorem 10 (in Section B) which restated from Bartlett et al. (2002).
Local Rademacher complexity technique, therefore, essentially looks at the Rademacher complexity of a smaller subset of functions from the original hypothesis class. Formally, star(F) E [ < <r}) where star(F) {af I E F, E [0, 1]} is the star-hull of F. This technique has been used to derive sharper generalization bounds for various kernel learning problems (Blanchard et al., 2007; Ullah et al., 2018; Cortes et al., 2013; Gilbert et al., 2018). Informally, the rate obtained is usually controlled by the tail decay of the spectrum of a higher order moment. We discuss this in more detail in subsequent soctions.
have (F, R, e
B Proof of the main theorem
We first restate the local Rademacher complexity result from Bartlett al. (2002), which is a key tool in our analysis.
14

---

Published in Transactions on Machine Learning Research (03/2023)
Theorem 10. (Bartlett et al., 2002) Let X be measurable space and let P be probability distribution X. Let 21, 22. be i...d. samples drown from P, let Pn. denote. ils empirical measure, and let for a measurable function f. Let F be a class of functions on X ranging from [-1,1] 1] and assume that there erists some constant B such that for every f F,F BPf. Let vb be sub-root function and let r- be the ftxed point of sh. Suppose that up salisfies
Pf = [<=]] and Pnff== -i
(()) 2 BRAf E star(F))Pf sr}
where star(F) (V E F, E [0, is the star shaped hull of F and RF( E [supyer Ei= ozf(2;)] is the Rademacher complerity of F given n data points from P, then for every K > 0 and 8 > 0, with probability at least e-
K
Pnf + 6K r* + 0(11+5BK)
ffEF
(4)
K
B
n
Also, with probability at least 1 - e
K
6K r"
8(11 + 5BK)
VFFF,P.ff K+1
Pf
(5)
B
Farthermore, if on is data-dependent sub-root function with fired point fr such that
(r) 2(10 B)E, R. star(F) pm s 2r) 2(10 V B + 11)8
n
then with probabilily at least - 2e,, it holds that fr 2 r"; as consequence, Equations (4) and (5) hold with r" replaced by fr
We now start the proof of Theorem 1. As discussed in the proof sketch in Section 5, we decompose the error into three terms, and bound each of them one by one.
E(Un,) Vn.) = =UcVo, C)A(HyHH)) (UGAV C,A. Cx) Cx) L(MD))
Error
+ (UnAVa Vny C1 C) L(HG,HHN
Error
(UCAV Un ViL Cx) HxH
Error 3
The three error terms are bound in Lemmas 11, 14, and 15 respectively. Combining them gives the guarantee stated in Theorem 1. In the following subsections, we give the proofs of the afore-mentioned lemmas.
B.1 Bounding the Error 1
Lemma 11 (Error 1). Error 1 is bounded as,
8k: (UcVe - Ci) Hx) (x)))))))) (C(C)
((AxtVis) +2 +2((Ax+ ? ?)
-
Proof. Note that Ue and Ve are operators corresponding to the first & left and right singular functions of C. Therefore (UeV) C) C) (UGAVC. C.) L(Hy.Hxx is difference of the sum of first is singular values
of C and Cx. That is, (UoVG, C) C) ΣE o,(C) and (UG. C2) L(Hy.Hx)
= (:(C)). We
15

---

Published in Transactions on Machine Learning Research (03/2023)
therefore have,
(UoVe. C)( - -UUG, Cx) L(H,
Σ
(VACCOO--VACCA (ICAC3))
(A,(CC*) A((ACC))
VA.(CO*) VA(CIC)
(A((CC)) - ((GAC))
VA(CC)))
where the first inequality follows because x(CxC3) 2 0. We now apply perturbation bounds, in particular Weyl's inequality to bound the difference of eigenvalues of operators using the norm of their difference. We therefore get
(UcVC, 0) - VUG.VV C2) (166.)))))
|CC - CAC
(C(
|CC0 - CC2 + CO3 C
([C]] + |Cx+C Call
(C)
-101) II-
(C)
(C) (21IC-
-xll I|C -[x]lI
where the second inequality we used the fact that singular values are ordered, in the last inquality that |[C|| < and triangle inequality in others. We now appeal Lemma 12 that bounds ||C-Cx] which completes the proof.
Cx Cxyyy11 and its regularized counterport Cx Assuming C is compact, there difference is bounded as, (Cx + Axxx) 1/2 Cxy (Cy -Ally)
Lemma 12. Given C
|CC Cxll & 2( (>y)
16

---

Published in Transactions on Machine Learning Research (03/2023)
Proof. The proof follows the proof of Lemma 7 in Fukumizu et al. (2007).
|Cxx - CCl
|(Cx +
S [[Cx+ Axxx+++))))//00)(( Ayly) 111 - -y1yy)
+ +|[(xx)1/[xx)((>> (BCx))
Cx 11-1/ -1/2
= |[(Cx+ + +xxx)~xx)-12
Cx 1/2 Cxx(Cx + (yly)
-Cy-1 -1-1/31 |
Cy
= (xlx 1/2 1x Cx 11/2 -1/2
+
= [1(Cx+AxTx> 1/2 1xIxx) 1/2 Ix
- CCy 1/2 (Cy+ + Ax1y))
+||crc> + 121 Isy)
S [[(Cx Axxx) 1/2 -xx)C + C(cc + Ayly)-112 1z)]
where the last inequality follows since |cy + Ayly) 11/2
S for positive Ay. We will now bound the two terms separately. Suppose for the first term, the operator norm is realized for w E Hy, || = and e = Cw. Fukumizu et al. (2007) remarks that the range of C is contained in the closure of the range of Cx. That is, v e {Cw: w E Hy, || < 1) n Closure(Range(CA) ()))) Since Cx is continuous, we have that for any 6 0, there exists E {Cw t E Hy. || S 1) n Range(Cx)) such that ||u rll नllæx S c. Further, there cxists Φ Hy, a Hx such that Ca Cx Plugging this in the first term, get,
((Hy)
((Cx + Ax 1x1x) 1/2 1x )r
Hx
[(Cx + Ax1x) 1/2 1/2 - -Ix Ix)( + -リー (0--)) 6)
Hx
< ((Cx + Axlx) xx1x)=112xxx1 1/2 1x)
x/2xxx/2
Lx)(v - 8) 60/|me + |[((xx + Axlx) -12x) -L)00-
1xx
HX
< (Cx + )xxx) C/2 1/ 1/(((( 1/2 -(Cx +xxxx) 1/2 1/2 1/2
+ [(Cx Axxx) -1/2 1/2 Ix) ||0 -0 Hx
Hx
(Cx + \x - -/22, 1/2// 1/22
Cx (Cx + )x(x))/22
<
+c
Hx
2 2 Cx 1/2
|| 1/2 - (Cx + 1/2
where in the first inequality, we used the triangle inequality, where the second equality follows because (Cx + Xxxx) 11/2 1/2 (Cx + Xxlx) Cx Cx since these operators are commulative i.e. have the same eigenspaces. In the second to last inequality, we use that [((xx + Xx1x) 1/2C 1/2
Lx) < 1 which fol- (((Cx)- VAVV-AAACA)A S
lows because [((Cx [((Cx+xxTx) + AxTx) - 1/2 Ix) max;
vx((x)) -1 max;
VAICx2+Ax
1 as Cx is trace-class so its eigenvalues go to 0. Finally, the last step follows from
Cx 1/2 + -
5
for positive ex and by choosing e = [Cxx + +xxxx) //
Cx 1/2g
| 1/2 (Cx + 1x2x)
Hx
We will now argue that Cx 1/2 r|| < 1. This follows by our assumption that the operator Cx - C, -1/2
17

---

Published in Transactions on Machine Learning Research (03/2023)
is Hilbert-Schmide With some abuse of notation, we have that ||xx x = ||x = -||| Cx 1
Cx Cxx"cxyy _ Cx T5x--Cooe CCyyCy ||ق||| S 1 where the first term bounded by 1 by assumption,
and the second because ||قه|| I 1. Similarly, using the same argument the other term, we get,
C(Cy)/2(Cy + Xyly) 1y)
s Cy / /yy/2 (Cy + )y1x)
- 2 C2 1/2 (Cy + \
Finally using Lemma 13, we get the bound 2(vAx + Vxy). Lemma 13. For aelf-ndjoint trace-class operator Cx and positive Xx
-x 1x1x) S vxx
Proof. Since these operators are commutative,
Cx (Cx + Ax max M (A(())) + Axlx) S Vxx
since the operator being trace class implies that the eigenvalues go to 0.
B.2 Bounding the Error 2
Lemma 14 (Error 2). Error 2 is bounded as
(UnAVV C C2) - C|I < 4h (Vxx+ VTy)
Proof. The first inequality simply follows from Holder's inequality with conjugates Schatten and oo norms, and the second using Lemma 12.
B.3 Bounding the Error 3
Lemma 15 (Error 3). With probability least - 8, Error 3 is bounded as,
12aph
+ 24a
24
(UC.VV.. - -nnVV nn C2)
L(HY.HX)
S inf h20
Σny(e))
Ax
Axddy
vn
Axdy sDH
12a,
22,3 22 log(1/0) Vxxdyn
10a, log(1/0)
Ax
Ax
Proof. The proof follows the application of local Rademacher complexity analysis technique for Kernel PCA Blanchard et al. (2007), with modification ions arising from differences in the problems. We start with the function class
F ==ffuv (x,0) + (UCAVON- UUV, C.. L(Hy,Hx)
1/2 where UC,A- (C2*)
Uc, Vea = (ctT)
1/2
Va and Ca = x &((Hy.Hx) y
VAxAy.
We look at the function class G = TJ, where
20vk From Lemma 17, get that for E G the
range of is contained in [-1,1]. We then show in Lemma 22 that E [f]] s μE [f] where μ Ax
2a,
and
F. Er.sia'a' (/' (a,a") )xx (v.0/22 My for f E G.
ap Ac(C)-Ae+1(0)
18

---

Published in Transactions on Machine Learning Research (03/2023)
From Lemma 16, we have that ||UV* (( I Axdy" Similarly, we also have ||Uc,A V.C.V...llL(HH... S Ax Therefore, we have
UcVe UV L(Hy,HHxx
2 [ToVd /|
L(Hg,,Hx + ((UV"(2(()))
4h
1 Xx
Therefore, we can write,
FS ( (x,)) (T,
Xx }
4k
DE Hx), IIT (1l S
= 7
We will now concern ourselves with the set H. We have
R [ = R (T, Lony, Be, (T,
Cr. Cr. Hx) Cuy L(Ng) (T, (T, L(Hs
where C E L(L Hx)) is defined as = Exy [Cr. @n Hx) which is a convex set and contains origin, star(Fx) is also contained H.
Cz.y] Since the set F is contained in H.
star(F) S
(((..)) 5 + (T, (.CC) DE L(Hy. Hx), IT L(H, S
4k
xx
Moreover,
{g E star(g) [ <r) = (g E star [o-] 3r]
CT + (T, Cay) L(Hy,
I L(Hy, Hx),
4k
[[ S xx S:
(T, (T) L(H,, S ST
We now want to bound the Rademacher Complexity of S, which is Rn(S,) Ex [ supres, E of v:]]-
From Lemma 18, we get that the Rademacher complexity of S, is bounded as follows,
(r,) S [ inf (vh + 27 vn 620
h
Cds(o))
(r() /
Ax
ssh
Note that this sub-root function in r, as the infimum for sub-root functions is sub-root. We now need to upper bound the fixed point of (6(r). Define == == Ax
2ap_ We want,
r' = ((")))
ÇT Vn
VF (Vh+1) 2T, +TV Axxy
k
Exiee)
inh
From Lemma 21, we have that fixed point r* is bounded as
2
2
4
h:
82
inf
Σ Exyle))
120
71
Vn
Axdy
7
19

---

Published in Transactions on Machine Learning Research (03/2023)
Let
2 h
4E Vn V
x(S,
inf h20
Σ (0")") Ax i3h
n
n
Having shown that satisfies all the conditions of Theorem 10, we now apply the theorem. We get that for any K > with probability at least 1 5, U L(Hx, R²), V E L(Hy, IR*) in the feasible set, have,
5TTK) log B[TJu.v] - KEnJU 6Kr* +
K
TE
n
K KEnJV.
6Kr(E, NiT GKgT
11 log
5EK log 87
K
E
n
n
Therefore,
KE,Ju. K-1 +
6Km(g,n) &
6Kg 11 log d
5 log d
E [fu.v] S
n
7n
n
We set U Cx U/2u, and V = Cy 11/2 therefore we get E. s O. where E, is the expectation with respect to the empirical measure. Letting K + 1, we get, with probability at least 1 - 6,
(U.AVV. Un,AV R,A: Cx) L(HY.
6x(5, 66 11 + 5g 6
8
a (0.z)) (0x2))2x(( (v.0)) My
Note that 8= 20p
where ap
Mx
and
Ax
We now substitute these
xx
(An(C)
Ax A 1(0))
28VE
obtain the final bound. We have,
<(S, ki n)
22 +
2T
4
k
inf
Extle))
h20
VTl
Ax
j2h
inf
Eh
2
+
4
k
Σ 21(0))
h20
n
vnl V
Axdy
jzh
2a Ax
40,Vi
k
inf
+
+
22((e))
h20
Ax
va Ax
j>h
Therefore, we get,
(UG.VV. - UnnAV n.A. CA) CA) L(Hy)HHx
Axdyn + 24ap/h
12aph
24
120p + Axdyn
22
10aplogh
< inf h20
Axdyn +
Σnsle')
+
+
Axdy
Vxxdym
Xxdyn
J2h
Lemma 16. If U and V satisfies UCUU = I and V.CVV = Ig, where CA = Cx + AxIx and
Cyy = =Cy + Ayly, then,
k
|U S Axdy
20

---

Published in Transactions on Machine Learning Research (03/2023)
Proof. We have,
= - L(L(Hx.85)
2 Xx (UU
Therefore, get L(CHH..
$ Similarly, can show that |V IV'VIl L(L(H) '/y xx
V
VB
|UUV LOHY (UV", UV L(Hy.Hx
= (U*U, V)
3 ||U*U|IZ(R>) |IV"VIl
bx
where we use the definition of adjoints in the second step and Cauchy-Schwartz inequality in the third step.
Ax
Lemma 17. For any IF the range of f is contained in [-1,1], where 7
29vR
Proof. From Lemma 16, we get that ||UV* ((CH,,H))) 2xpx Similarly, also get ||UC. /
|
((HS)
Ax
We now note that,
(U..Ve.a- - UV" -VV", Cz..) UV*,,r..) I(Hy,HHx
1²
Vc. UV ((Hy),H)
|1C2,y (
(|UGAVO. (
s 288
+1IUV* (LHH
4,3%
Axdy
where the first step we applied Cauchy-Schwartz incquality and in the second step, we used that [[Czelle(H))HH)) || [I alle(Hy)Ax)) S ||0||| Hx Ilullay S 3a. Therefore, we have, (UCAVeA- UV*
C -V. Vxx
28VE
Therefore, since any JE range of I-,, we have for Tf its range 11 The lower bound holds because Uc and Ve correspond to the optimal solution, therefore for any function f F. 0. So, any E TF G -1. -1.
Lemma 18. The Rademacher complexity of Sr, defined as,
4k T L(Hy, Hx), || ( S Ax
S, = ((( (T, Can)
(T, CT)
CT) L(ngMe) -T-
is bounded as follows,
r
Ex(ees)
(S,) S
inf A20
Vrh + 27, |. Axxyy gan
vn
21

---

Published in Transactions on Machine Learning Research (03/2023)
Proof. Note that can write (T, C2.)) (I, Cr.y Cxyy + (T, LCH,HHY) Equiva- lently, we can decompose the function class S, into two classes P. and 2r, defined as,
P. = r (x. (T. Cx)))) (T. Hx) S {r]
and
Q -T (((()))) + (T, CaN (()))()) I (H,, S ,x
4k:
-Exx Cxy Hxx) Cxy)r) H(H S 3r]
By simple application of triangle inequality, we have,
Ri (S,) s (2,
We bound the Rademacher complexities of the sets in Lemma 19 and 20 respectively, From them, we get,
RR,(P)) - V
and
1 inf
h
Rr, S
vrh+20 25 2
/n h20
Xxdy
Combining these, we have,
RS, S V n h20
Vrh + V Axdy inf
Exsee
Lemma 19. The Rademacher complecity of the set Pr, defined as,
P, 7,=T((x,)) (x. (I, (x, (T. (T) LCH ST-2)
is bounded as,
(r,) E
Proof. Since P, contains only constant functions, easily bound its Rademacher complexity. In particular, for set of scalars 7 C IR, we have
sup Z - inf Z
E
sup 2E2
E
sup 2 inf
[|ov|]
2
i=1
(sup Z inf Z) vT
2
22

---

Published in Transactions on Machine Learning Research (03/2023)
where the second step follows from Jensen's inequality, and last step from the fact that || = 1 for Rademacher random variable a. Let f E IR where each co-ordinate is the value of the constant function. Therefore, we have
Ri (P.)
- B
sup
S
SEP, :=1
2 2/n
sup { (I, Crv)) (T, eT) L(Hy,H(x) 5T
r
-
This follows because
(T, CT) LCHY.Hx = R [C T (uo 2 (E (Crr (eCHssP))
from Jensen's incquality.
Lemma 20. The Rademacher complecity of the set 2r, defined as
Q =T (z. + (I, Cr.y Cxy) I ( S
4h Axda
(C- Cxy OL(L(Hy,M.)) Hx)) Cxy)l') L(Hy, ST
is bounded as,
RA (Q,)
1
inf
v
h Xxdy
Enyler s>b
vn 420
Proof- Let di's is be eigenfunctions of C Cxy (L()(Hy,H))) Cxy which form orthonormal basis. For h & rank(("), have
oi (T, Cz.,9: - Cxy) L(Hy,
(T, di) (5))
P3.
as cC.C.. CxP)
321
1=1
L(Hy
(T (0 22(0))
Øj.
Σ
o, (Cziv -C)
Vay(e')
1=1
L(Hy,HHx)
Σ
0j Σ (T, L(H),HH))
(Cr.m -xxy)
jzh
L(Hy,Hxx
1/2
1
TT, (3) (. Hx) 25(0")
as(Cr..gr - -Cxy)
2y(e")
1=1
[(Hy.Hx)
1/2
1/2
+
Σ
T, Φ3)
L(Hy.Hx)
oi (Cr.. - Cxyr)
i=1
I(Hy.Hxx)
1/2
Vr
h
Ø3 Σ
azl cI((Cr Cz..
Cxyr)
)5(en)
1(Ht,,Hxx)
4k
1/2
2
1/2
23
T (Cz..i
Cxty)
Axdyy
L(Hy-Hxx)
23

---

Published in Transactions on Machine Learning Research (03/2023)
where in the third step, we used Cauchy Schwartz inequality. In the fourth step, that
4k
IT (1y
(T,, (T, S
Xx
and
[r. (T. ( Bu (i))) r
(T, (T,T)) L.)
L(Hy.Hx)
Σ Xi(e') (T, (or 0x(Hy.Hx) 6i) 1) ((Hy)HHx
Enee' (r. (T. (1)
(1)) H(Hs,Hx)
E Ai(e)) (T, (1) ST
where the third equality follows from the definition of the outer product. We now look at,
Σ oj (CI,,)- - Cxy), 2 7m1
Ez,y,o
Ex M1 o
Σ of (Czy,8, - -Cxy. (2)
L(Hy,H+x)
= =Ezyy
(Czy.vs - Cxy, (i
==1
(Ozya - Cxxy) (1(H).Hxx (Czy.11 - Crx) di
-E
L(Hy;Hxx)
de Be
(C2s.os - C) (L(H) (Czs.us -C) dii
I(Hy.Hx)
(di, C' C' (1)s.
= =n):(C))
where in the first step, we use Pythagoras theorem by observing that Øi's form an orthonormal basis; and in the second step, we use that fact that for Rademacher variable a, E [o_] = In the fourth step, we use
that = Ex.y [ n Ej= (Cz,,0) - Cxy) @I(Hy.Hx) (Cz,,,, - Cxx)]. and in the fifth step, we use the fact that di is an eigenfunction of C.
Let Gr denote the feasible set of T defined
9, 9- 9-:= TE I
4k S Axdy , CT) ((y.Hx 2p
(T,CT)
24

---

Published in Transactions on Machine Learning Research (03/2023)
We have,
Rm ( (2)
I -Enyoo
sup
Σ o. o (Tt Wi)
f im1
- En, v.o n1
T
sup
Σ
of (I, Czum
Cxy) LxHs
TEG. i=1
h
1/2
2
1/2
7 E
oi (Cr.n - -xxy))
sup LEE
112,8.0
72 j=l
(i((")
1=1
HHx)
4k
1/2
2
1/2
+
Oj
0i (Czz.. - Cxar)
1x
1=1
I(Hy,HHx)
2
1/2
T
1
Eussio
n
oi (Cari - -xx)
)5(C")
11
7
j=1
i=1
L(Hy,Hxx)
1)
1/2
4k
1/2
n
oi (C - -0) -0))²
Exs.o j2b
Σ
Oj
Ax
i=1
I(Hy.Hox)
1
20k
Σ (2
vn
Xy(e")
vxxdy
1
k
Vrh + 2T,
Enyle)) 5>h
Axdy
Since the above holds for all S rank(C') (C') and can be trivially extended h 2 rank((") as 2₂(C") 0 for (ank()"), it therefore holds for the infimum over h. We therefore have,
k 1 inf 1 Rr (2,) S
Σxseer
vn h20
Xxdy 3ith
Lemma 21. The faxed point of vr(),, i.e.
r² ((=))r = Ş
VF= (Vh+1) + 27
2
k
Ex((e))
Vn
Axxdy
juh
is bounded as,
2 h
252V8
48
k Ex(ee)
E2
< 7
inf
#20
71
71
Vm
Ax
n
jzb
Proof. We have,
r²
"=v((r)
VF (Vi++)
+ 2
k
Exele))
nn
V
xxxy
S2h
25

---

Published in Transactions on Machine Learning Research (03/2023)
Consider the quadratic equation avII bs 0, we have,
2
a a+ v a² + 46
2 5
2
2a + +.4 + 2/ a² + 4b)
$ a² 2
where in the last step, we use that geometric mean v arithmetic mean. Plugging it here, we get
T² n
(h (h+1+2VI)
k
Σ>yee) jzh
vi V Axdy
Taking infimum over h we get,
T 72
inf
2
28 V/
4
Exiler
5²
Vn
Axdy
n2
Bagaad (xxx) (vo') (An(C)- (b+1(())
Lemma 22. For any f e, E [ S [.. where μ
20.7 and op Xx
Mxx 1
Proof. Given U, V, define U = (cx²) 1/2
U. U. (c))) 1/2
V. We remind that Uc = (cxx) 1/2
UG and
VC,1 (cxx) VC,, so we get U UC = Tand V Vc, =I. Define the projection Pc,x == UC. Σ uf ((Hy,,Hx) Us and P = UV" D u, LL( or using their singular value decomposition respectively. Let fe G. We first look at E [f]..
E B = R (TCAA -VV Ca.)) 2
L(Hy H.))
JUG.Vo CA UV", (V",B[(Cz,, 0I(Hy, Czww) (UG, UV*))
-UC.AVe UV", CVV,CUUCAVVC -CV" L(HS))(
- -UV.
-I0T1 Hx))
L(Hy,Hx)
(c**) - 1/2
(UGAVON - -UV' Cgty 112
L(Hy,Hxx
(C2x) -1/2
(Pc, PP) (CHD) -1/2
= [[(I)
1(Hl,,7x
|Pcc, - -P11--()(())
Axdy
2
[(IlZIZ(H))M))
(R- (Pc....)
Axdy
2
k
Σ
u
Ca
Ug
(1 Cx (1
Axdy
Hx
Ht
1,1=1
26

---

Published in Transactions on Machine Learning Research (03/2023)
where in the seventh incquality we just expanded ||Pc,> Pll Pll)(H),Hx)) Now, note that
|e L(L0H,MM)))
(c, L(((H, Hxx)
Exyx,'' 3
(Cx. SL(Hy,Hx) Cxy, Cx (((Hy,Hxx Cx ((1H))HHH)))
Exyy,''''
(Cxyy Cx 2 L(Hg)
Exy,,''s'
(x 2 y, x @ y 2 L(Hy Hxx)
Exyx''s'
(x,xx) 6r y ,/m =: ap
Let us now look at [f].
El E (Te.VC. c.a UV' .x,,
L(Hy.H)))
(UG. C. - UVV C.v) -UV,Cxx)
L(HysHHx)
Cxy (C2)) -1/2) PPA--P.(C -1/2
L(Hy.Hx)
(PC.A - -P,CA)
k Σ
(c.(Ca) - -(ui, Cxui)
1=1
Let ui = Ef= u
Cx +ri where r; is orthogonal to Cx x..jE [k] and = E)=1 (v)
Cs + Hy
Hx
where 8; is orthogonal to v5 jj E [k]. Then
(ug, Cxus)
Ui, ugg
Ca
Ug
Ca
ri, Cx
U/, 11
C.
n.eh + +s)
Hxx
Hy
k
Cs )
Cr + ris
2r(Ca) ( U2, 03.)
Cs + Cas:
Ug U1
Hxx
Ha
b
Σ ()(Ca) ( (uss (...
(us Hy
+ (rr. CAsil
Hxx
1=1
27

---

Published in Transactions on Machine Learning Research (03/2023)
The cross terms are zero because Cysy's will be linear combination of u, i lo and orthogonal to Kj.J E [k]] Note that
(ri, Cxsi) S A6+1 (Cx) |1:ll Hx ||si|1z5
k u4 Σ
= -)x11(OA)
Uss u Cs )
Uéa oj C
ug
04
j=l
Hxx
j=l
Hy
Uga u ) ?
=10+1(CA)
1
1xx |
1
Σ
Us. u
/ Hy
j=1
U43 11j
+ و=
(Uss 13
Cs
S {Cx1
Hx
Hy
2
2 Us; uj
2 Viy oi
S (Cx)
1
Σ
Hlx
Hy
S (Cx)
1
Uis uz
( Uii of.))
Hx
Hy
where the first step follows because r; and s; don't include components along the first & u,'s and o respectively. In the fourth and fifth steps, we use that arithmetic mcan 2 geometric mean, and in the last step, we use Cauchy-Schwartz inequality. Plugging this in the previous bound, we gel,
(ug: CAUI) Hxx
A((Ca) (u. u.) 1x
(u. My
+ +
1
Σ ==1
uis uy
(1r Cx
Hx
ny
Moreover,
k Σ
k 1-
E 2
\c(Ca)-
-
(r(Ca)) ((CCa((is
Os u Hx uis (u:
(ur ( C2)
Hyy Hy
+ +
E
uis Mi
C2
Hxx
(us, 15 15 1
1=1
j-1
j=1
* 1
b Σ
Σ M(Ca))
(
Σ'
Uii
u0 Cs ) Hx
(15 Ny
ACW1(Ca)
1-
Σ
Usi u. u.
15 My
nx
j=1
i=1
j=1
2 - - - (Ae(Ca) AK+I
Σ
Uii Uy
Cs
) Hx
{ (f) )
Hy
i==1
= (Ax(CC)) (CA) -cet(C))
h
Σ +=
(us
U1 05
Hxx
Har
where in the second last step, we used that X; 2 du, E [k]] and (1-Eise ( (us u xx ( (5. ny )m) 2 ||rillx ||sillac 2 (see above). Therefore, we get,
E [ 2 (Ax(C>) (C2) k: Σ
(un ug Ox)
( U1s ve )120)
76x
(An(CA) A ( Ax
EE P2)
20p
28

---

Published in Transactions on Machine Learning Research (03/2023)
Let {= Ax
200 For f E 9, let f == ff where F. Therefore,
( E' | E
E [f]
{ - [
2 where μ Ax
29


Reviews:
[{"review_id": "KcyNBigK0F", "reviewer": "Reviewer_fTVa", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "- The motivation of the paper is not clear. The introduction does not convince me that studying Kernel CCA and extending the result to abstract Hilbert spaces is interesting. \n\n- The presentation of the paper is not good. It is almost impossible to follow the paper. In particular, there are lots of notations everywhere in the paper. The relationship between the sections are not clear. For instance in Section 3, we have some subsections on ERM, Generalization error, and then Kernel Duality. It is not clear the connection of these parts.\n\n- Do we have a proof that ERM without regularization fails for CCA problem?\n\n- There are numerous assumptions in Section 3 without discussing the implication and intuitions of the these assumptions. I would suggest that the author should consider some case studies for their general statement.\n\n- In Page 4 of the paper, the authors state many assumption. Then, suddenly before presenting the main result in Theorem 1, the authors state another assumption. I think the organization of the paper can be greatly improved.\n\n- What is C in assumption 1?\n\n- In the statistical learning theory, generalization error usually refers to the difference between the performance of a model on the test data and that of the training data. I am not sure you use the right terminology in the paper. I think in this paper the goal is to analyze \"excess error\".\n\n- numerous typos in the appendix: Appendix A.1 first line has typos. Also there are other typos.  In Theorem 10, you use the probability notations that are not defined anywhere in the paper such as writing the expectation of f(X) under X~P as P[f]. Also, in Theorem 10 there are other typos as well. \n\n- Statement of Theorem 11 in the appendix which is the main result of the paper can be improved. It is almost impossible to parse this theorem. The statement is more than 10 lines. \n ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "\nThis paper studies the problem of  Canonical Correlation Analysis where the goal is, given two vectors X and Y, to find linear combinations of X and Y which have maximum correlation with each other. This problem is well-studied problem in Euclidean case. The main focus of the paper is on obtaining a non-asymptotic excess error guarantee for the case kernelized version of CCA. Also, the authors extend the result to the abstract Hilbert space.\n\nThe algorithm they consider is regularized ERM where we plug the empirical covariance matrices instead of the true ones.\n\n", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "My main request is to improve the organization of the paper. One concrete suggestion is to focus on one instance of kernels for instance Gaussian kernels and discuss the results for this special case. Also, the motivation of the paper should be stated more clearly.", "broader_impact_concerns": "not applicable.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "3UfnbhGcl3", "reviewer": "Reviewer_wHob", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths**: This paper focuses on the important problem of the generalization error analysis of KCCA. And the proposed analysis improves previous arts in some sense.\n\n**Weaknesses**: the presentation of the paper can clearly be improved. Efforts can be made to carefully revise the paper to help readers (myself including one of them) better understand the significance of this work and to position this piece of contribution in the existing literature. Some clarifications are needed, see below.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "In this paper, the authors establish (in Theorem 2) non-asymptotic bounds on the generalization error (in the sense of the objective) for regularized empirical risk minimizer of kernel canonical correlation analysis (KCCA). Results on the more general functional CCA are also given (in Theorem 1), i.e., when the Hilbert spaces of interest are not necessarily RKHS. The results also allow one to obtain guarantees on finite-dimensional (K)CCA (in Corollary 3) that improve previous results of linear CCA.\n\nThe technical results rely on a fine-grained decomposition of the excess error and local Rademacher complexity analysis. ", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Some detailed comments:\n\n* P2 Sec 1.2 Our Contributions: depending on distributional properties OF THE DATA?\n* P3: as \"high confidence\" -> as ``high confidence''\n* The authors said at the end of P4 that \"Observe that the solution to the CCA problem in Eqn. (1) is given by the singular value decomposition (SVD) of C\" and then define U_C and V_C, would the authors make a more precise statement on how they relate to the solution of CCA problem? This is a basic conclusion, but of sufficient significance to be mentioned in the paper I believe.\n* End of P5 \"The regularization above corresponds to shifting the spectrum of the auto-covariance operators so that all eigenvalues are positive\": for lambda_{\\mathcal X}, lambda_{\\mathcal Y} > 0?\n* Section 3.1 in P5: perhaps add a few references here just to provide some context for applying Tikhonov regularization in CCA.\n* Beginning of P6 \"as is standard in statistical machine learning\": perhaps cite a few papers on (optimal or not) n-dependent regularization in a, e.g., kernel ridge regression context.\n* Assumption 1: perhaps point to the defining equation (1) of the operator C somewhere in Assumption 1.\n* Does Theorem 1 need Assumption 1? If yes, this should be stated explicitly IN the theorem statement. Also, Assumption 1 assumes that r.v. x and y are bounded, but Theorem 1 only needs some almost sure boundedness. I feel confused about this.\n* Theorem 1: some explanation is needed here in Theorem 1 on the parameter alpha_\\rho, what are x' and y'? May independent copies of x,y?\n* It would be great to have a table somewhere to summarize previous efforts and to better position this piece of contribution in the existing literature, e.g., to compare with the results in Fukumizu et al., 2007; Fan and Lian, 2016; Gao et al. (2017), etc.\n* The authors argued in P7 that the proposed analysis is stronger than those in Fan and Lian (2016), in the sense that the proposed results cover the case of exponentially decaying eigenvalues. It would be of interest to discuss what novel insight can be obtained with the proposed analysis in this case. For the moment this remains very unclear.\n* End of P7 \"so both decrease with n when lambda = omega (n^{-1/2})\": is this a typo?", "broader_impact_concerns": "This contribution of this paper is mainly theoretical and I do not see any ethical concern to report.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "za5QlvlFPP", "reviewer": "Reviewer_mSDT", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper provides non-asymptotic bounds in terms of convergence in the objective for a well-established estimator. The authors motivated reasonably well the choice of focusing on convergence of the loss rather than of the estimators. Since the paper focuses on a different problem,  the comparison with the state-of-the-art rates may not be completely fair.\n\nThe analysis does not significantly improve upon previous results, and aims to control the excess risk of the CCA estimator rather than the distance between the estimator and the real solution.  Thus, it does not provide new perspectives that could improve practical approaches. In this sense, the paper has low significance and potential impact.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper establishes non-asymptotic generalization error bounds for Kernel Canonical Correlation Analysis (KCCA). \nSpecifically, the bounds are given for the convergence of the objective value, rather than in terms of the estimator which is the standard practice in the literature.\n", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "- CCA is mostly used as an intermediate step to other tasks and therefore it's really not clear what insights we can get by knowing the convergence of the loss.\n\n- There seems to be an error in the proof of Lemma 13. Shouldn't the inequality (line 17, page 17) be CX^{1/2} u = CX^{−1/2}v - (CX^{−1/2}v − CX^{1/2}u)?\n\nTypos: \n- Lemma 13: there -> the\n- 1 is missing in the inequality in Line 11, page 17\n", "broader_impact_concerns": "No", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper provides new results on kernel CCA which would be of interest to some in the ML community. The presentation is suitable.
Decision: Accept (poster)