Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper presents a novel algorithm for approximating posterior distributions via weighted subsets of the data. The proposed algorithm samples points uniformly at random and then computes the weights using a quasi-Newton method; crucially it scales well with respect to the number of data points, both in terms of time and storage. The authors provide a rigorous theoretical analysis of their proposed algorithm and empirically evaluate it against commonly-used methods for posterior approximation. 
strengths_and_weaknesses: Overall, I found this paper to be an excellent read and believe it to be a strong candidate for acceptance. 

1. The proposed method is not particularly creative but frankly, I think the simplicity of the ideas being presented here are a strength of this work. The sum of the contributions in my mind are sufficient to get this paper above the originality bar for acceptance. 

2. The theoretical and empirical analysis are compelling although I do have a few suggestions/concerns regarding the experiments that if addressed, could raise my score of this submission even higher: 
    - I would have liked to see some comparison against SVI, even if that meant scaling down the experiments to settings where SVI is computationally tractable. It would be very telling if QNC was competitive with or even outperformed SVI in small-data regimes; if not, then finding some sort of cost-accuracy trade-off between the two methods could be useful for practitioners. 
   - I would have liked to see some sort of sensitivity analysis to the model hyperparameters, specifically S, K_tune (about which very little is said) and tau. 

3. The manuscript is very well-written; I genuinely found this paper to be an enjoyable read and applaud the authors' effort to include intuition wherever possible. 

4. I believe this work will have significant impact on a non-trivial percentage of the NeurIPS population: the proposed algorithm is simple and easy-to-implement and thus, accessible to people who might want to use/expand upon it. Furthermore, the scalability makes this algorithm broadly applicable, in settings where previously-proposed methods might not be. 
questions: My understanding of the empirical evaluation is that all four settings satisfy the assumptions of either Theorem 4.1 or 4.2: is this correct and if so, have the authors considered experimenting on settings where those assumptions do not hold? It would be illuminating to see the empirical performance when the theoretical guarantees do not apply. 
limitations: Yes, I believe the authors' discussion of their work's limitations is sufficient; related to my question above, I would have found it helpful if the authors had provided some intuition about settings in which their theoretical results would not hold much like how they did for settings in which the assumptions do hold.
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: In the area of Bayesian Coresets, this paper presents an algorithm that proposes:
1. To uniformly select $M$ data points that will be used to  approximate the posterior distribution, and,
1. to use a quasi-Newton method to refine the weights that will be assigned to each of the selected data points.

For this quasi-Newton method, the authors propose using an estimated covariance matrix to approximate the objective’s Hessian. 
Finally, the authors provide theoretical justification for their algorithm via three different theorems.
strengths_and_weaknesses: I think this is a very solid submission.
The authors propose an algorithm and prove that their approximation might behave as the full posterior and provide a convergence rate.
A notable feature is that assumptions are deeply discussed in the body of the paper (Section 4) or the appendix.
In general, I would say that it is a very precise paper.
On the weak side, I found the proof in the appendix quite hard to follow. Many inequalities were not evident at all and limited the possibility of doing a complete verification of the paper’s contributions [cf. Questions below].
It is important to highlight that when I was able to derive the bounds, the proofs are correct, as in Thm. 4.3.
questions: The most important thing I would like the authors to clarify is the derivation of equation (6) in the Appendix because it is critical for the proof of both, Thm. 4.1 and Thm. 4.2.

In the proof of Thm. 4.3, I think it should be that $\mathbf u \in \mathbb R^M$ is in the null space of $G(\mathbf w)$ iff $\mathbf{u}^{\mathrm{T}}f(\theta) = c$ holds   $\pi_w$-almost everywhere. 

For the following limitations, I'm not asking the authors to solve them. Instead, I suggest the authors that, if my assessment is correct, they should make the limitations more explicit as open problems.

First, I see the following limitations:

- The use of Monte Carlo estimations. 
This has two implications:
    1. The obvious one is the Monte-Carlo error, which might imply a bias.
    2. A not-so-obvious one is that the method assumes that we have an oracle that allows us to sample from the corresponding distribution. However, often times we can only get approximated samples from the distribution (or samples from an unconverged chain).

Part of point (1) was briefly mentioned, but there is no discussion about (2). To be concrete, it should be pointed out that a version of Thm. 4.3 with the two sources of errors, is still an open problem, extending the discussion at the end of section 3.2 

Another limitation is the fact that we don't know if the optimization is actually making progress. A quick look at Algorithm 1 will show that there is no function of the objective being used as stopping criteria. I understand why this happens. Nevertheless, I think the authors should be, again, more explicit about this. This is related to the fact that the Armijo condition is not being used.
limitations: The authors mention some of the paper’s limitations. Above I'm suggesting mentioning a few more.
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: This paper addresses the problem of approximating a Bayesian posterior with a large number of datapoints. They do so by selecting a sparse, weighted subset of datapoints (a coreset). Previous methods have addressed this problem, but the authors note that previous methods suffer from requiring some subset of: (1) potentially expensive loops over the whole dataset, (2) user input or parameter tuning, (3) a large number of potentially expensive MCMC simulations. The authors address (1) by noting that a coreset can be formed on a random subset of the data, (2) by proposing a quasi-Newton method that requires one MCMC simulation per iteration, and (3) just by virtue of providing a different algorithm without the same tuning / user input requirements. 

The authors prove conditions under which (1) still allows for exact or approximate recovery of the posterior. And they prove conditions under which their optimization algorithm (2) does not require many iterations. In experiments, the authors show that their method is both faster and more accurate than other coreset methods.
strengths_and_weaknesses: **Strengths**
- The writing in the paper is good; the material is pretty technical, but I found it relatively easy to follow. 
- The method proposed by the authors intuitively fixes clearly explained problems with previous work and has desirable theoretical properties (mostly -- see weaknesses below) and this intuition and theory actually seem to hold up in practice in non-exhaustive, but at least detailed and careful experiments. That's a pretty solid combination. Based on this, I vote for the paper to be accepted. 

**Weaknesses**
1. The method is claimed to be "black box" with "far less ... user input required" than other algorithms. I think this is overselling things a little bit. I see five different hyperparameters (at least five, since one of them is a sequence): the number of coreset points $M$, the step size sequence $\gamma_k$, the Hessian regularization $\tau$ (or, equivalently, the condition number threshold mentioned on line 142), the number of iterations to tune the stepsize for $K_{tune}$, and the size of the subsampling set $T$. Since there are no sensitivity studies for these hyperparameters, I don't think it's fair to suggest that little user input is required. Relatedly, some competing methods are criticized for needing an initial, user-specified posterior approximation $\hat\pi$ as an input, such as the Laplace approximation. I don't think this requires much user input; given access to an optimization library and automatic differentiation tools, a Laplace approximation can be constructed without user input.
2. Theorem 4.3, which studies the convergence rate of the authors' proposed algorithm (an important selling point of the work), essentially assumes the smallest eigenvalue of the covariance $G(w)$ is not too small. For example if $\xi$, is zero, and the optimal coreset perfectly approximates the posterior, then Theorem 4.3 predicts no convergence of their algorithm. But it seems -- and maybe the authors can correct me on this -- that as $N \to \infty$ we should expect $\xi \to 0$. For example, say we expect the posterior to concentrate to a point mass as $N \to \infty$ and some $w^* \in W$ perfectly approximates the posterior. If the posterior is contracting to a point mass, won't $G(w^*)$ approach the matrix of 0's? (I'm writing this as if the inf over $W$ is actually the inf over $W_N$; if it's the inf over $W$, then the inf contains arbitrarily large $w$'s even for $N = 1$).

**Smaller things**

- There are a lot of derivatives with respect to $w$ taken throughout the paper. But $w$ sits in a constrained set $W$. How are these derivatives defined when $w$ is on the boundary of $W$?
- Should the left hand side of equations 6 and 7 be indexed $1:M$ and $1:M, 1:M$, respectively?
- Line 113: it's not intuitively clear to me why the first term should dominate the expression here.
- Algorithm 1: is input $K$ supposed to be $K_{tune}$?
- "This is sublinear in $N$". I usually take "sublinear" to mean $o(N)$, whereas this runtime is $O(N)$.
- In the equation right after line 188, I don't think $A$, $K, X$, and $X_1$ were ever defined.
- In Theorem 4.3: could the inf over $w \in W$ be replaced by the inf over ${ w \in W :  \|\| w - w^* \|\| \leq \|\|w_0 - w^* \|\| \}$? Since there's monotone improvement towards $w^*$, it seems like you'll never leave this ball, and so you can ignore any bad behavior outside of it.
- In the experiments, it would be good to include the runtime of FULL to see how marginal / non-marginal the gains here are.
- In the proof of Theorem 4.3, there are a couple places where $G(w) + \lambda I$ is written. Should this $\lambda$ be a $\tau$?
- It would be helpful if the equations in the appendix were contiguously numbered with those in the main text. Otherwise it's not immediately obvious which equation "Eq. (1)" refers to.
- The letter $t$ shows up in a few places in proofs. It seems like this is a number between 0 and 1, but I don't think this is ever stated.

questions: - Can the authors clarify what's going on with $\xi$ in Theorem 4.3 (see weaknesses above)?

- (minor question): On lines 118-122, the authors note that when M is larger than the dimension of the space of log-likelihood functions, $G$ is not invertible, which motivates adding some small $\tau$ to its diagonal. If $G$ has a zero eigenvalue in some directions, this implies the weight vector $w$ has an orthogonal decomposition into directions along which its variation does and does not matter. Could a reparameterization allow the optimization algorithm to instead just work along the directions for which the variation of $w$ does matter? This might avoid the use of $\tau$. 
limitations: I think the authors have adequately discussed the social impact of their work.
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: This paper proposes a method for approximating a posterior distribution in the framework of Bayesian statistics. Specifically, this posterior distribution involves a sum over $N$ potentials $\sum_{n=1}^N f_n(\theta)$ which has to be evaluated each time an expectation wrt the posterior has to be calculated. It is proposed to replaced this sum of another weighted sum over $M \ll N$ terms.  This corresponds to selecting a subset of data, called a coreset. 
These points are sampled uniformly at random and their weights are computed by minimizing the KL divergence between the full posterior and the approximated posterior. A Quasi-Newton optimization method is proposed to calculate these weights.
Statistical guarantees are given for the size of the coreset in order to reach a small KL divergence. The convergence of the Quasi-Newton method is also discussed. Numerical simulations illustrate the accuracy of the posterior approximation.
strengths_and_weaknesses: Originality: This paper discusses interesting ideas. Being familiar with coresets in general but less with this specific application, I cannot completely assess the originality of this paper.
    
Quality: From a global perspective, the main paper is well-written and the results are well presented. However, from the technical viewpoint, the interpretation of some mathematical claims is not straightforward, for instance, in the case of Thm 4.1. The numerical simulations are convincing.
    
Clarity: The main paper is easy to follow. Concerning the technical details, I have several questions about the proofs of the theoretical results in Supplementary Material. These proofs are long (e.g., the proof of Thm 4.2 takes more than 8 pages). In principle, this is not an issue. However, these proves deserve extra clarifications at several places and are not easy to read; see the questions below. To guide the reader, it would also be beneficial if a brief description of the proof strategy is given before each proof.
    
Significance: This method is certainly interesting and probably useful in the context of Bayesian inference.
questions: I have several questions about Thm 4.1 and its proof. 
- First, the statement of this result is difficult to interpret since $J(\delta)$ depends on $\delta$ in a non-trivial way. After Thm 4.1, the authors try to explain the behaviour of $J(\delta)$ at the lines 185-191.
I do not find this explanation very clear. Although we might guess what are the random variable $X$ and $X_1$ from the context, it is worth defining them explicitly.
The limiting behaviour for $J(\delta)$ at line 189 is not obvious. Can you give a few lines of explanation?
- Second, it is difficult to follow the proof of Thm 4.1 in Supplementary Material. Could you give a roadmap for this proof? What are the main steps? It would help the reader to read this proof.

Here are a few technical questions about the proof of Thm 4.1. 
- At line 61 (SM), the authors introduce a variable $t$, which is presumably in the $[0,1]$ interval. It is worth defining $t$.
Next, at line 62 (SM), there is a formula for the KL divergence. Can you give a few words of explanation? Why is this integral equal to the KL divergence?


- Also, at line 75 (SM), the authors claim they use a union bound. This step necessitates a clarification. Could you give a few details?
What are the events that you consider in the union? How do you bound $\phi$?

- At line 79 (SM), there is a typo. At the right-hand side of first inequality, there should be $\Pr( \dots < t_N)$ but $<t_N$ is missing. The same thing happen at the second inequality. 

- At line 82 (SM), I presume there is another typo. In my opinion, $\log(A_d^{-d/2})$ should be replaced by $\log(A_d^{d/2})$. Also, the last equality should be an inequality. 

Also, I have a few questions about the proof of Thm 4.2

- At line 98 (SM), the authors upper bound $I_{\epsilon, 1}$. The last inequality is unclear. I presume that the authors claim that 
$[g - \sum_m v_m (f_m - \bar{f})-E_{w(v),t}]^2\leq [g - \sum_m v_m (f_m - \overline{f})]^2$. 
Why is this correct? 
Is the quantity $g - \sum_m v_m (f_m - \bar{f}) - E_{w(v),t}$ positive?

- At line 101 and at several other places (e.g. line 113), it is written that the probability of an event is bounded from below by $1 - f(N)$, or some decreasing function $f(N)$. To be complete, it should be mentioned that $N$ has to be large enough so that $f(N)<1$.

- At line 100 (SM), the authors write *We now assume $\|S_N(\theta)\| \leq (2- \sqrt{2}) \epsilon L_0 \sqrt{N}$*. This is not an assumption since the authors calculate right after the probability that this event does not happen. See also line 120 for a similar use of the verb *assume*.

- At line 102 (SM), another inequality is unclear. At the second lower bound, it seems that the authors take the square of an inequality. Are both sides of this inequality positive numbers? 

- At line 127 (SM), the first equality is unclear. Could you give some details?

Here are some questions about Thm 4.3.

- At line 229, I think that the assumptions are incomplete, namely, about the parameter $\eta = 1 - \gamma(\xi - \epsilon)$ which influences the convergence rate. What are the conditions on these parameters such that $\eta >0$? Shouldn't there be conditions on $\epsilon$ so that $\xi - \epsilon >0$?

- About the convergence guarantees, there is an upper bound on $\| w_k - w_k^\star\|$ where $w_k^\star$ is the projection of $w_k$ on $W^\star$. Here, $w_k$ is the weight at iteration $k$. What does this bound tell about the convergence to a global optimum?


Typos:

104 unfinished sentence

Algorithm 1: indicies &larr; indices

SM 34 extra full stop

SM 87 $S_N$ &larr; $S_N(\theta_0)$

SM 122 missing ) on the left-hand side

=========================================================================

Note: I have read the authors' response which I found convincing. I update my score.

limitations: The limitations of this work are summarized in the checklist and are briefly discussed in section 5.4. I do not see any potential negative societal impact.
review_title: null

Meta-review: metareview: The paper has genereated unanimous enthusiasm and we are happy to recommend acceptance. Please make sure that all comments in the reviews/discussion threads are taken into account in the final version of the manuscript.
confidence: Certain
Decision: Accept