Generalization Bounds andLearning Rates forRegularized Principal
We derive uniform convergence bounds and learning rates for regularized principal manifolds. This builds on previous work of Kegl et al., however we are able to obtain stronger bounds taking advantage of the decomposition of the principal manifold in terms of kernel functions. In particular, we are able to give bounds on the covering numbers which are independent of the number of basis functions (line elements) used. Finally we are able to obtain a nearly optimal learning rate of order O(m ? 1 2 +) for certain types of regularization operators, where m is the sample size and an arbitrary positive constant. A companion paper 4] describes the basic algorithm, details of the implementation and experimental results.