Efficient Optimization for Sparse Gaussian Process Regression
We propose an efficient optimization algorithm for selecting a subset of training data to induce sparsity for Gaussian process regression. The algorithm estimates an inducing set and the hyperparameters using a single objective, either the marginal likelihood or a variational free energy. The space and time complexity are linear in training set size, and the algorithm can be applied to large regression problems on discrete or continuous domains. Empirical evaluation shows state-ofart performance in discrete cases and competitive results in the continuous case.
Update after reading the authors' rebuttal: 
      Very good paper. I advise the authors, if this paper gets 
      accepted, to update it with the additional information regarding rejection 
      rates and experimental details. ===== 1. Summary This 
      paper presents an efficient algorithm for optimization of inducing points 
      in sparse Gaussian process regression. While popular approaches such as 
      the IVM use heuristic functions (instead of the marginal likelihood) to do 
      this selection, the proposed method uses the marginal likelihood (or the 
      variational free energy) to optimize inducing points and GP 
      hyper-parameters jointly. Other approaches that achieve this such as the 
      SPGP framework of Snelson or the variational approach by Titisias focus on 
      continuous inputs, while the proposed approach is more suitable for 
      discrete inputs where continuous optimization of inducing points is not 
      feasible. The paper extends the Cholesky with Side Information 
      (CSI) method of Bach and Jordan to the Gaussian process regression case. 
      In particular, it exploits the observation that it is possible to use the 
      partial Cholesky factorization as a representation of the approximating 
      covariance in the GP. Efficient learning of inducing points is done by 
      updating the corresponding matrices in the factorization and by 
      approximating the reduction in cost of the objective function (marginal 
      likelihood or free energy). Results are shown on several realistic 
      datasets with suitable comparisons to standard baselines such as IVM, 
      Random and SPGP showing the benefits of their approach, specially in the 
      discrete input case. 2. Quality The paper is 
      technically sound as it builds upon previous results shown by Bach and 
      Jordan (the CSI method) for kernel methods. The claims are supported by 
      the corresponding derivations of the updates and the approximations 
      required in order to achieve the claimed computational costs. The 
      experimental results also strongly support that the proposed method is 
      faster than other methods such as CSI, the variational framework of 
      Titsias and more effective than other approaches such as random selection 
      and IVM. 3. Clarity The paper is generally well 
      written providing the detail of the updates necessary for swapping 
      inducing points and the actual optimization algorithm used for the overall 
      optimization framework. However, it would be useful to clarify the 
      following issues: (a) In section 3.1 there is a small k <= m 
      mentioned in the factored representation (see e.g. line 137) that affects 
      the partial Cholesky factorization and the subsequent QR factorization. 
      However, this k seems to disappear in the following sections. Is this 
      parameter relevant? if So, how is it set in the experiments? 
      (b) The introduction of the "informative pivots" seems quite 
      crucial in the fast approximate reduction. However, this means that if one 
      were to use this approximation then the method would be optimizing a 
      different objective function. While section 3.4 explains that this fast 
      approximation is only used to consider the candidates for inclusion and 
      that the actual inclusion does evaluate the true changes in the objective 
      function, it is unclear how good this approximation is at selecting good 
      candidates. In other words, what rejection rates are usually observed 
      during optimization? (c) Figure 1 needs improvement. The axes are 
      not square (with different numerical bounds) and the labels are very 
      small. (d) More details in the experiments are required. For 
      example, lines 293-294 mention that swapping inducing points at every 
      epoch is unnecessary. How often are the inducing points updated? what 
      about hyper-parameters? (e) It is unclear why IVM is more 
      expensive than the proposed method as shown in Figure 3 (a). This is 
      probably related to item (d) above. (f) More analysis in the 
      experiments is needed. Why SPGP is better in terms of predictive 
      likelihood as shown in Figure 5? (g) (Minor): The end of line 
      174 may need rephrasing: "same for the updating with j" looks like an 
      incomplete sentence. 4. Originality The paper 
      addresses the well stablished problem of sparsification of GP regression 
      via inducing points. It mainly extends the results of Bach and Jordan to 
      the sparse Gaussian process regression case. However, it does differ 
      substantially from previous approaches in how it selects these inducing 
      points and how they can be learned efficiently (and jointly with 
      hyper-parameters) while optimizing a single objective function such as the 
      marginal likelihood. 5. Significance The results are 
      important in that this may establish a superior baseline in terms of 
      inducing selection methods for GP regression. The scalability of such 
      methods is, however, still an issue for these types of algorithms to be 
      used by practitioners on large datasets.