Learning with high-dimensional data

Abstract

This thesis is divided into three parts. In the first part we introduce a framework that allows us to investigate learning scenarios with restricted access to the data. We use this framework to model high-dimensional learning scenarios as an infinite-dimensional one in which the learning algorithm has only access to some finite-dimensional projections of the data. Finally, we provide a prototypical example of such an infinite-dimensional classification problem in which histograms can achieve polynomial learning rates. In the second part we present some individual results that might by useful for the investigation of kernel-based learning methods using Gaussian kernels in high- or infinite-dimensional learning problems. To be more precise, we present log-covering number bounds for Gaussian reproducing kernel Hilbert spaces on general bounded subsets of the Euclidean space. Unlike previous results in this direction we focus on small explicit constants and their dependence on crucial parameters such as the kernel width as well as the size and dimension of the underlying space. Afterwards, we generalize these bounds to Gaussian kernels defined on special infinite-dimensional compact subsets of the sequence space ℓ_2. More precisely, the considered domains are given by the image of the unit ℓ_∞-ball under some diagonal operator. In the third part we contribute some new insights to the compactness properties of diagonal operators from ℓ_p to ℓ_q for p ≠ q.