Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: This paper develops an algorithm for online variational inference and parameter learning in state-space models, where both model parameters and variational parameters are learned online with each new data point in the time series. The authors accomplish by approximating a backwards decomposition of the full posterior $p(x_{1:t}|y_{1:t}) = p(x_t|y_t) \prod_{k=1}^t p(x_k | y_{1:k}, x_{k+1})$ with a factored variational distribution $q_t(x_{1:t}) = q_t(x_t) \prod_{k=1}^{t-1} q_t(x_k | x_{k+1})$. This factored approximation is used to derive a (forward) recursive equation for computing the ELBO at time $t$, along with gradients of the ELBO with respect to the model and variational parameters. These recursive equations allow both the ELBO and its gradients to be estimated (using recursive learning of regressors) in an online manner, hence enabling online learning and inference. The authors evaluate this approach on two synthetic examples, and one example of video data, demonstrating that online inference successfully minimizes KL divergence to the true posterior as each new data point is observed, and that online learning successfully converges to plausible model parameters / transition dynamics, including in the video modeling task.
main_review: This was a nice paper to read. I thought it was clearly described and motivated, made use of the backwards decomposition of the posterior distribution in an insightful, original, and principled manner, and clearly demonstrated the utility of their approach relative to existing online baselines in a series of experiments. I just have a few clarificatory questions:

1. How fast is the regression step for $\hat T_t$ and $\hat S_t$? It was not immediately clear to me that this would take constant time, or exactly what kind of fitting was going on (it might be helpful to give a concrete example in the main text). I looked at the appendix, and it seems like it requires sampling some 500 and data points, and multiple iterations of fitting. This seems like it might be slightly too slow for some applications (e.g. real time robot tracking), and may require variable time if convergence of the regressor is desired.
2. Why is regression necessary at all, as opposed to Monte Carlo estimation of $T_t^{\theta,\phi}$ and $S_t^{\theta,\phi}$? Is it because they need to learned as functions of $x_t$ in order to be queried at different (sampled) values of $x_t$? Would it be possible to use (recursive) Monte Carlo approximations instead, avoiding the need for regression?
3. Are there potential issues with issues with the convergence of online learning, given that the recursive equations for $T_t^{\theta,\phi}$ and $S_t^{\theta,\phi}$ are not strictly followed once the parameters $\theta$ and $\phi$ are updated? e.g. $\hat S_{t-1}$ is learned using $\theta_{t-2}$, but $\hat S_t$ is learned using $\theta_{t-2}$. Perhaps there is RL theory addressing this?
4. How does this approach compare in speed / accuracy / computational cost versus amortized variational inference (e.g. learning an RNN as a recognition network)?

I also have the following minor comments:

- In the Abstract, I would personally avoid calling the decomposition / factorization "non-standard", because this gave me the impression that it might be unprincipled. "Backwards decomposition" would be more informative, and avoid that impression. Having read through the math fairly carefully, the proposed method is definitely principled in a way that I cannot say for many other papers that integrate variational inference with state space models.
- In Algorithm 1, there is a minor inconsistency between the update rules for $\phi_t$ and $\theta_t$ in terms of how the time-index subscripts are used.

Overall, I thought this was a solid paper. It could be made even stronger with a little more clarity on the regression steps, the inclusion of the AELBO baselines for the SVAE task, and additional comparisons of speed / accuracy to amortized inference methods, but the approach is adequately evaluated, well-motivated, and principled, and hence deserving of acceptance in my evaluation.

== Post-Rebuttal ==

Thank you to the authors for their detailed responses and clarifications. I believe that they have adequately responded to the questions raised by myself and other reviewers, and I will maintain my score of 8.
limitations_and_societal_impact: The authors adequately addressed limitations and society impacts. With the extra space in the camera ready version, I would also suggest discussing their method in comparison with amortized variational inference in SSMs (e.g. using RNNs), which are also able to perform constant-time inference of new latent states after batch-wise training on a dataset of sequences. This means additional training cost, and potential overfitting, but potentially lower cost at inference time. It would be good to discuss the costs and benefits of each approach.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The paper borrows the ideas from reinforcement learning to come up with an online inference and learning for state-space models. It focuses on the smoothing distribution instead of the usual filtering distribution for online learning. When performing variational EM with the new incoming data, the ELBO is recursively updated, and the gradients are estimated with a regressor. Experiments show good performance on various datasets.
main_review: The paper proposes a novel online inference scheme for state-space models. The paper is generally clear and well-written. Here are some unaddressed points in my mind:
- It seems the (auxiliary) neural network for gradient estimation is learned in advance. If this is the case, in a non-stationary environment, will this estimation become outdated as the network is stationary? 
To train the auxiliary neural networks for gradient estimation, an additional dataset is also needed. This seems not a desideratum of an online setup where an additional dataset is usually not available.
- Does it also work for model-based reinforcement learning since it borrows ideas from RL applications? If so, how does it perform?
limitations_and_societal_impact: It would be great to state which requirement does not coincide with the usual online learning setup.
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: This paper presents a variational inference algorithm for state-space models, that is suitable for online learning: at each time step, the variational posterior approximation can be updated to account for the new data in constant time. Parameters of the generative model can also be learned online. The algorithm is based on variational families $q_t^\phi$ that factor as $q^{\phi_t}(x_t \mid y_{1:t}) \prod_{i=t}^2 q^{\phi_{i}}(x_{i-1} \mid x_i, y_{1:i-1})$. The key point is that when a new datapoint $y_{t+1}$ is observed, the optimal backward kernels $p(x_{i-1} \mid x_{i})$ (which the $q^{\phi_i}(x_{i-1} \mid x_i)$ approximate) do not change for $i = 1,\dots,t$. The authors use this to justify freezing the parameters $\phi_i$ after time step $i$, so that at each time step, only the parameters $\phi_{t+1}$ must be learned. Besides this factorization, the other trick enabling online learning is a scheme for estimating gradients of the ELBO with respect to $\phi_{t+1}$ in constant time. This requires an additional approximation step, leading to biased gradient estimates. However, in experiments on several models and datasets, the authors show that their proposed technique can produce reasonable results in practice.

main_review: This is a nicely written paper that presents (to my knowledge) a novel technique for online inference in state-space models, and validates it empirically in three compelling experiments. The exposition is clear and provides good intuition for the key insights behind Algorithm 1. I think the paper is of definite value and interest to the NeurIPS community and recommend acceptance.
	
However, I have a less clear picture of what exactly is happening theoretically. One question is what penalty  we should expect to incur (e.g., compared to batch variational inference) by using this online variant. Intuitively, we might expect that in the "online" Algorithm 1, the learned parameters $\phi$ would, assuming a sufficiently high number $M$ of gradient updates per time step, recover the optimal "batch" solution using the same variational family—i.e., the parameter settings you'd find if you optimized $L_t$ with respect to all of $\phi$ at once. But I believe this is not the case in general, because although $p_\theta(x_k \mid y^k, x_{k+1})$ does not depend on observations past time $k$, the optimal $q^{\phi}(x_k \mid y^k, x_{k+1})$ might. This is because, if $q^\phi(x_k \mid y^k, x_{k+1})$ cannot perfectly represent the true backward kernel, it will prioritize accurate backward transitions for the most probable values of $x_{k+1}$. Since the posterior on $x_{k+1}$ does change as new data comes in, the optimal $q$'s priorities also change. The experiments suggest that this may not be a problem in practice, perhaps because $q(x_k \mid x_{k+1})$ is sufficiently expressive to learn an accurate backward kernel for all $x_{k+1}$, or because in these particular datasets, the filtering and smoothing distributions over $x_{k+1}$ were sufficiently similar. But it might be nice to see some discussion of this issue, and/or an empirical validation that the online and batch variants learn similar variational approximations in practice.
	
A similar issue arises, I think, with the biased gradient estimates — L296-297 point out the importance of using sufficiently expressive function approximators to reduce the bias, but it also seems important that the training data used to optimize the approximators be from a good distribution. If I'm following correctly, the "training data" distribution for the approximators $\hat{T}$ and $\hat{S}$ are not equal to their "test time" distributions, which incorporate an additional data point. Could this introduce appreciable error in practice?
	
Overall, I suspect both these concerns are nitpicks -- but perhaps they could be signposted as assumptions the algorithm makes. To reiterate my overall positive impression of the work, I think the paper presents a clever idea with clear exposition and convincing experiments. 
	
One very minor comment: in discussing [30], L222-223 state that "any" particle filtering technique will scale poorly when the state is high-dimensional, but this seems a harder claim to defend when the technique uses learned / well-adapted proposal distributions. (In any case, it is not a reason to dismiss PF in favor of VI; if you have a variational approximation to the posterior, you could use it within a particle filter as the proposal, and the accuracy should only improve.)
limitations_and_societal_impact: The authors include a limitations section, which I think is adequate, but could be expanded to discuss the issues raised in the main review. I did not see discussion of the potential negative societal impact, but the work is theoretical enough that I am not sure it is necessary to include.
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: This paper proposes a variational filtering scheme for state space models that enables recursion to successively estimate the ELBO to achieve efficient inference. Experiments are performed on linear Gaussian filtering, RNN estimation, and sequential VAEs.

main_review: tldr: I tend to weakly accept this paper, although I would strongly encourage the authors to make the connection to reinforcement learning way more explicit in the paper. 

edit: after the author(s)' rebuttal, I tend to accept the paper. Thank you for the clarifications.

## Originality

*Are the tasks or methods new?* Yes, I haven't seen any sort of recursive filtering mechanism for state space models like this before.

*Is the work a novel combination of well-known techniques?* Yes, this is probably a novel combination of variational filtering with the variational interpretation of reinforcement learning models in the sense of [Levine, '18](https://arxiv.org/abs/1805.00909) and [Fellows et al, '18](https://arxiv.org/abs/1811.01132). Note that this is a positive comment.

*Is it clear how this work differs from previous contributions?* Yes, it's pretty clear how it differs from other approaches in the state-space models literature.

*Is related work adequately cited?* Yes, overall, I think so. See discussion + the papers listed above as well.

## Quality

*Is the submission technically sound?* Yes, it seems to be. The proofs seem to be mostly algebraic book-keeping (which is fine). 
- I would have liked to have more details about the function approximators that use $\hat S_{t+1}$ and $\hat T_{t+1}$ in lines 161-180. 

*Are claims well supported (e.g., by theoretical analysis or experimental results)?* 
Yes, see comment above. The experimental results suggest that the method works pretty well.

*Are the methods used appropriate?* 
Yes, overall. Not knowing the literature well I'd like to know how KRR is used in line 165.

*Is this a complete piece of work or work in progress?* This looks like a complete work.

*Are the authors careful and honest about evaluating both the strengths and weaknesses of their work?* Mostly, see discussion.

## Significance

*Are the results important?* Yes, better variational inference techniques for state space models are likely to encourage their usage in practice, while the technical connection to the Bellman recursion (I think) is probably important.

*Are others (researchers or practitioners) likely to use the ideas or build on them?* Yes, probably.

*Does the submission address a difficult task in a better way than previous work?* Yes.

*Does it advance the state of the art in a demonstrable way?* Yes.

*Does it provide unique data, unique conclusions about existing data, or a unique theoretical or experimental approach?* A unique theoretical / practical approach.

## Discussion

- While I agree that the connection to reinforcement learning is there (I think this is closely related to the Bellman recursion and dynamics models), the authors really need to do some more work to formalize this connection as otherwise, it's really lost on the reader and is a bit of a weakness. 
    - RL can be constructed as probabilistic (and really variational) inference as in [Levine, '18](https://arxiv.org/abs/1805.00909) and succeeding works, so this work could help bridge the gap between these types of interpretations of RL and state space models generically. 
    - However, none of the connections are made explicit so it's a bit tricky to tell right now what the impact is. Improving these connections would significantly improve the paper.
    - specifically, my concerns are about the paragraphs in lines 122 (I think you're referring to the bellman recursion but not sure), 

### Questions

- While I understand that the time complexity is constant per iteration, it still seems like there is $t$ separate operations that much be computed. Does this mean that as the number of time steps increases, the method slows down over time?
    - Or is there only a single pass being computed through the sequence?

- In Fig. 1b why does the quality of the variational approximation get worse as the number of steps?
    - Is this overfitting or the quality of the variational approximation breaking down?

- How are the number of steps of SGD / Adam chosen in the inner loop?

- How are the summary models (either krr or mlp) initialized and with what sort of data? These are the models using $\hat S$ and $\hat T$?
    - Why doesn't computation for the KRR slow down over time?

- Is fig 1a just the first 10 time steps? Is there a tradeoff between "time per iteration" and "accuracy" here? If so, how is the tradeoff chosen?

### Writing Comments

20: network[s]

24: [estimating?] "online inference" 

29: ref for "notoriously unreliable" as a non-expert in this field, i'd like to see a reference to verify.

limitations_and_societal_impact: yes
review_title: null

Meta-review: The authors propose a general scheme for approximation in state space systems where the variation distribution is conditioned _backwards_ in time.  This leads to an ELBO (and gradients) that can be computed online, without having to adjust previous terms. 

The reviewers unanimously praised the clarity of the writing, and I was impressed that each reviewer was left with a very clear picture of the paper's contribution and relevance - a sign that the idea has been presented with great clarity. 

One clarification that arouse during the discussion was around a regression that occurs at time step $t+1$, and whether the input/output pairs here are drawn in such a way that could introduce error. I'm happy with the authors' clarification, which I anticipate in the camera ready manuscript. 

One in-depth discussion between a reviewer and the authors covered connections to reinforcement learning: the authors connect Bellman recursion to the ELBO updates. This discussion could make for a neat appendix to the paper. 
 
Decision: Accept (Oral)