Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: The authors present a novel method, named IterGP, for doing approximate inference in Gaussian processes. Taking a probabilistic numerics approach, they treat the representer weights, $\mathbf v_* = \hat{\mathbf K}^{-1} (\mathbf y - \boldsymbol \mu)$, as a quantity to iteratively compute. By building on recent advances in probabilistic linear solvers, they derive an algorithm for iteratively updating a distribution over the representer weights, which captures the (computational) uncertainty in them. 
By reparameterising the GP posterior in terms of the representer weights and then marginalising them out, the authors obtain a new GP posterior expression, which implicitly accounts for the uncertainty in approximation made by the iterative representer weights.

While explicitly computing the computational uncertainty is expensive, computing the combined (computational and mathematical) uncertainty has a quadratic cost, meaning that IterGP computationally sits in-between exact GP inference (cubic) and linear-time approximation methods, which, however, do not provide calibrated uncertainty estimates. At the same time, the memory cost of IterGP is only linear.

To make the iterative updates, IterGP requires a policy for selecting and weighing data. The authors discuss different strategies and show how they correspond to standard approximation methods, such as conjugate gradients and inducing point methods, and extend these to properly account for computational uncertainty.

The paper concludes with a theoretical analysis, proving general convergence of the posterior mean as well as proving that the combined uncertainty is a worst-case bound on the error, and an empirical evaluation of IterGP, showing that it provides better posterior estimates than commonly used methods.

strengths_and_weaknesses: **Strengths**

The paper overall is of very high quality. The writing is clear, and the figures are fantastic. I especially like the pedagogical use of colours for the different kinds of uncertainties, which are shared between figures, equations, and the text.

From a technical perspective, the paper is very thorough, and the authors carefully explain the intuition behind the method where possible. They also provide a good discussion of the different policies for choosing actions and how these link back to commonly used approximation methods, showing a kind of unification (and extension) of these methods.

The theoretical analysis seems solid, but I did not check it in detail.

While the field of probabilistic numerics is not my area of expertise, the work seems original and highly novel to me. Overconfident posteriors are a well-known issue in the approximate GP world, so the contributions in this paper make it a very exciting piece of work. It is definitely a significant contribution to the approximate GP literature, which will be of major interest to the NeurIPS community.

**Weaknesses**

While the writing is overall of very high quality, there are a lot of new concepts to digest for someone not in the field of probabilistic numerics (but who does have experience with GPs). A short background on probabilistic numerics (perhaps probabilistic linear solvers in particular) would have been helpful for me, but I understand that I might not be the target audience.

One thing that the authors did not discuss is how to choose the stopping criterion in algorithm 1. I suppose there are some trivial choices (e.g., if one has a fixed computational budget), but perhaps one can be smarter here. A brief discussion of this would have been nice.

For the experiments, it would have been interesting to see SVGP and IterGP compare in terms of wall-clock time for different numbers of inducing points/iterations. Since SVGP is faster to compute, I suppose it would achieve better results for very few inducing points. It would be interesting to see when IterGP begins to perform better for a fixed computational budget.

Also, it would be interesting to see the RMSE and NLL obtained by an exact GP indicated in both figure 4 and 5.

**Various minor things**
* In equation (2), I think a $+ \mu$ is missing in the mean.
* The next-to-last sentence in the caption of figure 2 appears incomplete.
* A couple of lines in algorithm 1 are coloured grey, but there's no discussion of what this means, as far as I can see.

questions: NB I have quite limited experience with probabilistic numerics, so the following questions should be read in this context! :)

1. I don't fully understand the definition of the residual in line 90. Specifically, why does it contain $\hat{\mathbf K}$ and not just $\mathbf K$? I would have expected the latter if it's the residual between the observations and the GP posterior mean.

2. I found the discussion of the overconfidence in SVGP extremely interesting, but I don't quite understand the point made in lines 142-146. Since the representer weights of the inducing points are typically calculated exactly, where does the error in the uncertainty estimate (i.e., the overconfidence) come from? (To be clear, this is absolutely not a crucial question; I'm just trying to understand SVGP :) ).

3. I suppose the choice of a stopping criterion will be problem-specific, but do you have some suggestions for this? While the computational uncertainty is too expensive to explicitly compute in general, is it possible to somehow estimate it and stop when we have reached a pre-defined tolerance?

4. Figure S5 (b) in the supplementary hints are instabilities in certain settings. Do you know which parts of the algorithm lead to this, and can you say something more about when this could happen?

limitations: Potential negative societal impacts have not been discussed, but it is not necessary given the paper's theoretical nature.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: Gaussian process regression model is impractical for big data and various approximations have been proposed to alleviate such difficulty. However, people have overlooked the uncertainty due to the numerical approximations for saving computational resources. This paper presented a novel low-complexity algorithm that respects uncertainties arising from the finite number of data observed and the finite amount of computation expended. Besides, theoretical analyses are given to support the effectiveness of the proposed algorithm. Experimental evaluations were also conducted to verify the proposed algorithm with some widely used approximation methods, such as sparse GP. 
strengths_and_weaknesses: Strengths:
1. A novel GP approximation that accounts for computational uncertainty.
2. Well-crafted performance analyses (Th.1 and Th.2)
3. Experimental evaluations in terms of a few widely used GP approximations. 

Weaknesses:
1. In Eq.(6), I understand that the "computational uncertainty" term results in a combined uncertainty that is cheaper to evaluate; however, I doubt this term is solely due to the numerical approximation made to the standard GP. 
questions: 1. Would the proposed algorithm work for distributed GP as well? If yes, what is the action $s$_i?
2. The theoretical analysis assumes that the actions $s$_i are linearly independent. Is this always true for the considered approximations?
3. Have you verified that the "computational uncertainty" term will go to zero when the computational resource is infinite?
4. Do you have more experimental results obtained using other kernels, such as the spectral mixture kernel and some hybrid kernels?
5. In the conclusion, you mentioned that the proposed algorithm is particularly useful for online data processing, which is not clear to me? 

limitations: Maybe more experiments with different kernel functions and different data lengths would be helpful.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary:         This paper proposed a method to take into account extra uncertainty arising from using approximate GP solutions to scale GPs to large datasets. The proposed method is based on making inference about some parts of the computation of the posterior predictive distribution of a full GP. The authors indicate that the proposed approach is a generalization of many GP approximate methods. Theoretical results associated to the proposed method and derived and some experiments are carried out on synthetic and real-world data.

strengths_and_weaknesses: Weaknesses:

        - The explanation of the proposed method is poor. The authors have to make a better job at explaining their method. Eq. (3) and the update on p(v*) has to be better explained.

        - Section 2.1 is poorly explained. It is not clear the connections with other methods.

        - The experimental section is a bit weak.

Strengths:

        - Nice theoretical results are derived for the proposed method.


questions: It is not clear that the marginalization of v* below Eq. (2) gives the GP prior. The mean would be zero mean after the marginalization, using Eq. (2). The resulting variance will have to add the variance of the mean. Can the authors clarify this? It seems Eq. (2) is missing the GP mean.

Above Eq. (3) should not r_i bet r_i-1?

limitations: The authors have indicated that they have described the limitations of their method. However, they do not indicate where in the manuscript.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: The paper proposes an approximate inference technique, called IterGP, for Gaussian progress (GP) regression. Methodologically, the key algorithm (Algorithm 1) provably constructs increasingly more accurate approximations (of the GP posterior) as the runtime increases. Each approximation also comes with a notion of approximation error (in the sense of Theorem 2). Empirically, IterGP can be computationally cheaper, but just as accurate as existing methods (Figure 4), or more expensive but more accurate compared to existing methods (Figure 5).
strengths_and_weaknesses: I think the paper’s key ideas are original and strong, but I have some concerns about the quality and clarity of the manuscript.

# Originality
Section 2 is a novel way of using probabilistic linear solvers (PLS) to perform GP regression. Section 2 treats the so called representer weights as unknown/random, whereas existing works treat either the kernel matrix or the inverse of the kernel matrix as random. The randomness here is due to limited computation. Since the posterior mean at a test point is a function of the representer weight (Equation 2), the randomness in the representer weight propagates into the posterior mean and is computable as in Equation 6. The update equations 4 and 5 give the general skeleton of how to reduce the randomness in the representer weights. 

# Quality 
In terms of strengths, the visualizations and plots in the paper are very legible and convey the message well. Figure 1 panel b breaks down uncertainty into two constituent parts. Figure 4 demonstrate how IterGP is cheaper than conjugate gradient (CG) GP but just as accurate. Similarly, Figure 5 is very easy to read and understand the takeaway.

In terms of room for improvement, I think the paper is missing three kinds of discussions. 
- The first is the impact of the policy. Although Table 1 mentions a list of policies, the rest of the paper does not discuss the pros and cons of different policies, or give recommendations on which to use. I do understand that in a sense the actions s_i are hyper-parameters of Algorithm 1, and tuning hyper-parameters is potentially its own problem.  
- The second is distinguishing the combined uncertainty (in Equation 6) from the regular approximate posterior variance at test points. What I mean by approximate posterior variance is that, while the true posterior variance at $x_*$ is 
$$k(x_*, x_*) – k(x_*, X) \hat{K}^{-1} k(X, x_*),$$
When we have an approximation of the inverse of the kernel matrix, say, $L \approx \hat{K}^{-1}$, then we announce the approximate posterior variance to be
$$k(x_*, x_*) – k(x_*, X) L k(X, x_*),$$
My current impression is that the combined uncertainty is exactly the approximate posterior variance for the choice $L = C_i$, where $C_i$ is constructed using the IterGP iterative procedure. But more generally, all approximate GP approaches that have approximations to $\hat{K}^{-1}$ will also have the combined uncertainty, and it’s equal to the approximate posterior variance that they report. 
- The final discussion is whether Theorem 2, in particular Equation 13, applies to other kinds of approximate GP inference techniques. Skimming through Theorem 2’s proof, there is no part of the proof that relies on the actual structure of iterGP, in the sense that the statement will hold if we replace $C_i$ with any other approximation of $\hat{K}^{-1}$. In that case, since other approximate GP inference techniques have their own approximation of $\hat{K}^{-1}$, their approximate posterior variance can also be used to give worst-case bounds in the sense of Theorem 2. 

# Clarity
The paper is well-written. There are some negligible typos that I will highlight in the “Questions” section.

# Significance
Advances in scalable and accurate GP inference are important since GP regression is a staple of modern data analysis.

questions: I would like the authors to address my questions regarding the “quality” subsection of the “Strengths and Weaknesses” section. My biggest concern is being confused about the relationship between combined uncertainty and the approximate posterior variance. The answer to this question is important, because if the combined uncertainty is the same as the approximate posterior variance, then the claim in the abstract “[…] due to limited computation, is entirely ignored when using the approximate posterior” is not accurate, since approximate GP automatically accounts for both computational and mathematical uncertainties, through the approximate posterior variance / combined uncertainty. More generally, I don't see the benefit of the so-called combined uncertainty, it it's just equal to the approximate posterior variance. My confusion also spawned my question about whether Theorem 2 applies to other approximate GP techniques. It also makes me question whether the claim in Figure 1 is valid: if it were true that Theorem 2 also applies to SVGP, then the message of modelling computational uncertainty improves GP approximation is incorrect. Perhaps the cause of IterGP-PI performing better than SVGP is due to the later using inducing points, which can be inaccurate.

The list of typos I’ve found are as follows
- Lines 83-84: Equation 2 is true if the prior mean is zero.

- Lines 96:97: the contraction only happens for a well chosen set of policies $s_i$, not in general

- Lines 119-120: it’s not true that the algorithm is online. Line 9 of Algorithm 1 requires the whole kernel matrix $\hat{K}$.

limitations: I do not see any negative societal implications to this line of work.
review_title: null

Meta-review: metareview: Gaussian Processes are a very nice modelisation tool in Bayesian nonparametrics, with very nice uncertainty quantification. But they also lead to serious computational issues. So, in practice, it is difficult to know what part of the uncertainty is due to the data, and what is due to approximations in the computations. Here, the authors propose a new (and cheap) iterative approximation, IterGP. They analyse carefully its approximation error in Section 3. Experimental results corroborate this analysis. Overall, IterGP can reach the same accuracy than previous methods with a limited number of steps, and thus a smaller computational burden. Increasing the number of steps will of course make it even more accurate.

The four reviewers agreed on the relevance of the algorithm, the quality of its technical analysis and the quality of the experimental results (I agree with them). Reviewer 5Mot praised the high quality of the writing. The other reviewers overall agreed, but provided a list of minor points that could be fixed to improve the paper. I therefore recommend to accept this paper.
confidence: Certain
Decision: Accept