  We introduce a new scalable approximation for Gaussian processes with
provable guarantees which hold simultaneously over its entire parameter space.
Our approximation is obtained from an improved sample complexity analysis for
sparse spectrum Gaussian processes (SSGPs). In particular, our analysis shows
that under a certain data disentangling condition, an SSGP's prediction and
model evidence (for training) can well-approximate those of a full GP with low
sample complexity. We also develop a new auto-encoding algorithm that finds a
latent space to disentangle latent input coordinates into well-separated
clusters, which is amenable to our sample complexity analysis. We validate our
proposed method on several benchmarks with promising results supporting our
theoretical analysis.
