Summary
In this work, the authors draw inspiration from the randomized midpoint method for Langevin dynamics and design a new method called the poisson midpoint method. They establish guarantees for this method relative to the EM discretisation with thinning, and discuss theoretical and practical applications to sampling.
Strengths
### Originality and Significance
The idea is quite interesting, and binning the unit interval to perform a randomized midpoint discretization is novel in my view. This clearly is not a straightforward innovation despite seeming like one. The theoretical statements also help characterize the benefits of this new strategy, which appear to be shown under weaker conditions than those required for sampling. Practically, this is also very appealing as the computational costs for the applications to generative modelling is lower than now-standard techniques when fixing the requirement (i.e., low FID).
### Quality and Clarity
The idea is well-motivated, but I feel like the paper could be a lot more clearly presented, especially to be accessible to broader audiences. Please see the weaknesses / questions section below.
Weaknesses
The writing of the paper can be definitely improved. It appears a bit rushed in multiple key areas, and several definitions and procedures are stated without much consideration towards the readability of those portions. Since there is a new method being proposed, it would help if intuition for this method is proposed, not just for the idea, but also the design of the method itself. Additionally, when certain complex steps (relative to other methods described in the paper like LMC) are mentioned (see the Algorithm and Computational complexity paragraph on Page 5), it would help to explain each (or a subset of them) in layman's terms to connect them to method (the two equations (7) and (8) on the previous page). The theoretical result in Section 3, specifically theorem 1 has inconsistent terminology ($B$ is the Brownian motion, $\mathsf{S}(...)$ and $\mathsf{PS}$ are lacking a $b$, $B$, $b$, $\beta$, the role of $r$ and the randomness of the expectation is unclear. In the next theorems, the authors state "Lower Order Terms" instead of a small-O notation would have seemed more appropriate. The paragraph on quadratic speedup is also quite hastily presented in my opinion, because it is still not clear to me how the speedup is represented.
Questions
1. What is $p_{\tau}$ in Eq. (4)?
2. As mentioned in Page 2, $A_\alpha$, $G_\alpha$, $\Gamma_\alpha$ are time independent, and so DDPM doesn't fall under the model in (1) right? How is DDPM relevant to the scheme (1) in that case?
3. The scaling relations part of Section 2.1 could perhaps be placed later on? It's difficult to understand its purpose since it seems disconnected from the rest of the main draft.
4. In Line 109, "speed up" is usually a computational term. Is this alluding to the "speed up" discussed later in Section 3 (in which case it might help to reference it here)?
5. Since RLMC is also relatively complex (in comparison to a standard forward EM discretization), it would help to remark on how this is implemented, even if briefly. As written, it is essentially a combination of two discretizations: one forward, and one backward, and the backward discretization is the harder one to implement.
6. The section of text between Lines 118--123 is very hard to follow. Since it is essential to the intuition, I would recommend that it be reworded suitably to be more formal and less colloquial. What is $\mathrm{law}(Z + \epsilon)$ and $\mathrm{law}(Z + \epsilon Z')$?
7. I feel like the claim of "replacing K steps with one step" is not quite true, since eqs (7), (8) are each performing K steps each right?
8. In eq (7), could the authors perhaps give some intuition about the summation on the RHS, and what the cheap interpolation is actually performing? A diagram would help greatly, but it is understandable if this is difficult to provide.
9. In (8), what is the purpose of H_{t,i}? Why don't the $\Gamma$, $A$, $G$ terms not have a "i" scaling like in the cheap interpolation?
10. Why does $I_t$ have $N$ elements, and what is $N$ here? Initial conditions / conventions for the recursion in step 2 would be better off being stated apriori. What is $\mathrm{Corr}$ in Step 4?
11. Where is the computational complexity discussed in the paragraph on the top of page 5?
12. How is there no dependence on the $\{X_{t}\}$ sequence in Eq. 10?
13. Why is this strange dependence on 14th moment in Assumption 2 present?