Implicit Maximum a Posteriori Filtering via Adaptive Optimization

Summary

The paper explains how sequentially optimising the likelihood of a nonlinear time-series estimation problem with any given optimiser can be interpreted as implicitly (point-)estimating the solution of a specific filtering problem. The difference to existing interpretations of filtering algorithms through the lens of optimisation problems (e.g. the iterated extended Kalman filter) is that the proposed approach only requires access to an optimisation routine, a sequence of likelihood functions, and the mean of a temporal transition model. *The Kalman filter's need for prescribing process noise covariance functions of the temporal transition model is replaced by the need for prescribing optimisation algorithms.* Most popular optimisation algorithms scale to high-dimensional settings; most Kalman filter variations do not (because they use covariance information). This approach takes inspiration from a result by Santos (1996) that states the equivalence between truncated gradient descent and solutions of least-squares-type problems. The scalability of the resulting algorithm is demonstrated, among other things, by applying the method to a high-dimensional state-space model representing the weight space of a neural network.

Strengths

The paper is well written with a high level of clarity, including the experiment selection, and the algorithm is an enjoyable application of Santos' (1996) result to (nonlinear) filtering problems. The resulting algorithm is so simple that anyone with previous exposure to optimisation or filtering algorithms could implement it. I appreciate the honest assessment of limitations; for instance, the method does not deliver any uncertainty quantification. Overall, I think this paper is in good shape.

Weaknesses

While I do like the paper, I think that the algorithm/presentation has some (minor) issues: 1. **From linear to nonlinear problems:** For linear problems, Santos (1996) shows that a choice of a (truncated) gradient descent corresponds to an implicit choice of predictive covariances. Thus, for linear problems, estimating the filtering-mean by applying a suitably truncated version of gradient descent "makes sense" -- provided the prior model implicit to the length-scale in gradient descent "makes sense". Using the same idea for nonlinear problems, arbitrary optimisers, and possibly optimisers with momentum is, technically speaking, a leap of faith, and there is nothing to support this transition other than "it seems to work well on the test problems". Fortunately, it does seem to work well on the test problems. (Unless one chooses to use AdaDelta, that is.) 2. **Sensitivity to misspecification:** I am unsure about how, in some parts of the manuscript, the paper describes the implicit MAP filter to be robust against misspecification of the prior. For example, the last paragraph on page 6 reads: "Since the Implicit MAP Filter does not explicitly use the process noise $Q_t$, there is no sensitivity to misspecification, as indicated by the empty columns in Table 1." I think this statement might be somewhat misphrased because choosing the "wrong" optimiser is not unlike prescribing the wrong process noise covariance. In other words, while the implicit MAP filter is, by construction, not sensitive to _explicit_ misspecification of the prior model, it can suffer from misspecification: according to Santos' (1996) results, choosing the wrong length-scale for truncated gradient descent leads to similarly inaccurate approximations as passing the false process noise to a Kalman filter. If we extrapolate a bit by replacing "length-scale" with "optimiser" in the sentences above, we could think of choosing the wrong optimiser as equivalent to selecting the wrong prior model -- this would be model misspecification. The perspective of the wrong optimiser not being unrelated to model-misspecification is corroborated by Table 1: In Table 1, AdaDelta performs *much* worse than other optimisers. In general, I think the first point is a clear disadvantage, but a disadvantage one has to live with (unless I have missed something, in which case I am open to correcting my assessment). The second point is minor because it mainly affects the phrasing in Section 5.1. It should be relatively straightforward to fix. In general, I think that the strengths outweigh the weaknesses, so I vote for accepting this submission.

Questions

None

Rating

8: accept, good paper

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Summary

This work proposes methodology for recursively obtaining point estimates of the states in a Bayesian filtering setting. Specifically, the authors first show that the Kalman filter can be equivalently phrased as a recursive truncated gradient-descent. They then explain that certain hyperparameters used by the optimiser (e.g., the number of gradient steps taken at each time step) can be interpreted as implicitly specifying a particular process-noise variance. Finally, the authors propose to linearise the mean of the state-transition equation in order to deal with models in which this mean is a non-linear function of the previous state. The authors argue that their methodology is more robust than Kalman- or particle-filtering type methods because it does not need to know true the process-noise variance.

Strengths

**Originality** Although it relies heavily on previous work by Santos (1996) (as the authors make clear), the proposed approach seems novel. **Quality** I believe that this work is of sufficient quality to be, in principle, publishable in ICLR. **Clarity** Overall, the presentation is clear. I only have some minor concerns detailed below. **Significance** In higher-dimensional problems, in which Monte Carlo sampling may become prohibitively costly, I agree that optimisation-based approaches (like the present work) can be sensible. And the "Yearbook" example seems to support this view. In this regard, I believe that this work makes a worthy contribution.

Weaknesses

**Choice of hyperparameters** I think Table 1 could slightly misleading because the hyperparameters of the proposed methodology are optimised based on a grid search using (other?) data based on (presumably) the same "true" process- and observation noise parameters. In other words, optimising these hyperparameters via a grid search is not dissimilar to letting competing methods (e.g., Kalman or particle filtering-type methods) learn the process- and observation noise parameters from other data sets. And if we did the latter, they would not suffer from the misspecification of $Q_{t-1}$ shown in Table 1. **Clarity** It would be good if the authors could provide a bit more detail and intuition in the second half of Section 3.1 and in Section 3.2, e.g., about * the role of the matrices $B_t$ and $C_t$ and why we can be sure that these are well defined. * the learning-rate matrix (maybe just state the plain gradient-descent update equation which includes this matrix). There are also a few minor typos, e.g. the notation $\mathbb{E}[p(x_t|y_{1:t-1})]$ does not make sense (presumably $\mathbb{E}[x_t|y_{1:t-1}]$ is meant)? Finally, in Section 4, I'm not sure Equation 13 and the discussion about the delta-method is really needed.

Questions

Some of the "true" model parameters (especially the process and observation noise) in the examples from Sections 5.1 and 5.2 seem to be slightly different than those used in the references cited for these applications. Is there a particular reason for this change? And do the results in these sections differ qualitatively if the parameters from the literature were used? I am willing to raise my score if the authors can show that the results in Sections 5.1--5.2 are robust to the choice of model parameters.

Rating

6: marginally above the acceptance threshold

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

4 excellent

Contribution

3 good

Summary

This paper proposes to do inference in non-linear, non-Gaussian state space models using an introduced technique termed the "implicit MAP filter". The key idea underlying the proposed method is to build on an observation of Santos (1996) that connects regularized least squares solutions to those obtained by running truncated gradient descent. Translated to the state space model inference context, the choice of steps implicitly defines a prior on the transition process, hence truncated optimization can be viewed as doing Bayesian MAP estimation in the state space model. The authors demonstrate their proposed method on two classical examples from the Particle Filter literature and an online inference task utilizing a pretrained network. It is shown that the proposed method is competitive with standard techniques, and works particularly well on the Lorenz-96 model.

Strengths

The question that the paper attempts to address, namely online learning of state space models, is important in a variety of contexts and the authors offer a concrete pathway to do so, via their proposed optimization framework. The paper provides a potential novel direction that can be followed and certainly developed further, due to, notably, the computational cost savings from looking at optimization as an alternative to (explicit) filtering approaches. The paper is clearly written and easy to read, and the results can be reproduced without much difficulty.

Weaknesses

The interpretation of the number of steps as a prior (or as a regularizer) is not very intuitive. The authors should provide at least some minimal guidance on tuning the number of optimizer steps K and selecting the optimizer itself. The authors should note some of the modern KF based research in this space (Chang et al. 2023 (https://arxiv.org/abs/2305.19535), Titsias et al. 2023 (https://arxiv.org/abs/2306.08448)) that successfully works on larger-scale problems than the ones considered in this paper. The experiments chosen are somewhat small-scale given that the authors' argument for not having access to estimates of uncertainty is having a scalable method. Since the authors explicitly connect the choice of optimizer to defining a prior, they should for example compare different optimizers to one another on the same problem. Have you tried doing this?

Questions

My questions mainly concern the practical uses and developing a better understanding of the proposed method. Table 1 states that the MAP methods are not dependent on the process noise covariance Q_t-1, which is true, but they are dependent on the number of steps K, which as stated earlier, in e.g., 3.3, implicitly defines a prior. The authors however state that there is no sensitivity to missspecification (last paragraph of Page 6). This should be clarified. How robust is the method to the number of steps K? What if you run the optimizer essentially until convergence every time, truncating many steps ahead? What if you only do one step of the optimizer. Perhaps the method is not too sensitive to this, but this should be verified and made clear and this aspect of the method should be studied further. How would the method compare to some of the more modern KF-based methods mentioned earlier, especially on the neural network problem and with some of the datasets that are used there? In practical contexts, we often don't have access to a pretrained model. How would the method perform when the model is trained completely from scratch?

Rating

6: marginally above the acceptance threshold

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Revised version of the paper just uploaded

We just uploaded a revised version of the paper. We thank all three reviewers for their excellent feedback. Detailed below are the list of changes. TL;DR: Added experiments to toy nonlinear system and Lorenz attractor that significantly improve argument. Rewrote Section on implicit MAP filter update step to give better intuition. Rewrote the experimental section to be more succinct, precise, and sound with our argument. Added reference to (Chang et al., 2023) in the related work. Fixed typos, improved writing and clarity throughout the paper. [Complete List of Changes] - Stochastic Lorenz Attractor results: We added results where we specified a grid search for the EKF and UKF instead of only using the true model parameters. We make a stronger “misspecification argument” here and the experiments are more sound given this grid search for the baseline methods. We ran all methods for three additional process noise specifications. In total, we have results for alpha = 1, 5, 10, 20. We report alpha = 10 in the main section (as before) and alpha = 1, 5, 20 in the Appendix. Optimized EKF and Implicit MAP Filter were the best and had statistically equivalent performance. However, Implicit MAP Filter has several distinct advantages we mention in the paper. We believe that 5.2 is much more sound and the advantages of our approach are much more clear now. - Toy nonlinear system results: the optimizer misspecification argument we originally included is now being made in Section 5.2. In the place of the original 5.1 results, we show results over 9 different true model parameters (originally we just showed results for one set of true model parameters). The results are consistent and show that the proposed method can be competitive with the UKF, PF as before…except now it is over 9 toy nonlinear systems instead of 1. We believe this makes the paper significantly stronger. - Added 5 more tables to the Appendix showcases additional results and added additional writing to the extended experimental section. The reader now has access to a much richer set of results. - Yearbook dataset results: We made the section more succinct and added a sentence about how this approach is easily adapted to the case where we do not start with a pre-trained network. - Implicit MAP filter update rule section: completely re-written to offer better intuition for what is happening at the update step and how the choice of optimizer, number of steps, and initialization implicitly chooses the prior. - Removed unnecessary delta-rule explanation when introducing the implicit MAP filter - Added reference to (Chang et al., 2023) in the related work. - Figure 1 (figure and caption) adapted for better clarity. - Improved writing and clarity concerns in Bayesian Filtering as Optimization section