2
$\begingroup$

I have read both the original NUTS paper and also the dual averaging paper by Nesterov but due to my lack of background knowledge in optimisation, I don't really understand how dual averaging works.

In particular, I don't understand why the update scheme below will cause the step size to converge to a value such that we get the acceptance probability we want.

Any help/intuition will be appreciated. Thank you.

Step-size Update Scheme

$\endgroup$
1
$\begingroup$

I stumbled on this while looking for an answer to my own misunderstanding of the step size algorithm, so your mileage my vary on this answer...

With that said, the idea is that the slice sampler is there because we can't solve the dynamical system exactly, but with a discrete system. Because it's going to have an error, we use the slice sampler to compensate for bias that might exist if we just accepted the numerical Hamiltonian dynamics as if they were exact.

We have an acceptance probability for this, which would be one iff we could exactly run the dynamics. Essentially, this acceptance probability is related to how good the numerical approximation to the Hamiltonian dynamics is. Then, we balance the tradeoff between $\epsilon$ and the time it takes to generate any given sample by varying $\delta$: either spend more time generating better approximations of the Hamiltonian-dynamics, or alternately spend less time generating crappier ones knowing that we will throw more away.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.