NYTRO: When Subsampling Meets Early Stopping

2015·Arxiv

Abstract

Abstract

Early stopping is a well known approach to reduce the time complexity for performing training and model selection of large scale learning machines. On the other hand, memory/space (rather than time) complexity is the main constraint in many applications, and randomized subsampling techniques have been proposed to tackle this issue. In this paper we ask whether early stopping and subsampling ideas can be combined in a fruitful way. We consider the question in a least squares regression setting and propose a form of randomized iterative regularization based on early stopping and subsampling. In this context, we analyze the statistical and computational properties of the proposed method. Theoretical results are complemented and validated by a thorough experimental analysis.

1 Introduction

Availability of large scale datasets requires the development of ever more efficient machine learning procedures. A key feature towards scalability is being able to tailor computational requirements to the generalization properties/statistical accuracy allowed by the data. In other words, the precision with which computations need to be performed should be determined not only by the the amount, but also by the quality of the available data.

Early stopping, known as iterative regularization in inverse problem theory (Engl et al., 1996; Zhang and Yu, 2005; Bauer et al., 2007; Yao et al., 2007; Caponnetto and Yao, 2010), provides a simple and sound implementation of this intuition. An empirical objective function is optimized in an iterative way with no explicit constraint or penalization and regularization is achieved by suitably stopping the iteration. Too many iterations might lead to overfitting, while stopping too early might result in oversmoothing (Zhang and Yu, 2005; Bauer et al., 2007; Yao et al., 2007; Caponnetto and Yao, 2010). Then, the best stopping rule arises from a form of bias-variance trade-off (Hastie et al., 2001). Towards the discussion in the paper, the key observation is that the number of iterations controls at the same time the computational complexity as well as the statistical properties of the obtained learning algorithm (Yao et al., 2007). Training and model selection can hence be performed with often considerable gain in time complexity.

Despite these nice properties, early stopping procedures often share the same space complexity requirements, hence bottle necks, of other methods, such as those based on variational regularization `a la Tikhonov (see Tikhonov, 1963; Hoerl and Kennard, 1970). A natural way to tackle these issues is to consider randomized subsampling/sketching approaches. Roughly speaking, these methods achieve memory and time savings by reducing the size of the problem in a stochastic way (Smola and Sch¨olkopf, 2000; Williams and Seeger, 2000). Subsampling methods are typically used successfully together with penalized regularization. In particular, they are popular in the context of kernel methods, where they are often referred to as Nystr¨om approaches and provide one of the main methods towards large scale extensions (Smola and Sch¨olkopf, 2000; Williams and Seeger, 2000; Zhang et al., 2008; Kumar et al., 2009; Li et al., 2010; Dai et al., 2014; Huang et al., 2014; Si et al., 2014).

In this paper, we ask whether early stopping and subsampling methods can be fruitfully combined. With the context of kernel methods in mind, we propose and study NYTRO (NYstr¨om iTerative RegularizatiOn), a simple algorithm combining these two ideas. After recalling the properties and advantages of different regularization approaches in Section 2, in Section 3 we present in detail NYTRO and our main result, the characterization of its generalization properties. In particular, we analyze the conditions under which it attains the same statistical properties of subsampling and early stopping. Indeed, our study shows that while both techniques share similar, optimal, statistical properties, they are computationally advantageous in different regimes and NYTRO outperforms early stopping in the appropriate regime, as discussed in Section 3.3. The theoretical results are validated empirically in Section 4, where NYTRO is shown to provide competitive results even at a fraction of the computational time, on a variety of benchmark datasets.

2 Learning and Regularization

In this section we introduce the problem of learning in the fixed design setting and discuss different regularized learning approaches, comparing their statistical and computational properties. This section is a survey that might be interesting in its own right, and reviews several results providing the context for the study in the paper.

2.1 The Learning Problem

We introduce the learning setting we consider in the paper. Let be the input space and the output space. Consider a fixed design setting (Bach, 2013) where the input

points are fixed, while the outputs are given by

where is a fixed function and are random variables. The latter can be seen seen as noise and are assumed to be independently and identically distributed according to a probability distribution with zero mean and variance . In this context, the goal is to minimize the expected risk, that is

where H is a space of functions, called hypothesis space. In a real applications, unknown and accessible only by means of a single realization training set and an approximate solution needs to be found. The quality of a solution f is measured by the excess risk, defined as

We next discuss estimation schemes to find a solution and compare their computational and statistical properties.

2.2 From (Kernel) Ordinary Least Square to Tikhonov Regularization

A classical approach to derive an empirical solution to Problem (1) is the so called empirical risk minimization

space

induced by a positive definite kernel (see Sch¨olkopf and Smola, 2002). In this case Problem (6) corresponds to the Kernel Ordinary Least Squares (KOLS) and has the closed form solution

for all denotes the pseudo-inverse of the empirical kernel matrix . The cost for computing the coefficients in memory and in time, where is the cost for computing K and the cost for obtaining its pseudo-inverse. Here q(X) is the cost of evaluating the kernel function. In the following, we are concerned with the dependence on n and hence view q(X) as a constant.

The statistical properties of KOLS, and related methods, can be characterized by suitable notions of dimension that we recall next. The simplest is the full dimension, that is

which measures the degrees of freedom of the kernel matrix. This latter quantity might not be stable when K is ill-conditioned. A more robust notion is provided by the effective dimension

Indeed, the above quantity can be shown to be related to the eigenvalue decay of K (Bach, 2013; Alaoui and Mahoney, 2014) and can be considerably smaller than , as discussed in the following. Finally, consider

Aside from the above notion of dimensionality, the statistical accuracy of empirical least squares solutions depends on a natural form of signal to noise ratio defined next. Note that the function that minimizes the excess risk in H is given by

Provided with the above definitions, we can recall a first basic results characterizing the statistical accuracy of KOLS.

Theorem 1. Under the assumptions of Section 2.1, the following equation holds,

The above result shows that the excess risk of KOLS can be bounded in terms of the full dimension, the noise level and the number of points. However, in general empirical risk minimization does not provide the best results and regularization is needed. We next recall this fact, considering first Tikhonov regularization, that is the Kernel Regularized Least Squares (KRLS) algorithm given by,

The above algorithm is a penalized empirical risk minimization problem. The representer theorem (Sch¨olkopf and Smola, 2002) shows that Problem (6) can be restricted to

Indeed, a direct computation shows that the solution of Problem (6) is

for all . The intuition that regularization can be beneficial is made precise by the following result comparing KOLS and KRLS.

Theorem 2. Let . The following inequalities hold,

We add a few comments. First, as announced, the above result quantifies the benefits of regularization. Indeed, it shows that there exists a for which the expected excess risk of KRLS is smaller than the one of KOLS. As discussed in Table 1 of Bach (2013), if and the kernel is sufficiently “rich”, namely universal (Micchelli et al., 2006), then be less than a fractional power of

Second, note that the choice of the regularization parameter depends on a form of signal to noise ratio, which is usually unknown. In practice, a regularization path1 is computed and then a model selected or found by aggregation (Hastie et al., 2001). Assuming the selection/aggregation step to have negligible computational cost, the complexity of performing training and model selection is then in memory and in time. These latter requirements can become prohibitive when n is large and the question is whether the same statistical accuracy of KRLS can be achieved while reducing time/memory requirements.

2.3 Early Stopping and Nystr¨om Methods

In this section, we first recall how early stopping regularization allows to achieve the same statistical accuracy of KRLS with potential saving in time complexity. Then, we recall how subsampling ideas can be used in the framework of Tikhonov regularization to reduce the space complexity with no loss of statistical accuracy.

Iterative Regularization by Early Stopping The idea is to consider the gradient descent minimization of Problem 3 for a fixed number of steps t. The corresponding algorithm is then

where . Note that in the above algorithm regularization is not achieved by explicit penalization or imposing constraints, and the only tuning parameter is the number of steps. Indeed, as shown next, the latter controls at the same time the computational complexity and statistical accuracy of the algorithm. The following theorem compares the expected excess error of early stopping with the one of KRLS.

Theorem 3. When the following holds

The above theorem follows as a corollary of our main result given in Theorem 5 and recovers results essentially given in Raskutti et al. (2014). Combining the above result with Theorem 2, and setting , we have that

The statistical accuracy of early stopping is essentially the same as KRLS and can be vastly better than a na¨ıve ERM approach. Note that the cost of computing the best possible solution with early stopping is . Thus, the computational time of early stopping is proportional to the signal to noise ratio. Hence, it could be much better than KRLS for noisy problems, that is when SNR is small. The main bottle neck of early stopping regularization is that it has the same space requirements of KRLS. Subsampling approaches have been proposed to tackle this issue.

Subsampling and Regularization Recall that the solution of the standard KRLS problem belongs to . A basic idea (see Smola and Sch¨olkopf, 2000) is to consider Nystr¨om KRLS (NKRLS), restricting Problem (6) to a subspace

Here is a subset of the training set and . It is easy to see that the corresponding solution is given by

for all is the pseudoinverse, and . A more efficient formulation can also be derived. Indeed, we rewrite Problem (6), restricted to

where in the last step we performed the change of variable matrix such that is the rank of . Then, we can obtain the following closed form expression,

(see Prop. 1 in Section B of the appendix for a complete proof). This last formulation is convenient because it is possible to compute economic QR decomposition of upper triangular matrix and an invertible triangular matrix that is the Cholesky decomposition of , the complexity of Nystr¨om KRLS is then O(nm) in space and in time. The following known result establishes the statistical accuracy of the solution obtained by suitably choosing the points in M.

Theorem 4 (Theorem 1 of Bach (2013)). Let be a subset of the training set uniformly chosen at random. Let ˜be as in Equation (12) and ¯Equation (8) for any

with ˜, then the following holds

The above result shows that the space/time complexity of NKRLS can be adaptive to the statistical properties of the data while preserving the same statistical accuracy of KRLS. Indeed, using Theorem 2, we have that

requiring in memory and in time. Thus, NKRLS is more efficient with respect to KRLS when ˜is smaller than , that is when the problem is mildly complex.

Given the above discussion it is natural to ask whether subsampling and early stopping ideas can be fruitfully combined. Providing a positive answer to this question is the main contribution of this paper that we discuss next.

3 Proposed Algorithm and Main Results

We begin by describing the proposed algorithm incorporating the Nystr¨om approach described above in iterative regularization by early stopping. The intuition is that the algorithm thus obtained could have memory and time complexity adapted to the statistical accuracy allowed by the data, while automatically computing the whole regularization path. Indeed, this intuition is then confirmed through a statistical analysis of the corresponding excess risk. Our result indicates in which regimes KRLS, NKRLS, Early Stopping and NYTRO are preferable.

3.1 The Algorithm

NYTRO is obtained considering a finite number of iterations of the gradient descent minimization of the empirical risk in Problem (2) over the space in Equation (11). The algorithm thus obtained is given by,

of computing , the total cost for the above algorithm is O(nm) in memory and

In the previous section, we have seen that NKRLS has an accuracy comparable to the one of the standard KRLS under a suitable choice of m. We next show that, under the same conditions, the accuracy of NYTRO is comparable with the ones of KRLS and NKRLS, for suitable choices of t and m.

3.2 Error Analysis

We next establish excess risk bounds for NYTRO by providing a direct comparison with NKRLS and KRLS.

Theorem 5 (NYTRO and NKRLS). Let be a subset of the training set. Let be the NYTRO solution as in Equation (17), ˜the NKRLS solution as in Equa- tion (12). When (for example ) the following holds

Note that the above result holds for any and any selection strategy of the Nystr¨om subset M. The proof of Theorem 5 is different from the one of Theorem 4 and is based only on geometric properties of the estimator and tools from spectral theory and

Figure 1: The graph represents the family of learning problems parametrized by the dimensionality ˜d and the signal-to-noise ratio SNR (see Equations 4, 5). The four regions represent the regimes where different some algorithm are faster than the others. Purple: NYTRO is faster, Blue: Early Stopping is faster, Orange: KRLS is faster, Yellow: NKRLS is faster – see Section 3.3.

inverse problems (see Engl et al., 1996). In the next corollary we compare NYTRO and KRLS, by combining Theorems 4 and 5, hence considering M to be chosen uniformly at random from the training set.

Corollary 1. Let be chosen as

Let ¯be the KRLS solution as in Equation 8 and be the NYTRO solution. When the subset M is chosen uniformly at random from the training set, the following holds

The above result shows that NYTRO can achieve essentially the same results as KRLS. In the next section we compare NYTRO to the other regularization algorithms introduced so far, by discussing how their computational complexity adapts to the statical accuracy in the data. In particular, by parametrizing the learning problems with respect to their dimension and their signal-to-noise ratio, we characterize the regions of the problem space where one algorithm is more efficient than the others.

3.3 Discussion

In Section 2 we have compared the expected excess risk of different regularization algorithms. More precisely, we have seen that there exists a suitable choice of , where SNR is the signal-to-noise ratio associated to the learning problem, such

Table 1: Specifications of the Datasets Used in Time-accuracy Comparison Experiments. is the Bandwidth of the Gaussian Kernel.

that the expected risk of KRLS is smaller than the one of KOLS, and indeed potentially much smaller. For this reason, in the other result, statistical accuracy of the other methods was directly compared to that of KRLS with

We exploit these results to analyze the complexity of the algorithms with respect to the statistical accuracy allowed by the data. If we choose then combining Theorem 2 with Corollary 1 and with Theorem 4, respectively, we see that the expected excess risk of both NYTRO and NKRLS is in the same order of the one of KRLS. Both algorithms have a memory requirement of O(nm) (compared to KRLS), but they differ in their time requirement. For NYTRO we have while for NKRLS it is . Now note that ˜by definition is bounded by

thus, by comparing the two computational times, we can identify two regimes

To illustrate the regimes in which different algorithms can be preferable from a computational point of view while achieving the same error as KRLS with (see Figure 1), it is useful to parametrize the family of learning problems with respect to the signal-to-noise ratio defined in Equation (5) and to the dimensionality of the problem ˜in Equation (4). We choose ˜d as a measure of dimensionality with respect to ˜d directly affects the computational properties of the analyzed algorithms. In Figure 1, the parameter space describing the learning problems is partitioned in regions given by the curve that separates the subsampling methods from the standard methods and the curve that separates the iterative from Tikhonov methods.

As illustrated in Figure 1, NYTRO is preferable when SNR , that is when the problem is quite noisy. When SNR > 1, then NYTRO is faster when the dimension of the problem is sufficiently large. Note that, in particular, the area of the NYTRO region on SNR > 1 increases with n, and the curve is quite flat when n is very large. On the opposite extremes we have early stopping and NKRLS. Indeed, one is effective when the

Table 2: Time-accuracy Comparison on Benchmark Datasets.

dimensionality is very large, while the second when it is very small. There is a peak around SNR for which it seems that the only useful algorithm is NKRLS when the dimensionality is sufficiently large. The only region where KRLS is more effective is when SNR and the dimensionality is close to n.

In the next section, the theoretical results are validated by an experimental analysis on benchmark datasets. We add one remark first.

Remark 1 (Empirical parameter choices and regularization path). Note that an important aspect that is not covered by Figure 1 is that iterative algorithms have the further desirable property of computing the regularization path. In fact, for KRLS and NKRLS computations are slowed by a factor of is the discrete set of cross-validated s. This last aspect is very relevant in practice, because the optimal regularization parameter values are not known and need to be found via model selection/aggregation.

4 Experiments

In this section we present an empirical evaluation of the NYTRO algorithm, showing regimes in which it provides a significant model selection speedup with respect to NKRLS and the other exact kernelized learning algorithms mentioned above (KOLS, KRLS and Early Stopping). We consider the Gaussian kernel and the subsampling of the training set points for kernel matrix approximation is performed uniformly at random. All experiments have been carried out on a server with 12 2.10GHz IntelCPUs and 132 GB of RAM.

We compare the algorithms on the benchmark datasets reported in Table 12. In the table we also report the bandwidth parameter adopted for the Gaussian kernel computation. Following (Si et al., 2014), we measure performance by the root mean squared error (RMSE). Note that for the YearPredictionMSD dataset outputs are scaled in [0, 1].

Figure 2: Training Time of NKRLS and NYTRO on the cpuSmall Dataset as the Subsampling Level m Varies Linearly Between 100 and 4000. Experiment With 5 Repetitions. Mean and Standard Deviation Reported.

For all the algorithms, model selection is performed via hold-out cross validation, where the validation set is composed of 20% of the training points chosen uniformly at random at each trial. We select the regularization parameter for NKRLS between 100 guesses logarithmically spaced in, by computing the validation error for each model and choosing the associated with the lowest error. NYTRO’s regularization parameter is the number of iterations t. We select the optimal by considering the evolution of the validation error. As an early stopping rule, we choose an iteration such that the validation error ceases to be decreasing up to a given threshold chosen to be the 5% of the relative RMSE. After model selection, we evaluate the performance on the test set. We report the results in Table 2 and discuss them further below.

Time Complexity Comparison We start by showing how the time complexity changes with the subsampling level m, making NYTRO more convenient than NKRLS if m is large enough. For example, consider Figure 2. We performed training on the (n = 6554, d = 12), with m spanning between 100 and 4000 at 100-points linear intervals. The experiment is repeated 5 times, and we report the mean and standard deviation of the NYTRO and NKRLS model selection times. We consider 100 guesses for , while the NYTRO iterations are fixed to a maximum of 500. As revealed by the plot, the time complexity grows linearly with m for NYTRO and quadratically for NKRLS. This is consistent with the time complexities outlined in Sections 2 and 3 (for NKRLS and for NYTRO).

Time-accuracy Benchmarking We also compared the training time and accuracy performances for KRLS, KOLS, Early Stopping (ES), NKRLS and NYTRO, reporting the selected hyperparameter (for KRLS and NKRLS, for ES and NYTRO), the model selection time and the test error in Table 2. All the experiments are repeated 5 times. The standard deviation of the results is negligible. Notably, NYTRO achieves comparable or superior predictive performances with respect to its counterparts in a fraction of the model selection time. In particular, the absolute time gains are most evident on large scale datasets such as Covertype and YearPredictionMSD, for which a reduction of an order of magnitude in cross-validation time corresponds to saving tens of minutes. Note that exact methods such as KOLS, KRLS and ES cannot be applied to such large scale datasets due to their prohibitive memory requirements. Remarkably, NYTRO’s predictive performance is not significantly penalized in these regimes and can even be improved with respect to other methods, as in the Covertype case, where it requires 90% less time for model selection.

5 Acknowledgements

The work described in this paper is supported by the Center for Brains, Minds and Machines (CBMM), funded by NSF STC award CCF-1231216, and FIRB project RBFR12M3AC, funded by the Italian Ministry of Education, University and Research.

References

Ahmed Alaoui and Michael W Mahoney. Fast Randomized Kernel Methods With Statistical Guarantees. arXiv, 2014.

Francis Bach. Sharp analysis of low-rank kernel matrix approximations. In COLT, volume 30 of JMLR Proceedings, pages 185–209. JMLR.org, 2013.

F. Bauer, S. Pereverzev, and L. Rosasco. On regularization algorithms in learning theory. Journal of complexity, 23(1):52–72, 2007.

A. Caponnetto and Yuan Yao. Adaptive rates for regularization operators in learning the- ory. Analysis and Applications, 08, 2010.

Bo Dai, Bo Xie 0002, Niao He, Yingyu Liang, Anant Raj, Maria-Florina Balcan, and Le Song. Scalable Kernel Methods via Doubly Stochastic Gradients. In NIPS, pages 3041–3049, 2014.

Heinz Werner Engl, Martin Hanke, and Andreas Neubauer. Regularization of inverse problems, volume 375. Springer Science & Business Media, 1996.

Trevor Hastie, Robert Tibshirani, Jerome Friedman, and James Franklin. The elements of statistical learning: data mining, inference and prediction. The Mathematical Intelligencer, 27(2):83–85, 2001.

A. E. Hoerl and R. W. Kennard. Ridge Regression: Biased Estimation for Nonorthogonal Problems. Technometrics, 12:55–67, 1970.

Po-Sen Huang, Haim Avron, Tara N. Sainath, Vikas Sindhwani, and Bhuvana Ramabhad- ran. Kernel methods match Deep Neural Networks on TIMIT. In ICASSP, 2014.

Sanjiv Kumar, Mehryar Mohri, and Ameet Talwalkar. Ensemble Nystrom Method. In NIPS, pages 1060–1068. Curran Associates, Inc., 2009.

Mu Li, James T. Kwok, and Bao-Liang Lu. Making Large-Scale Nystr¨om Approximation Possible. In ICML, pages 631–638. Omnipress, 2010.

Charles A Micchelli, Yuesheng Xu, and Haizhang Zhang. Universal kernels. The Journal of Machine Learning Research, 7:2651–2667, 2006.

Garvesh Raskutti, Martin J. Wainwright, and Bin Yu. Early Stopping and Non-parametric Regression: An Optimal Data-dependent Stopping Rule. J. Mach. Learn. Res., 15(1): 335–366, January 2014. ISSN 1532-4435.

Ryan Rifkin, Gene Yeo, and Tomaso Poggio. Regularized least-squares classification. Nato Science Series Sub Series III Computer and Systems Sciences, 190:131–154, 2003.

Bernhard Sch¨olkopf and Alexander J. Smola. Learning with Kernels: Support Vector Machines, Regularization, Optimization, and Beyond (Adaptive Computation and Machine Learning). MIT Press, 2002.

Si Si, Cho-Jui Hsieh, and Inderjit S. Dhillon. Memory Efficient Kernel Approximation. In ICML, volume 32 of JMLR Proceedings, pages 701–709. JMLR.org, 2014.

Alex J. Smola and Bernhard Sch¨olkopf. Sparse Greedy Matrix Approximation for Machine Learning. In ICML, pages 911–918. Morgan Kaufmann, 2000. ISBN 1-55860-707-2.

A. N. Tikhonov. On the solution of ill-posed problems and the method of regularization. Dokl. Akad. Nauk SSSR, 151:501–504, 1963.

Christopher Williams and Matthias Seeger. Using the Nystr¨om Method to Speed Up Kernel Machines. In NIPS, pages 682–688. MIT Press, 2000.

Yuan Yao, Lorenzo Rosasco, and Andrea Caponnetto. On Early Stopping in Gradient De- scent Learning. Constructive Approximation, 26(2):289–315, 2007. ISSN 0176-4276. doi: 10.1007/s00365-006-0663-2.

Kai Zhang, Ivor W. Tsang, and James T. Kwok. Improved Nystr¨om Low-rank Approxima- tion and Error Analysis. ICML, pages 1232–1239. ACM, 2008. doi: 10.1145/1390156. 1390311.

Tong Zhang and Bin Yu. Boosting with early stopping: convergence and consistency. Annals of Statistics, pages 1538–1579, 2005.

A Proofs

Proof of Theorem 2. By applying Prop. 2 to the estimator of Equation 3 we have . Now note that by definition, Tr, therefore

Now let be the eigen-decomposition of K, with U an orthonormal matrix and a diagonal matrix with the projection operator on the range of K. By applying Prop. 2 to the estimator of Equation (3) and considering that we have

where the last step is due to the fact that . By defining and assuming

Proof of Theorem 3. It is an application of Theorem 5 when we select the whole training set (m = n) for the Nystr¨om approximation. In that case, the expected excess risks of Nystr¨om KRLS and NYTRO are just equal to the ones of KRLS and Early Stopping, indeed when m = n we have that . If we call ¯-matrices for the two algorithms (see Prop. 2) and

Proof of Theorem 5. In the following we assume without loss of generality that the selected points ˜are the first m points in the dataset. In Prop. 2 we have seen that the behavior of an algorithm in a fixed design setting is completely described by a matrix Q = KC when the coefficients of the estimator are of the form Cy. We now find the associated Q for NYTRO, that is . By solving the recursion of Equation (17), we have for any

Rewriting of Now we rewrite in a suitable form to bound the bias and variance errors. First of all, we apply Prop. 3 to with , we have that

where . Now note that

Bound of the Bias Now we are going to bound the bias for NYTRO. Let and

and . Note that the third step is due to the fact that range is symmetric. Therefore, Ph(Z) = h(Z)P as a consequence of Prop. 3 for any spectral function be the singular values of Z, we have

We have . Indeed, for , while for

therefore , the function . Now we rewrite w a bit. First of all, note that

with . The fact that implies that

Let us now focus on Trbe its eigenvalue decomposition with U an orthonormal matrix and

where we applied many times Prop. 3 and the fact that the trace is invariant to unitary transforms. Thus

The Expected Excess Risk for Nystr¨om KRLS The Nystr¨om KRLS estimator with linear kernel is a function of the form

with . Now, by applying Prop. 3 we have

where the last step is due to the same reasoning as in the bound for the bias of NYTRO. Finally, by applying twice Prop. 2 and calling , we have that

for . Now the choice is valid, indeed

Proof of Corollary 1. Theorem 5 combined with Theorem 1 of Bach (2013).

B Some Useful Results

Proposition 1. With the notation of Section 2.3, let . Then, for any is characterized by Equation 16.

Proof. By Equation 7.7 of Rifkin et al. (2003) we have that

where the last step is due to Prop. 3.

Proposition 2. Let be a kernel function on be the given points and be the labels of the dataset. For any function of the form f(x) = independent from y, the following holds

with the kernel matrix, the projection operator on the range of K.

Proof. A function is of the form . If we compute it on a point of the dataset with . Note that

Now note that and that inf, then the excess risk can be rewritten as

Expected Excess Risk We focus on the expectation of R with respect to the dataset for linear functions that depend linearly on the observed labels y. Indeed we have

Here the third step is due to any vector a, b. The last term in the third step vanishes due to the fact that mean random variable, moreover note that , therefore

Proposition 3 (Spectral functions). Let be a continuous function and symmetric with be its eigenvalue decomposition with an orthonormal matrix, a diagonal matrix, then

designed for accessibility and to further open science