Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: In this paper, a fast algorithm for the probabilistic solution of BVPs are proposed. Comparing with the classical deterministic methods, the proposed method allows computing a posterior distribution in linear time while further delivers uncertainty quantification, mesh refinement and hyperparameter adaptation.
main_review: The paper is generally written well. The mathematical derivations seem proper and the discussions on initial guess, mesh refinement and hyperparameter calibration are helpful.

My main concern about the paper is its lack of comparison with baseline methods. Bayesian approach for BVPs was discussed in many classical uncertainty quantification literatures, for example:
Chkrebtii, O. A., Campbell, D. A., Calderhead, B., & Girolami, M. A. (2016). Bayesian solution uncertainty quantification for differential equations. Bayesian Analysis, 11(4), 1239-1267.
O'Leary, P., & Harker, M. (2014, May). Inverse boundary value problems with uncertain boundary values and their relevance to inclinometer measurements. In 2014 IEEE International Instrumentation and Measurement Technology Conference (I2MTC) Proceedings (pp. 165-169). IEEE.
However, the authors didn't provide a thorough review on these previous works in the area nor situate their approach with respect to them.

Another possible pitfall is: BVP problems can be ill-posed. How does the proposed method perform on those problems?
limitations_and_societal_impact: See main review.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper discusses refinements to current probabilistic BVP solvers, namely the IEKS. The paper proposes new initialisation and meshing strategies for speed-up. This is an interesting paper with potentially high impact.

main_review: Post-discussion update. The authors have adressed my concerns, and this work does improve over earlier work substantially, and there is sufficient discussion about this. Some issues still stand, but I'm nevertheless raising my score to 6, and would be happy to see this paper accepted. 

--------

The paper discusses refinements to current probabilistic BVP solvers, namely the IEKS. The paper proposes new initialisation and meshing strategies to speed-up the method. This is an interesting paper with potentially high impact.

I’m having lots of trouble understanding the papers notation and nomenclature. The paper talks of posteriors without introducing any priors or likelihoods. The math is incomplete (see below). This makes following the paper unnecessarily difficult. In NIPS papers should be accessible to wide audience, and not limited by subdomain shortcuts. The sec 3 would be easier to follow if one would mathematically define at least the gist of bridge and EKS, currently the method is only in the appendix.

The paper is otherwise well written. All the methods are sensible and the individual improvements are demonstrated also empirically.

There is strangely no empirical comparisons between the final tuned IEKS and the vanilla IEKS. I don’t understand why this is missing, since the main contribution of the paper is to improve upon IEKS (or is it..). Maybe the authors feel that this would be too trivial experiment. However, the improvements gained from the individual “tricks” have varied effects, and its not clear which one improves what part of the performance. In fig5 one already gets very low residuals with vanilla method, and in fig 6 the reference method seems way faster. The authors claim that this work is the first practically usable probabilistic solver, but the impracticality of IEKS was not shown in any way. The results should also contain ablation studies of all parts or combinations of the new ideas.

The paper proposes well-thought refinements to probabilistic BVP, but the empirical evaluation of the refinements seems incomplete or lacking. 


Other comments:
* The learning problem is unclear from page 1, what is it?
* What do the ball/diamond mean in fig 1?
* The paper’s notation is a bit complex. The start of sec 2.1. does not define \nu. What is a single Y_i? The notation Y : t -> R is unnecessarily complex. \Gamma does not connect anywhere. What is “integrated” wiener (reference)? How come Y has a derivative if its Wiener?  
* Why is eq 5 a posterior? It looks just a conditional distribution since we haven't placed any priors to the losses \ell. Similarly this does not look like MAP, but constrained global optimisation.
* What is p(Y(t) | ..)? Please define
* Why is \ell_n nonlinear? Eq 4 looks linear. 
* eq 7 drops the zero-conditioning, how do we condition here if not 0?

limitations_and_societal_impact: Limitations could be clearer.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The manuscript entitled “Linear-Time Probabilistic Solution of Boundary Value Problems” introduces a Gauss–Markov prior and tailors it specifically to BVPs, which allows computing a posterior distribution over the solution in linear time, at a quality and cost comparable to that of well established, non-probabilistic methods. Existing probabilistic solvers has cubic complexity which puts severe upper limits on grid resolution. Traditional, non-probabilistic BVP solvers are very efficient but do not provide probabilistic output. Thereby, they would have to serve as black-boxes inside probabilistic programs. 
The main contribution of this work is that this proposed solver can deliver uncertainty quantification, mesh refinement, and hyperparameter adaptation with linear time (although it is still much slower than the non-probabilistic BVP solvers). This results in a usable probabilistic BVP solver that is natively compatible with other parts of the statistical modelling tool-chain.


main_review: In general, this paper is in a good shape. I have some comments on this paper as follows:

1.	Figure 5 shows too many EM updates are not optimal either (RIGHT). The authors should give an explanation for this phenomenon.

2.	In Figure 6, the legend sits on Subplot 3. However, this legend should belong to all these 4 subplots. Also, the legend shouldn’t cover the data points on the plots. 

3.	Although the proposed solver has linear-time complexity in terms of the number of grids, it is about 100 times slower than the off-the-shelf probabilistic solver which also has linear-time complexity. Authors should comment on what causes such a slowness compared with the non-probabilistic solver.

4.	I don’t see the appendix for this paper although the paper says it has.


This paper tries to close the gap between the probabilistic and non-probabilistic BVP solvers such that the new proposed probabilistic BVP solver has a linear-time complexity which is much better than the exiting probabilistic BVP solvers, and it can deliver the algorithmic parameters automatically, including some that have to be set manually for non-probabilistic solvers. It beats non-probabilistic BVP solvers in a way that this solver is naturally compatible with other statistical modelling tool-chain. Although the experimental results show this solver is still much slower and gets poorer point estimates than the off-the-shelf non-probabilistic solvers. But it made some improvements for the probabilistic BVP solvers. This paper has its significance.

In summary, I recommend its publication in NeurIPS after those issues are addressed.
limitations_and_societal_impact: The author should address more of this solver’s limitations and discuss the potential improvement in the future. Limitations can be the Markov assumption, poorer point estimation than non-probabilistic solvers, the slowness of the computation compared with the off-the-shelf non-probabilistic solvers,
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: This paper introduces a probabilistic boundary value problem solver that inherits much of its background from the similar  Gaussian filtering paradigm developed over several recent papers for IVP solvers. While the method initially seems like a minor extension to these, the paper discusses initialisation, calibration, mesh refinement to achieve pre-set tolerance level, things which are often neglected in these types of works. There are encouraging results (though mutliple approaches for eg. initialisation are presented and its not clear which is recommended in given cases) and the claim is made that the computational cost of the algorithm is competitive with state of the art classical solvers.
main_review: This is a strong paper which attacks an important problem (BVPs) within the relatively new yet increasingly established probabilistic numerics paradigm. The work is rigorous and considers at length practical issues such as initialisation and computational cost (though in the latter case benchmarking is not provided, and neither is code) while also undertaking a detailed discussion of calibration, hyperparameter setting, and differences in prior choice. These issues are often neglected in similar papers. The detailed description of the model in Appendix A is informative and well written and it is a pity it does not fit into the main paper. I particularly appreciated the focus on the use of the method in practice (including what seems from the description like carefully designed code) though obviously the code has not been made available. I also appreciated the clear writing. I did wonder given the claims of 'practical usability' why no benchmarking was attempted.

I do have some questions and clarifications for the authors:
* Can this method easily extend to the situation where the boundary conditions are random (with known distribution, say, but not simply a fixed point). Would this also apply to the revised model in Sec 3.2 ?
* Fig 3. Please provide some more detail on what happens when the number of points is increased. Is the poor EKS linearisation using the guess start made up for with more points, or is it long term catastrophic? Are there any issues with the EKS scheme (beyond the additional cost), say the failure to find alternative solutions where more than one exists etc? Some comment would be good.
* It’s not discussed how to set \nu. What is the intuition with the higher derivatives? I can see in Fig 6 that you have varied this parameter but how does the practioner decide? This seems like the major critical algorithm parameter not discussed.
*Is BQ sufficiently accurate in practice with such a small number of nodes? How is the BQ uncertainty propagated to the main IEKS algorithm? That’s not entirely clear. How can you discriminate the source of error as coming from the ODE or from the BQ within the steps?
* Calibration (right hand plot of Fig 6) is interesting. This seems to be not only quite poor (underconfident as stated in the main text) but also getting worse as the number of grid points increases. Are the strategies within the current algorithm (a different approach to setting certain parameters for example) that would mitigate this? How should a practitioner who presumably wants ‘ a well calibrated method’ interpret this plot?
* Did you compare your method (in wall clock time rather than in computational complexity) to existing solvers including state of the art classical ones? Can you give anything quantitive?
limitations_and_societal_impact: No plausible negative societal impacts from this work so not addressed.
review_title: null

Meta-review: This paper proposes and studies a probabilistic numerical method for the solution of boundary value problems (BVPs) specified by ODEs.  The contribution builds on earlier work that exploited the state-space formulation of Gaussian processes (GPs) to solve initial value problems specified by ODEs.  Considerable attention is paid to practical implementation and I believe the author(s)' claim that the method is useable out of the box (the author(s) promise that code will be released).  The NeurIPS community have historically been interested in the use of GPs to solve ODEs, and I expect that this work (which is the first practical method for BVPs) will again attract significant interest.
Decision: Accept (Poster)