Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 9: Very Strong Accept: Technically flawless paper with groundbreaking impact on at least one area of AI/ML and excellent impact on multiple areas of AI/ML, with flawless evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper proposes a Bayesian inference methodology incorporating coresets with Hamiltonian flows. The paper demonstrates theoretically the challenges that both coresets and variational inference via Hamiltonian dynamics face, and proposes a fix for both in their algorithm "Sparse Hamiltonian Flows". Their method first selects a coreset and then follows a sparsified Hamiltonian flow with quasi-refreshments, which allows the flow to update the momentum. Important or argumentative claims are backed up with theoretical proofs. Experiments on a variety of regression problems demonstrate the superiority of their algorithm over current state-of-the-art coreset compression and variational-flow-based methods.
strengths_and_weaknesses: Strengths:
- Important claims and new insights on coresets and Hamiltonian flows are backed up with theoretical proofs. Where may be difficult to prove in the general case, such as Proposition 3.1, a representative example is given and the claim is proven on it. 
- The proposed idea is very novel and addresses important drawbacks that current coreset methods suffer from.
- A thorough and clear review of related and past methods is provided
- Experiments are well-conducted and a variety of datasets, both synthetic and real, are explored

Weaknesses:
- Perhaps some other choices of $\rho_t$ and $R_\lambda(x)$ could be explored so that a potential user could understand the sensitivity of the algorithm to these choices
questions: - I am under the impression that the quasi-refreshment step could also be incorporated into some of the other baselines considered in the experiments, and not just for SHF. If this is the case, how would the baselines then perform?
- In Figure 2, relative cov error seems to take a long time to converge, compared to UHA-Full. Why did the purple UHA-Full suddenly go up after ~2000 iterations? It seems like at that point, the approximation is just as good as SHF.
limitations: Yes
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: The paper introduces a new method for constructing Bayesian coresets. The authors demonstrate that a single uniform subsampling of data points is in principle sufficient to obtain an exact coreset, and introduce the sparse Hamiltonian flow to efficiently construct and sample from the corresponding coreset posterior approximation. Notable improvements over other coreset methods are reported in several experiments.

strengths_and_weaknesses: ### Originality:
To my knowledge, the presented method is original. The authors provide a footnote citing concurrent work based on similar ideas, but the combination of Hamiltonian flow approximations to the coreset posterior seems unique to his work. One could argue that the authors should provide a dedicated Related Work section to elaborate on the connections to earlier work.

### Quality:
The paper is technically sound, and the claims are carefully developed and well supported. The paper could be further improved with some reflection on the limitations of the approach.

### Clarity:
The manuscript is well structured and very clearly written, with helpful introductions to the methodological ingredients that it builds upon.

### Significance:
The paper constitutes a significant contribution within research on Bayesian coresets, both in terms of methodology and measured in terms of the performance improvements over other methods. I am not certain how large a contribution it will have to the field of Bayesian inference in general. This would have been easier to assess if the authors had broadened the scope of their baselines to other Bayesian inference procedures.

questions: ### Detailed comments and questions:

Line 110. After having introduced Hamiltonian Dynamics, the author state that here that it is possible to use it as the basis of a normalizing flow. It would be informative if they could also explain what the advantages of using a Hamiltonian flow are compared to other choices of normalizing flows. I assume this might be explained in [21,22], but it would be helpful if it was reiterated here.

Line 142. The model covered in Proposition 3.1 is referred to as a "representative example model". The authors should elaborate on why this is a representative (or even relevant) example model. Can anything be said about the compression for the posterior of other models? Can anything be said for finite N? In particular, it would be interesting to know whether anything could be said about the choice of M in the general setting.

Line 197. "In this work we assume that p_t ~ N(mu, Lambda^-1)"
Does this mean that we are ultimately assuming that the posterior can be approximated by a diagonal Gaussian? In that case, how is this different from the assumption made in a simple parametric VI setting? In the introduction, the authors explicitly mention the “simple parametric families” as a contrast to the current work. It would be helpful if the contrast between the two was explicitly explained for the case when this parametric assumption of p_t is made.

Line 266. "Figs. 2c and 2d demonstrate that this reduction in KL divergence is primarily due to a lower relative error in the approximate posterior mean provided by SHF."
To which extent is this explained by the fact that the posterior is Gaussian in this case? It seems like an idealized setting for the proposed method, given the assumption of Gaussianity of p_t.

In the Experiments section, the choice of baselines used in the different figures was not clear to me. Why there was a difference in the baseline methods included in Fig 2/3 and Fig 4?

I would have liked to see simpler Bayesian Inference baselines such as Laplace and simple mean-field VI included as baselines as well. This would make it easier for someone not intimately familiar with coreset methods to judge how big an impact these methods have over conventional approaches.

In the Conclusion section, it would have been helpful with a discussion of the limitations of the proposed approach.


### Minor details

Line 81. "While theoretically not expensive, interleaving MCMC and gradient descent steps is hard to implement and tune, and is too slow to be practical. "
This sentence was not entirely clear to me. First, you state that it is theoretically not expensive, and that it is hard to implement and tune, but then you conclude that it is too slow to be practical, which seems to contradict the first part of the sentence. Please clarify whether the limitation here is fundamental (e.g. efficiency wise), or whether it is practical (difficult to implement and tune).

Line 149. "Let C be the universal constant from [37], Corollary 1.2.
This constant appears a bit unmotivated here right before Propoposition 3.1. It might increase readibility if it was either explained in greater detail, or otherwise moved to the end of the sentence in 152.

Line 163. "since w only has the first M entries nonzero"
Was the convention of placing the nonzero elements first mentioned anywhere? Perhaps I missed it.

limitations: The authors do not discuss the limitations of their method.
review_title: null

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: “Bayesian Inference via Sparse Hamiltonian Flows” combines three techniques to make Bayesian Inference faster and more accurate. It combines a) subsampling of the data (core sets), b) sparse flows and c) quasi-refreshments.

The paper provides theoretical evidence for why these subcomponents reduce the runtime or increase performance (see section 3) and empirical evidence in three different settings. The Sparse Hamiltonian Flows (SHF) clearly and strongly outperform the alternatives in most experiments. 

*UPDATE*: thanks for addressing all of my concerns. I update my score from 7 to 8. Great work. Keep it up!

strengths_and_weaknesses: In short, I think the paper is good and should be published with minor revisions. 

*Strengths:*
- The paper is very well-written and clear
- The suggested combination of methods clearly and strongly improves performance compared to the alternatives
- The paper provides a theoretical analysis of why and in which manner the performance improves due to SHF. 

*Weaknesses:*
- The experiments are all in fairly simple settings. The results already convince me that the method is very strong and warrants publication but a more complex experiment would increase this conviction (see questions). 
- The paper says little about its limitations (see questions).

questions: - Limitations: To my understanding, SHF makes some assumptions that imply limitations. For example, SHF chooses a random subset of data points. In cases where a random subset of data points is not representative of the entire dataset, SHF might be fast but not useful. Is this correct? Are there other limitations of SHF that are not explicitly mentioned?
- Scale (related to limitations): I expect that more complicated data types will run into problems with random subsets more easily. Thus SHF might not be an appropriate solution for more complex models and data. I’d like to see a more explicit interaction with these points, either by actually running an additional experiment or by stating the implicit assumptions and following consequences in more detail. 
- Subsets: I’m not sure I fully understand the way in which the random subset is chosen. Is the subset of M values chosen uniformly at random once at the beginning of the process or does the subset change over time? 
- Figure 1: I see that during the leapfrog steps (e.g. every 10th iteration), the ELBO jumps up towards a better state. This is in line with the theory. However, from steps 0-9 the ELBO decreases rather than increases. I don’t understand why that is the case. My naive assumption would be that the blue lines should also go up just not as drastically as the red lines. 

limitations: I think, the limitations of the method were discussed insufficiently and should be addressed as described in questions 1 and 2. 

I’ll use the rest of the section for high-level comments.
- In its current form, the paper convinces me that SHF decreases runtime and increases performance for datasets with low complexity. The authors show this with their theoretical analysis and empirical experiments. Furthermore, the paper is well-written and the presentation is good. All of this combined already warrants publication in my opinion. 
- The assumptions that SHF makes and the implied limitations are underexplored. I expect that SHF will have a hard time with more complex models and data because it assumes that a random selection of data points is representative of the entire dataset. I think a good response or an additional experiment in this direction would convince me to raise my score further. Note, that I think the paper would be improved, even if the method is more limited than expected. Stating limitations helps readers and practitioners because it defines the scope of possible use cases more clearly. 
- I want to help where I can. In case something is unclear, feel free to ask follow-up questions.
review_title: null

Meta-review: metareview: All reviewers agree that the paper proposes an interesting approach to Bayesian inference incorporating coresets with Hamiltonian flows. Although some reviewers have some technical concerns at their first reviews, basically those have been resolved by the authors' responses. Thus, although there are some points that should be modified from the current form, I think we can expect the authors modify the paper in the camera-ready by reflecting the discussion. Based on these, I recommend acceptance for this paper.
confidence: Certain
Decision: Accept