Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: In this paper, a method BAM is proposed for Bayesian learning in non-stationary environments: basically, at each time step, each previous datum may or may not be incorporated into the new posterior, so that old data from different states can be ignored, while old data from the same or similar states is remembered. The method doesn't rely on parametric assumptions. Experiments demonstrate it to work well in various scenarios.
main_review: Strengths:

- The theoretical development is principled;

- This approach seems to be novel (though I'm not familiar with the literature on Bayesian methods for non-stationary environments);

- The paper is clearly written.

Concerns:

None.

Minor points:

- In equations (11) and (12), shouldn't $\theta_t$ be $\theta$, as it is assumed not to change with $t$ here?

- Equation (17) is just a normalisation constant. Since (14) and (16) are also given only up to constants, is it worthwhile to include?

- Several times in section 2.1: "preventing BAM from overfitting" sounds like BAM won't overfit at all. Could you change the wording to reflect that regularisation reduces the chance/severity of overfitting, without preventing it altogether?

- Below equation (23) and in appendix C: $(t-1)!$ should be $2^{t-1}$

- Algorithm 1: While "Bottom's Up" [sic] is a nice name, I think the term you're looking for is "Bottom-Up" :)
summary_of_the_review: I enjoyed reading this paper. Assuming that this idea is as novel as claimed, I think this is a valuable contribution to the community and recommend acceptance.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: In this paper, the authors propose a new framework, Bayes Augmented with Memory (BAM), that takes advantage of past experience by allowing the agent to choose which past observations to remember and which to forget and demonstrate that BAM generalizes many popular Bayesian update rules for non-stationary environments. 
main_review: In this paper, the authors propose a new framework, Bayes Augmented with Memory (BAM), that takes advantage of past experience by allowing the agent to choose which past observations to remember and which to forget and demonstrate that BAM generalizes many popular Bayesian update rules for non-stationary environments. The variety of experiments demonstrate the ability of BAM to continuously adapt in an ever-changing world.

To the best of my knowledge, this is generally a good paper with a clear central idea. I have only two minor concerns:

For simplicity, this paper focused on binary values for the readout weights as it allowed for a simple greedy discrete optimization algorithm to be used. This assumption limits its practical application scenarios.

Although a simple greedy discrete optimization algorithm to be used, it still makes the proposed BAM have a relatively high time complexity. The paper could be improved if the authors can provide the time complexity of the proposed BAM. If it is difficulty, the comparison results in terms of the running time are needed.

summary_of_the_review: In this paper, the authors propose a new framework, Bayes Augmented with Memory (BAM), that takes advantage of past experience by allowing the agent to choose which past observations to remember and which to forget and demonstrate that BAM generalizes many popular Bayesian update rules for non-stationary environments. The variety of experiments demonstrate the ability of BAM to continuously adapt in an ever-changing world.

To the best of my knowledge, this is generally a good paper with a clear central idea. I have only two minor concerns:

For simplicity, this paper focused on binary values for the readout weights as it allowed for a simple greedy discrete optimization algorithm to be used. This assumption limits its practical application scenarios.

Although a simple greedy discrete optimization algorithm to be used, it still makes the proposed BAM have a relatively high time complexity. The paper could be improved if the authors can provide the time complexity of the proposed BAM. If it is difficulty, the comparison results in terms of the running time are needed.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The paper aims to solve the downside of the posterior shrinkage of Bayesian online learning when applied in a non-stationary environment. The previously posterior (a.k.a., the current prior) could be misspecified for current observations with the posterior shrinkage due to the environment change. To solve this misspecification problem, the proposed method constructs an adaptive prior that is correctly specified for current observations. This adaptive prior distribution is constructed by selecting the previous relevant data samples, which requires storing the whole history. The method is evaluated on various analytical experiments.
main_review: The paper tackles an important problem of Bayesian online learning in a non-stationary environment. The main contribution is BAM, an algorithm that constructs an informative prior distribution for current observations based on stored previous data. While the method seems technically sound, the method still falls short of the following points:

1) **Scalability**: the algorithm remembers all the data so far, which requires infinite memory in an ever-running system. So as to the computation. The algorithm will fail in an online learning environment. An immediate improvement would be to use a fixed memory. A similar idea occurs in continual learning with a memory system where people only select representative data into a fixed memory (see the following point).

2) **Proper related work discussion**: At least there are two highly-related papers not mentioned in the current version:

    - Li, Aodong, et al., “Detecting and Adapting to Irregular Distribution Shifts in Bayesian Online Learning”, NeurIPS 2021 (previously occurred in workshops).
    - Kurle, Richard, et al., "Continual learning with bayesian neural networks for non-stationary data." ICLR 2020.

    *(Possibly) related work in other fields*:

    *Continual learning with a fixed-size memory*:
    - Aljundi, Rahaf, et al. "Gradient-based sample selection for online continual learning." Advances in Neural Information Processing Systems 32 (2019): 11816-11825.

    *Bayesian inference with weighted likelihood*:
    - Wang, Yixin, Alp Kucukelbir, and David M. Blei. "Robust probabilistic modeling with bayesian data reweighting." International Conference on Machine Learning. PMLR, 2017.
    - Mandt, Stephan, et al. "Variational tempering." Artificial Intelligence and Statistics. PMLR, 2016.

3) **Large-scale experiments**: Current experiments are all analytical. However, practical systems could be complex, intractable, and large-scale in time. Without demonstrating the applicability in these environments, the approach may be not convincing.

4) **Baseline comparisons**: The paper conducted thorough experiments with baselines including ordinary Bayesian online learning and BOCD. However, existing baselines have obvious limitations and couldn’t properly illustrate the benefits of the additional memory and re-visited states. More adaptive baselines like Bayesian Forgetting or Bayesian filter can be desirable to exemplify the usefulness of memory in a changing environment.

Other additional comments/suggestions:
* $p(W_t|D_{<t}) \propto 1$: Should $W_t$ take some value?
* May consider change colors in Fig. 1 (left). Hard to distinguish methods.
* Fig. 5 is out of the main text.

summary_of_the_review: The paper could be an interesting contribution in the area of Bayesian online learning in a non-stationary environment. However, unless solving the scalability problem and demonstrating the benefits of the memory, the paper isn’t persuasive enough.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper proposes a learning framework called Bayes Augmented with Memory (BAM), where a recursive adaptation of the Bayes formula is augmented with selection variables $W$ to allow an agent to adaptively choose past experiences to forget. The original recursive Bayes formula assumes the stationarity of the data generating distribution, so keep all the past data for updating the posteriors for newly arriving data, and thus always tends to decrease the variance of the posteriors as it is meant to be. However, this can severely fail when the stationarity assumption is violated; when an agent encounters a change in the environment, it should somehow discard the past experience and quickly adapt to new data. BAM explicitly models this procedure with the binary selection variables, and by greedily optimizing those selection variables at each entrance of new data, quickly adapt to the change of environment and still leverages the past experiences. Various experiments with non-stationary environments demonstrate the usefulness of the proposed framework.
main_review: The paper is well written and easy to follow. The motivation is clear and the problem is well set. The proposed learning framework is a reasonable solution in principle. The experiments clearly demonstrate the benefit of BAM, especially its ability to adapt to the change of environments.

However, I'm a bit skeptical about the practicability of the proposed framework. All the elements of the algorithm, including the posterior updates and greedy selection procedure, assume the traceability of the marginal likelihood, which is not true in most non-trivial real-world applications.  As the authors stated in the conclusion, one can introduce variational approximations or MCMC to conduct approximate inference, but these are way harder than it looks since now each evaluation of $p(\theta_t|W, D_{<t})$ requires an iterative procedure requiring heavy computation until convergence, so the greedy selection procedure can be prohibitively time-consuming. As the authors pointed out when relating BAM to the existing works, and also suggested as future work, one can allow the selection variables $W$ to be any real number between $[0,1]$. Then we can resort to gradient-based approximate optimization techniques (e.g., based on variational approximation with Gumbel-softmax), but at this time it is not clear how accurate all such approximate inference techniques (especially for high-dimensional models such as deep neural networks applied to large-scale data). One should also think about an alternative prior $p(W|\theta_t)$ because the KL-divergence needed for the current prior is intractable.

So my point is, there are many obstacles to be addressed if we are to extend the current BAM framework for realistic scenarios, and all of such issues pose their own research problems that might require contributions significant enough to write standalone papers. Therefore, I think the current submission is quite incomplete, although I agree that the research direction itself is interesting.

Another practical aspect that is worth pondering is how the proposed framework compares to existing continual learning techniques introduced for deep neural networks. There are plenty of works for deep continual learning, where the goal is to learn large-scale deep neural networks while taking a continuous stream of non-stationary task data. Existing continual learning techniques learn to adaptively forget or retain past experiences, and also try to minimize the cost of learning and the complexity of the model (minimize the unnecessary expansion of the model).  Especially, an important consideration in continual learning is that it typically assumes that an agent doesn't have access to the previous data ($D_{<t}$), but only to the model learned from it. This is a reasonable assumption because keeping all the past data requires huge memory. So the difficulty in continual learning comes from the fact that it should learn continuously adapting model which keeps a balance between 1) how much to forget and 2) how much to retain past experiences, without access to the previous data. For instance, variational continual learning (Nguyen et al., 2018) constructs a lightweight summary of previous data that can be used as a representative for the subsequent learning. As far as I can see, BAM assumes access to all the previous data whenever updating the posteriors, and this again can be a significant challenge for more realistic learning scenarios.

I'm also quite confused with the name "Bayes augmented with memory". What does the "memory" stand for? If it is for the past data being used for the update of the posteriors, isn't the vanilla recursive Bayes also augmented with memory? The difference between BAM and the recursive Bayes is in BAM's use of the readout variable $W$, but I don't think the variable $W$ itself stands for the "memory".

References
(Nguyen et al., 2018) Nguyen, C. V., Li, Y., Bui, T. D., and Turner, R. E. Variational continual learning. ICLR, 2018.
summary_of_the_review: I think the proposed framework can be potentially interesting and useful, but at current presentation lacks many practical considerations to be dealt with, especially how it can be applied to non-trivial models requiring approximate inference for computing posteriors. It is quite disappointing thus to only see experiments on conjugate models.
review_title: null

Meta-review: The article introduces a Bayesian approach for online learning in non-stationary environments. The approach, which bears similarities with weighted likelihood estimation methods, associate a binary weight to each past observation, indicating if this observation should be including or not to compute the posterior. The weights are estimated via maximum a posteriori. 

The paper is well written, the approach is novel and its usefulness demonstrated on a number of different experiments. The original submission missed some relevant references that have been added in the revision. The approach has some limitations, highlighted by the reviewers:
* it requires to solve a binary optimisation problem whose complexity scales exponentially with the size of the dataset; although the greedy procedure proposed by the authors seems to work fine on the examples shown, the approach may not be applicable to larger datasets
* it requires to store all the data
* it requires the traceability of the marginal likelihood

Despite these limitations, there was a general agreement that this paper offers a novel and useful contribution, and I recommend acceptance. 

As noted by reviewer o4TK, I also think that the title is not very accurate. Bayesian methods naturally allow recursive updates of one's beliefs, and therefore have "memory". Maybe change the title for "Bayes with augmented selective/adaptive memory"?
Decision: Accept (Poster)