Generalization of Plaskota's bound for Gaussian process

Note: This paper is an extended version of the manuscript Learning curves for Gaussian process regression: Approximations and bounds by Sollich and Halees. The only dierence is the addition of Appendix B, which gives the derivation of the generalized version of Plaskota's bound. The remainder of the paper has been left in place to provide the proper context.] We consider the problem of calculating learning curves (i.e., average generalization performance) of Gaussian processes used for regression. On the basis of a simple expression for the generalization error, in terms of the eigenvalue decomposition of the covariance function, we derive a number of approximation schemes. We identify where these become exact, and compare with existing bounds on learning curves; the new approximations, which can be used for any input space dimension, generally get substantially closer to the truth. We also study possible improvements to our approximations. Finally, we use a simple exactly solvable learning scenario to show that there are limits of principle on the quality of approximations and bounds expressible solely in terms of the eigenvalue spectrum of the covariance function