BrownianInterval type

[ChrisRackauckas]

https://openreview.net/pdf?id=padYzanQNbg this paper is something we might want to add @frankschae .

[patrick-kidger]

What might help - we have an implementation here, which includes a few fun things we didn't mention in the paper, like Levy area approximation via Davie-Foster approximations.

[frankschae]

Looks cool. Thanks a lot for the link @patrick-kidger ! I had a very quick look. I didn't know the Davie-Foster approximation but it looks very similar to the KPW scheme from:

Kloeden, P. E., Platen, E., & Wright, I. W. (1992). The approximation of multiple stochastic integrals. Stochastic analysis and applications, 10(4), 431-441

based on the Fourier expansion of a Brownian Bridge.. is it the same?

[patrick-kidger]

There are definite similarities between the two approaches. Technical point: there are two slightly different methods, Davie and Davie-Foster. What I say basically applies to both.

KPW approximates Brownian motion (technically the bridge) wrt a Fourier basis. Davie(-Foster) approximates Brownian motion wrt a polynomial basis.

KPW takes lots of terms in the sum to get order-1 strong convergence in e.g. a Milstein solver. Davie(-Foster) takes only a couple terms to get near-order-1 Wasserstein convergence. (Which sits between weak convergence and strong convergence.)

As I'm guessing you're aware, getting higher-order strong convergence is a bit of a nightmare, but it's also not obviously useful for lots (most?) applications. Meanwhile weak convergence is ubiquitously of interest in lots of the SDE literature, and Wasserstein convergence is ubiquitously of interest in lots of the GAN literature. So the practical upshot is that Davie(-Foster) is much cheaper than KPW, whilst usually still giving good convergence in a way that you care about. (Or not. I don't know what your applications are.)

References are as at the very end of Appendix B.2 of this paper. Main points:

• The actual approximation is originally remarked upon without any fanfare between equations (5) and (6) of Davie 2014.
• The key result is Lemma 5.1 of Flint and Lyons 2015. This is the decomposition of Levy area which these approximations are based off.
• Davie's approximation is to replace each K_{kl} with a normal random variable that has the correct variance. (= h^2/12)
• The Davie-Foster approximation is to replace each K_{kl} with a normal random variable that has the correct “conditional variance” (= h^2/20 + h/5(\zeta_k^2 + \zeta_l^2))
• This “moment matching” idea can be taken even further in the d = 2 case.

[mschauer]

"Brownian tree", "Brownian interval"... it is still the same thing as B. Levy and C. Ciesielski's construction of Brownian motions by midpoint displacement, right? https://math.stackexchange.com/questions/936168/reference-for-the-construction-of-brownian-motion

[patrick-kidger]

Mathematically, pretty much yes. (Although the point of the Brownian Interval, over the Brownian Tree, is that it isn't restricted to using just midpoints.) The concern is computational -- memory management, handling approximation tolerances, etc.

[mschauer]

Have you seen https://projecteuclid.org/euclid.bj/1352727808 ?

[patrick-kidger]

It's an interesting paper but I don't think I see the relevance to this discussion.

[mschauer]

Back to the topic. To understand correctly, different trees are compatible with a given partition of the interval

[0           T]       [0           T]
[0      t][t T]       [0 s][s      T]
[0 s][s t][t T]       [0 s][s t][t T] 

If I understand correctly they give different Brownian trajectories, so query order is important?

[patrick-kidger]

That is correct. Whether or not that's an issue depends on whether you actually need your solution to be deterministic wrt just the global entropy, and whether you are using a fixed or adaptive step size solver.

If you are using an adaptive step size solver and need this determinism, then unfortunately the best you can do is fall back to the Brownian Tree over the Brownian Interval. (Somewhat slower.) At least in terms of implementation this is quite easy to do as a special case of the Brownian Interval: in the case of the implementation linked above, this can be accomplished by passing halfway_tree=True, tol=<nonzero>. See also the bottom of DOCUMENTATION.md.

[mschauer]

Ah, thanks a lot, then I understand it.