Add log-ODE scheme and simplify typing.

lxuechen commented 4 years ago

Main things here:

Add log-ODE scheme obtained with Lie-Trotter splitting and midpoint as described in your draft
Unify all the diagnostics files
Minor tweaks for problems and utility functions in diagnostics
Put all type info in types.py so that we don't have to import two modules elsewhere

Here's the strong order plot rate

Off the top of my head, I'm not entirely sure what strong order to expect. We could also do some W_2 error analysis, and I've done this in the past with pot for my sampling paper, but it's rather slow to run, given that these are cubic time algorithm IIRC. On another note, Sinkhorn would produce extra error.

Thinking out loud, possible sources of error just for this set of diagnostics are

true solution approximation by midpoint
not enough samples to approximate the mse

patrick-kidger commented 4 years ago

The 0.75 order is a bit mysterious looking. Adding another SDE to solve is likely to help diagnose if there's actually an issue - I recall that we got funny-looking convergence rates for one of the previous Strat solvers just because of the choice of SDE.

lxuechen commented 4 years ago

When trying to check the diagnostics, I found I couldn't run them (or at least the Ito/Strat diagonal one) due to a RecursionError in BInterval, which didn't occur before this change.

Is the error a stackoverflow? I'm using Euler with very small step size for simulating the ground-truth now.

I've spotted that our types.py module shares a name with one from the stdlib.

I don't see this as a problem in this particular setting. Importing from this file would probably follow two styles:

import torchsde.types
from torchsde.types import Tuple... The latter style is what we do in all files at the moment. I named this file as types.py originally following PyTorch.

lxuechen commented 4 years ago

The 0.75 order is a bit mysterious looking. Adding another SDE to solve is likely to help diagnose if there's actually an issue - I recall that we got funny-looking convergence rates for one of the previous Strat solvers just because of the choice of SDE.

I agree. I'll also check the rate for a simple SDE where I can check the Lipschitz constants of the coefficients and their derivatives.

patrick-kidger commented 4 years ago

So - I think I agree that log-ODE w/ Levy area approximation could get sub-1.0 convergence. (I'd note that what's there still needs tweaking to be 0.5 for general noise and 1.0 otherwise, where it just reduces to midpoint anyway.)

Regarding the rates - I looked at the SDE that this is tested on and I think I see a y^2 (cross-)term. The product operation x, y -> xy isn't Lipschitz as a map R^2 -> R. I think if we have a non-Lipschitz vector field then all bets are off, and we should probably use something else for the rate diagnostics anyway?

lxuechen commented 4 years ago

(I'd note that what's there still needs tweaking to be 0.5 for general noise and 1.0 otherwise, where it just reduces to midpoint anyway.)

I just noticed that the weak order is 2.0 with foster. Do you know the weak order with davie?

The product operation x, y -> xy isn't Lipschitz as a map R^2 -> R. I think if we have a non-Lipschitz vector field then all bets are off, and we should probably use something else for the rate diagnostics anyway?

Good point. Without taming, I agree this is a problem theoretically. I will have this fixed and also test the weak order.

patrick-kidger commented 4 years ago

Hmm. I've not thought about weak order at all tbh. Where are you getting that it has weak order 2.0 from?

lxuechen commented 4 years ago

Where are you getting that it has weak order 2.0 from?

This is handwavy. But the intuition I have is that given how similar the formulae are compared to Talay, and that Foster's also matches the first two moments of Levy area, it seems unlikely that it should have a lower order. The draft you sent me a while ago has some mildly relevant comments in the Talay connections section.

patrick-kidger commented 4 years ago

log-ODE is basically Milstein, but with just the antisymmetric part of the second order signature (=Levy area) as the correction, rather than the full second order signature. So my expectation is order 1.0 a la Milstein. I'd also note that Talay is an Ito scheme, whilst log-ODE is Strat. IIRC most high-order weak schemes are using something clever about the martingale properties of Ito to do well. (Although I've never really looked into that.)

lxuechen commented 4 years ago

This sounds reasonable to me. I'll change back the weak order to 1.0 for now.

lxuechen commented 4 years ago

@mtsokol Letting you know there are quite some changes here related to the diagnostics folder.

google-research / torchsde

Add log-ODE scheme and simplify typing. #43