−1 −0.5

Exact Gaussian process (GP) regression is not available for n 10, 000 (O(n3) for learning and O(n) for prediction) Our goal: use the GP framework even for large-scale learning Our contributions 1 Learning and classification in a Bayesian manner with Gaussian processes and histogram intersection kernels (HIK) in sub-quadratic and constant time. 2 Hyperparameter optimization for large-scale datasets with efficient GP marginal likelihood optimization