Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 3: Weak Reject
review_content: 1) Summary
The manuscript proposes a k-nearest-neighbor (KNN) Gaussian process (GP) approximate inference scheme to render computations more scalable.

2) Quality
Although the application is clear and the methodology is well established, the quality of the submission can be improved by a more thourough empirical evaluation in particular a proper evaluation in terms of runtime, approximation accuracy and comparison to baseline methods.

3) Clarity
The manuscript is reasonably well written and most of the technical and experimental content is accessible. There are some typos and some glitches in the notation. See "Details". There are some open issues regarding the KNN computations. See Questions.

4) Originality
The use of a localized (in the KNN sense) set of inducing inputs to improve GP inference but the impact needs to be better quantified empirically.

5) Significance
The proposed method is aiming at improving the established setting of GP inference. The modification is rather marginal and the empirical evaluation makes it hard to judge the relative merit of the proposal.

6) Reproducibility
The data is from published sources (toy, ebirds, precipitation, digits) and the code for the baseline methods and for the LAIM method itself is available. However, there is no code for the experiments, which makes the results slightly tricky to exactly reproduce.

7) Evaluation
The evaluation does not consider simple baselines like dense GPs or sparse approximations such as FITC and VFE. Also plain NN should be considered.

8) Questions
  A) How do you set the parameter delta?
  B) How are the nearest-neighbors computed in the first place? Does it require computing the dense covariance matrix?
  C) How accurate is the NN computation? How much of the computational effort (percentage) of the overall pipeline is required for the NN computation?
  D) How much better is the proposed approach than directly using NN predictions?
  E) Does "most correlated" in the footnote on page 2 really mean correlation or is it about covariance? The latter would involve a diagonal rescaling of the covariance matrix.

9) Details
  a) Abstract: "Gaussian Processes" -> "Gaussian processes"
  b) Intro: "GP poses a Gaussian prior" -> funny sentence, "with some special "
  c) Intro: "with some special structures" -> fix
  d) Background: "q(f)~N(mu,V)" -> imprecise notation, rather "q(f)=N(mu,V)"
  e) Background, footnote: "distance metrics" -> Are you talking about "distance" or "metric"?
  f) "Experiment" -> "Experiments"
  g) References: capitalization not correct e.g. Gaussian, Fourier, Bayes
review_title: Official Blind Review #2

final_score: rating: 1: Reject
review_content: PAPER SUMMARY:

This paper proposes a fast inference method for Gaussian processes (GPs) that imposes a sparse decomposition on the VI approximation of the posterior GP (for computational efficiency) using the KNN set of each data point. This is further coupled with armortized inference for better scalability. 

NOVELTY & SIGNIFICANCE:

This paper adopts a different approach of characterizing the VI approximation of a GP posterior than original VI approximation that was developed in Titsias (2009): Instead of characterizing the surrogate q(f_I) of p(f_I | Y) for a small collection of inducing inputs, the proposed method characterize q(f) directly where q(f) = int_f_I q(f_I) p(f | f_I)df_I.

This is, however, a somewhat strange direction which, to me, seems to raise extra issues that could have been avoided if one follows the conventional VI approximation:

(1) As the posterior surrogate is now directly over f instead of f_I, the number of variational parameters is now proportional to the data size which requires several (redundant) extra approximations including armortized inference & the lower-bound on the entropy term that admits a sparse decomposition.

(2) This at least creates the armortized and entropy gaps that decrease the expressiveness of the original VI. While I understand that this is in exchange for the ability to encode local information (via KNN) within the surrogate posterior, it is not clear to me why do we need to incur all these computational issues to incorporate such local information.

(3) For example, instead of forcing such local information in the posterior surrogate q(f), we could alternatively let it be reflected in the test conditional p(f_* | f_I, Y_n(*)) such that the test output depends on both the inducing output and a local partition of data (e.g., via K-mean), which has been previously explored in [*] and later incorporated in the conventional VI paradigm of Titsias (2009) without incurring extra intractability [**].

(4) This maintains the dense correlation between data points within the same neighborhood while allowing the VI surrogate to be more concisely specified and independent of the no. of training data points. Furthermore, it also helps avoid the data-bound overhead of computing a KNN per test point. 

[*] Local and global sparse Gaussian process approximations (AISTAT-07)
[**] A distributed variational inference framework for unifying parallel sparse gaussian process regression models (ICML-16)

To summarize, the practical significance of placing such a VI approximation directly on q(f) to encode such (indirectional) local information is, given the above, questionable to me.
Please note that I am not disputing the potential use of this VI form here, which could have been the only way to encode a different (directional) type of information. 
For encoding KNN information, however, it only seems to create more troubles than it solves. 

Minor point: 

The above references, especially [*], should have been cited. 

TECHNICAL SOUNDNESS:

[A] Optimization of the ELBO:

(1) The ordering of data (i.e., the directional information) was mentioned repeatedly in the paper but its importance to the fast approximation was neither explained nor discussed.
(2) The decomposition form of Eq. (6) also raises a question: How do we know that the term inside the log is positive? There seems to be missing information on the constraint of R.

[B] Amortized Inference:

(1) The choice of the GCN seems arbitrary here. I am in fact not sure why GCN is necessary for the inference network & furthermore, GCN also brings to the table another heuristic choice of A.
(2) How do we set the adjacency graph A? 
(3) How do we know what is the right complexity for the GCN?

[C] Complexity: 

The complexity analysis is too informal and lacking fine-grained information. 
Please include a detailed complexity analysis of the training and inference cost in terms of the input dimension, the no. of data points, the size of the neighborhood and the batch size.
It is also necessary to factor in the KNN overhead (e.g., the cost of building the K-D tree for low-dimensional embedding of data & the approximation cost of projecting that information to high-dimensional data)

EXPERIMENT:

The experiment results only show marginal improvement over the baselines, and the size of the dataset for regression is too small. If I read correctly, both have fewer than 20000 data points.
SVGP in particular has been tested on a much larger datasets (AIRLINE, UK Housing) comprising millions of data points -- comparison on such dataset should have been reported. 

Note that the largest dataset used to evaluate the efficiency of fast approximation of GP is on the scale of 6M data points [****]. On that note, eBird and precipitation should not even be considered mid-sized.

To demonstrate the efficiency of local information encoding, comparison with [*] should be reported. There is another class of inducing-point methods that use expectation propagation
that should have been discussed and/or compared with:

[***] A Unifying Framework for Gaussian Process Pseudo-Point Approximations using Power Expectation Propagation (JMLR-18)

[****] Distributed Gaussian Processes (ICML-15)

CLARITY:

The paper is clearly written. 

REVIEW SUMMARY:

This paper adopts a VI approximation that deviates from the conventional form of (Titsias, 2009) to encode the KNN information, which causes extra computational issues (that incurs extra approximations). I find this deviation redundant seeing that the same information could have also been accounted for using the old VI form, which is a lot more computational efficient. I also find the experiment lacking as comparison with fast approximation method such as [*] that incorporate local information is not included. There are also a few technical ambiguities that need to be clarified.

------ Post-Rebuttal Update ------

Thank you for the rebuttal & I have read it in detail. However, it still does not address my concern, which I re-summarize here:

I do not dispute the beneficial of exploiting neighborhood information but my point is we could still leverage the same amount of neighborhood information without going through the trouble of incurring extra steps of approximation due to approximating q(f) instead of q(f_I) -- I think I have elaborated this in points (1) - (4) in my original review -- which also creates the amortized gap. I am also not sure what model reuse means (in this context) and whether it is relevant since it appears somewhat noncentric to the objective of this paper. 

Also, apparently, the experiment is still lacking since to me, comparing with [*] is important in substantiating the contribution claim of this paper.
review_title: Official Blind Review #1

final_score: rating: 3: Weak Reject
review_content: In this paper, the authors propose a family of variational distributions in which the variational covariance matrix is parameterized as RR', with R_ij being nonzero only when j is a neighbor of i as defined by prior covariance. In other words, data points are only allowed to have nonzero posterior covariance if they are highly correlated a priori. This results in a sparse factor of the covariance matrix which can be used for efficient computation. Rather than being parameterized directly, the variational parameters \mu_{i} and R_{i, n(i)} are parameterized using a GCN: the labels and prior covariance information are supplied to the GCN, which produces the mean for a data point x_i and the |n(i)| nonzero elements of the covariance factor R.

Overall, the idea is interesting in the sense that a variational family with enforced sparsity likely leads to a reasonable probabilistic model. However, I have a few concerns about the execution.

First, as a minor point, in my opinion, the approximations eqns. 3-7 are not sufficiently motivated, and are essential to the method as they allow for stochastic optimization. It would be useful to see an empirical analysis of the tightness of the additional approximations, as well as a generally expanded discussion in this section. Beyond this, the method is highly engineered but the only ablation study done of the various components is Figure 3, which merely offers an analysis of convergence speed, but not on final model performance. Both ideas introduced in the paper (localization and amortization) can be used independently of the other.

More importantly, I believe the experimental evaluation should be substantially broadened. At present, three datasets are considered and on one of them (MNIST) three methods considered are within the error bars of each other: the bolding in Table 3 is inappropriate. Many popularly used benchmark datasets for sparse GP methods are widely available, and it seems particularly essential to include datasets larger than the ones considered here, since exact GPs can trivially be trained on these datasets in a matter of seconds (at least for the regression tasks). Again ignoring the single classification task, Variational GP methods are usually only considered for regression for much larger datasets. I suspect that, with proper hardware (e.g. a GPU) and truly large datasets much of the speed advantage enjoyed by LAIN as reported in the paper will be lost to overhead.
review_title: Official Blind Review #3

Meta-review: This paper presents a method for speeding up Gaussian process inference by leveraging locality information through k-nearest neighbours. 

The key idea is well-motivated intuitively, however the way in which it is implemented seems to introduce new complications. One such issue is KNN overhead in high dimensions, but R1 outlines other potential issues too. Moreover, the method's merit is not demonstrated in a convincing way through the experiments. The authors have provided a rebuttal for those issues, but it does not seem to solve the concerns entirely.

Decision: Reject