Scalable Log Determinants for Gaussian Process Kernel Learning
For applications as varied as Bayesian neural networks, determinantal point processes, elliptical graphical models, and kernel learning for Gaussian processes (GPs), one must compute a log determinant of an n × n positive definite matrix, and its derivatives -leading to prohibitive O(n 3 ) computations. We propose novel O(n) approaches to estimating these quantities from only fast matrix vector multiplications (MVMs). These stochastic approximations are based on Chebyshev, Lanczos, and surrogate models, and converge quickly even for kernel matrices that have challenging spectra. We leverage these approximations to develop a scalable Gaussian process approach to kernel learning. We find that Lanczos is generally superior to Chebyshev for kernel learning, and that a surrogate approach can be highly efficient and accurate with popular kernels.
Summary of the paper:
	This paper describes two techniques that can be used to estimate (stochastically) the log determinant of a positive definite matrix and its gradients. The aim is to speed up the inference process several probabilistic models that involve such computations. The example given is a Gaussian Process in which the marginal likelihood has to be maximized to find good hyper-parameters. The methods proposed are based on using the trace of the logarithm of a matrix to approximate the log determinant. Two techniques are proposed. The first one based on Chevyshev polynomials and the second one based on the Lanczos algorithm. The first one seems to be restricted to the case in which the eigenvalues lie in the interval [-1,1]. The proposed method are compared with sparse GP approximations based on the FITC approximation and with related methods based on scaled eigenvalues on several experiments involving GPs.
Detailed comments:
Clarity:
The paper is very well written and all details seem to be clear with a few exceptions. For example, the reader may not be familiar with the logarithm of a matrix and similar advanced algebra operations. There are few typos in the paper also.  In the Eq. above (2) it is not clear what beta_m or e_m are. They have not being defined. It is also known that the Lanczos algorithm is unstable and extra computations have to be done. The authors may comment on these too.
Quality: 
I think the quality of the paper is high. In particular, the authors analyze the method described in several experiments, comparing with other important and related methods. These experiments seem to indicate that the proposed method gives competitive results at a small computational cost.
Originality:
The paper a strong related work section and the methods described seem to be original. 
Significance:
My main concern with this paper is its significance. While it is true that the proposed method allow for a faster evaluation of the log determinant of the covariance matrix and its gradients. One still has to compute such a matrix with squared cost in the number of samples (or squared cost in the number of inducing points, if sparse approximations are used). This limits a bit the practical applicability of the proposed method. Furthermore, it seems that the experiments carried out by the authors involve a single repetition. Thus, there are no error bars in the results and one can not say whether or not the results are statistical significant. The differences with respect to the scaled eigenvalues problems (ref. [32]) in the paper seem very small.