# NUTS misses U-turns, runs in circles until max\_treedepth

**URL:** <https://discourse.mc-stan.org/t/nuts-misses-u-turns-runs-in-circles-until-max-treedepth/9727>\
**Category:** Algorithms\
**Created:** [July 15, 2019, 4:23pm UTC](https://discourse.mc-stan.org/t/nuts-misses-u-turns-runs-in-circles-until-max-treedepth/9727 "2019-07-15T16:23:26Z")\
**Posts on this page:** 1\
**Showing post:** 48

<div class="post-metadata">

**Author:** ![nhuurre](https://avatars.discourse-cdn.com/v4/letter/n/ad7895/32.png) [@nhuurre](https://discourse.mc-stan.org/u/nhuurre)\
**Post date:** [August 16, 2019, 5:53pm UTC](https://discourse.mc-stan.org/t/nuts-misses-u-turns-runs-in-circles-until-max-treedepth/9727/48 "2019-08-16T17:53:47Z")

</div>

> [@fehiepsi](#):
>
> But assume that there are only two points, then to me, computing p1.p2 to decide U-turn is better than computing p1.(p1+p2)/2 and p2.(p1+p2)/2.

The dot product becomes negative as soon as the angle between the vectors exceeds 90 degrees which is not a u-turn. To detect when the turn is near 180 degrees you need to compare the momenta not to each other but to some kind of a “pivot vector” that lies between them. I don’t think p1.(p1+p2)/2 is too strict. When sampling from a two dimensional IID normal Stan does limit about 15% of the transitions to a single leapfrog step so the current algorithm has no problem stopping at short u-turns. Limiting max\_treedepth to 1 or even 2 seriously lowers effective sample size so I think even 15% is quite a lot.

> [@betanalpha](#):
>
> The difference between the two is actually proportional to the _square_ of the step size, which you can see if you restore the step sizes in your calculation.

If I restore the step sizes I get

\begin{eqnarray\*} q\_{n}-q\_{1} & = & \frac{1}{2}\epsilon p\_{1}+\sum\_{k=2}^{n-1}\epsilon p\_{k}+\frac{1}{2}\epsilon p\_{n}+\epsilon^2\frac{f\_{1}-f\_{n}}{4}\\ & = & \sum\_{k=1}^n\epsilon p\_{k}-\epsilon\left(\frac{1}{2}p\_{1}+\frac{1}{2}p\_{n}\right)+\epsilon^2\frac{f\_{1}-f\_{n}}{4}\\ & = & \epsilon\sum\_{k=1}^n p\_{k}+O\left(\epsilon\right) \end{eqnarray\*}

So no, the `rho` used by the u-turn criterion is a first order approximation to q\_n-q\_1 (or vice versa). It is the symmetrically shortened sum that is a second order approximation.

I can’t help but digress here. The above calculation suggests a nice visualization for the leapfrog trajectories. Positions q\_k are represented by black dots in the obvious way. The force at position q\_k is drawn as a vector that starts from q\_k and has length \frac{1}{2}\epsilon^2 f\_k . The momentum is then drawn as a vector \epsilon p\_k placed such that its center coincides with the center of the corresponding force vector. It then happens that the momenta line up end-to-end and create a contiguous “spine” for the trajectory.

Circles are boring so I’ll use inverse square potential for the picture. (this potential is of course pathological due to the infinite peak in the middle and the improper flat tail but let’s not worry about those regions.)  
Here is a trajectory for a two dimensional \frac{-1}{2\left|q\right|^2} potential starting at q=(1.5, 0) and p=(0, 0.66).

 ![leapfrog](https://canada1.discourse-cdn.com/flex030/uploads/mc_stan/original/2X/7/756ffd5e0b42e1a3f32bf76b02c1b449126a9f3a.png)

Symplectic geometry is more than just the position space. To see what the trajectory looks like in the momentum space move all the momenta to the origin while keeping the force vectors attached to their respective momenta. Now the forces create a contiguous path!

 ![momentum](https://canada1.discourse-cdn.com/flex030/uploads/mc_stan/original/2X/d/d7877cde3c837f49023eac76bf7756081e5a20c9.gif)

With all the relevant quantities in the same picture it’s possible to visualize different u-turn conditions. The original u-turn condition stops the sampler when the line connecting the first and last position makes an acute angle with at least one endpoint momentum.

![uturn1](https://canada1.discourse-cdn.com/flex030/uploads/mc_stan/original/2X/2/2f593653dfeaa9a107dd35c812e8a7c921901680.png)

The condition in Stan 2.20 uses a line connecting the ends of the momentum spine.

![uturn2](https://canada1.discourse-cdn.com/flex030/uploads/mc_stan/original/2X/9/984fb17c70028397577d46726b69c64f249f0049.png)

@fehiepsi proposed something like

![uturn3](https://canada1.discourse-cdn.com/flex030/uploads/mc_stan/original/2X/e/ee821b3663b69ae5e9db5e09cede2c49a8aab9a6.png)

> [@betanalpha](#):
>
> The advantage of the current PR, and the current behavior in develop, is that it is more immediately connected to the proper theory and hence easier to demonstrate the desired invariant distribution.

Indeed. I’m not even sure anymore if you can say it is more “complicated.” It has couple of variables more but their purpose is absolutely clear. Any proposed alternative needs a solid theoretical justification first.

---

_[View the full topic](https://discourse.mc-stan.org/t/nuts-misses-u-turns-runs-in-circles-until-max-treedepth/9727)._