Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: The paper focuses on distribution shift, i.e. the distribution that generates the data changes with time, something that can cause problems to static models since now the train and test distributions are not the same. The authors take an online Bayesian perspective and try to detect a changes in the distribution based on the data points that are received in each iteration. They also perform extensive experiments in different domains.

main_review: Overall, I liked the paper, it provided an interesting perspective in distribution shift detection which has become a core problem to study recently in machine learning literature. The presentation of the paper is clear, I liked that the authors started by presenting the exact inference, before the introduction of variational inference, it helped understand the main idea although some parts of the paper were still technical and hard to follow in detail. The experiments were also very thorough and in several different datasets. One question I have for the experimental part, is how does the VBS approach compare with just using static models. In the case of CIFAR for example there is a large performance gap between the best performance that a neural network can achieve for normal CIFAR and the accuracy that VBS obtains for the modified dataset used here. I am wondering how well does a static model trained on CIFAR performs for the modified dataset and how does it compare to VBS. I am also not sure that I understand what the "trivial baseline" of independent batches is. Does it mean that you use the data points from this batch to learn a model? How does this work for CIFAR when you have only 100 samples per batch? (I probably misunderstood that but I would appreciate the clarification)

Typos:
- l320: MNIST or SVHN: should it be CIFAR?
- l347: whilee
limitations_and_societal_impact: N/A
review_title: null

final_score: rating: 4: Ok but not good enough - rejection
review_content: summary: In this paper, the authors propose a method to jointly model the data and also change points in the model parameters.
This is accomplished following a Bayesian approach, where the full vector of change point detections (as binary indicators) is part of the model, and it informs the marginal posterior.
The method is illustrated in an interesting mix of real and synthetic data.

UPDATE: The authors' responses were succinct and useful. However, I still think that the paper relies on too many approximations/heuristics. The approach is sensible, and the paper could be impactful, but they don't constitute a Neurips-level contribution.
main_review: In this paper, the authors propose a method to jointly model the data and also change points in the model parameters.
This is accomplished following a Bayesian approach, where the full vector of change point detections (as binary indicators) is part of the model, and it informs the marginal posterior.
The method is illustrated in an interesting mix of real and synthetic data.

Overall, this paper is well written and deals with an important problem. However, I have some important concerns:

* The method looks highly impractical to me. A full vector of change points is being carried around, and so the dimensionality of the model explodes. There are some interesting heuristics proposed, but they are all approximate heuristics, and so it is unclear how all this works in practice.
e.g., how to approximate a bimodal distribution with a unimodal one ? ( L182).

* On a related note, I find the normality assumption in (2) and (3) to be severely restrictive. I understand that the Bayesian approach requires this kind of simplifications, but this assumption automatically precludes practical cases. with, say, categorical or sparse or missing data. 

* At several points the authors describe an "exact inference" scheme. I am not sure what exact inference means here, especially given the number of heuristic methods involved.

* In L296, what does it mean to reproduce the targets with real-valued probabilities?


limitations_and_societal_impact: .
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper addresses the topic of changepoint detection in the event of distribution shift. A Bayesian model meant to detect such changes online, and able to discount historical information after a distributional shift, is formulated to express the problem. Algorithmic implementation is provided and evaluated across a number of data sets.
main_review: The paper is well organized and written: the problem is properly defined, assumptions are clearly stated, formalization rigorous; the reasoning steps in the development of the inference algorithm are also easy to follow. Experiments are extensive, and the sub-selection in the main paper suitably illustrative; some considerations on the compuational cost (as a function of the variational hyperparameters like beam size) against the SotA methods considered would have been interesting. Related works clearly relates the current work to the literature, although this reviewer is not able to judge independently how innovative the work is within the context of changepoint detection models.
limitations_and_societal_impact: Short and sufficient considerations on broader impact are offered at the end of the paper.
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: This submission relates a method for adapting to distribution shifts online in a Bayesian fashion. A distribution shift is represented as a binary latent variable indicating that a shift has, or has not occurred. If a shift is inferred to have occurred, then the variance of the posterior is increased before the next step of the Bayesian recursion, weakening the influence of previous observations. Computational constraints associated with maintaining many possible hypotheses of the incidence of distribution shifts are remedied by the use of beam search. 

This paper is timely and well-written. The topic of online adaptation to distribution shift is very relevant to the NeurIPS community, and the submission has developed through several rounds of peer review into a mature contribution to the literature. There are some substantial limitations that would be important to address in future work, but I am happy to recommend acceptance and willing to defend my evaluation.

UPDATE 08/17/2021
The author response has addressed all my concerns. In particular it is very good to know that the full changepoint history need not be maintained, and that the method will automatically adapt, in a sense, to a poor choice of \beta. I think this is a very good paper, and have increased my score to 8.
main_review: The approach as described is very thoroughly developed. As noted in the submission meta-data, this is the third round of peer review that this work has received, and I believe it represents a worthy contribution in its current state. There are a couple relevant references that have been omitted, but overall the literature review is adequate. I find the experiment evaluation sufficient to verify the quality of the idea. 

The asymptotic memory and compute complexity (particularly in terms of the time horizon) do not appear to be clearly stated, aside from a brief discussion of memory requirements in G.4.1.
I understand that beam search remedies the combinatorial explosion of possible histories, but it does not address the fact that even a fixed set of K sequences must eventually grow to infinite length in the current formalism. Of course the histories could simply be truncated, but that approach introduces history length as another hyperparameter to tune. Is there a more principled way to address the scaling with the time horizon (see limitations for more discussion on the importance of this question)? 

The way the method is introduced in terms of sufficient statistics creates the expectation that the method will be generally developed for any exponential conjugate prior. This extension would be worth considering for future work.

---- References ----

[1] Bui, T. D., Nguyen, C. V., and Turner, R. E. (2017). Streaming sparse Gaussian process approximations. In Advances in Neural Information Processing Systems 31, pages 3301–3309, Long Beach, California, USA. Curran Associates Inc.

[2] Stanton, S., Maddox, W., Delbridge, I., & Wilson, A. G. (2021, March). Kernel Interpolation for Scalable Online Gaussian Processes. In International Conference on Artificial Intelligence and Statistics (pp. 3133-3141). PMLR.

[3] Oord, A. V. D., Dieleman, S., Zen, H., Simonyan, K., Vinyals, O., Graves, A., ... & Kavukcuoglu, K. (2016). Wavenet: A generative model for raw audio. arXiv preprint arXiv:1609.03499.

[4] Solin, A., Hensman, J., & Turner, R. E. (2018). Infinite-horizon Gaussian processes. arXiv preprint arXiv:1811.06588.

limitations_and_societal_impact: There are some conceptual shortcomings of the method as proposed that prevent this good paper from being great. 

While the method is an online algorithm, it is not a streaming algorithm, and in practice streaming algorithms are necessary for deployment to most devices (for example, the sampling rate of a smartphone accelerometer is ~200 Hz [4]). The method is unlikely to be used in the (presumably low-latency) contexts of “... systems such as self-driving cars, robots, and financial trading algorithms…” until it is a streaming algorithm. In future work, it would be very intriguing to see if the method could be adapted to constant-time streaming sparse GPs, such as [1] or [2]. 

Along similar lines, the need to tune the hyperparameters offline is also a pretty serious limitation. In particular I see no reason why the \beta that worked well for one type of distribution shift would work well for another. The method could more plausibly be deployed if there was a sensible way to adapt the hyperparameters online.

The final limitation relates to the choice to model distribution shifts as binary changepoints. In particular, it would have been very interesting to see some experiments or discussion of the virtues of the changepoint detection class of methods vs. directly modeling possible shifts in the data generating process. As an example, in the rotated MNIST experiment, instead of modeling discrete (unknown) shifts, one could instead take the latent variable to be the average rotation (a continuous value). Obviously it would complicate the beam search process, but it would not be impossible, because one can always discretize a continuous signal (see e.g., the quantization scheme in [3]). I suspect that a well-specified hypothesis class of possible shifts would improve the speed of adaptation and allow for continuous shifts, which are an important case to consider (e.g. the relatively continuous shift in light intensity from day to night as a function of time).

Since this work relates to a very general class of methods, I have no concerns about potential social impact.
review_title: null

Meta-review: This paper proposed a Bayesian framework for detecting and adaptive to irregular distribution shifts. The reviewers generally appreciated the submission, and felt that the author response did a good job of addressing questions. While there were still some remaining questions about design decisions in the approach (see reviews), on the whole the paper represents a good contribution. Please carefully consider and incorporate reviewer comments in the final version.

Decision: Accept (Poster)