No-U-Turn Hamiltonian Optimization: Acceleration for Quadratics and a Fixed-Horizon Safeguard for Strongly Convex Functions

Restarted Hamiltonian methods must choose when to stop each trajectory. Existing accelerated schemes choose the integration time before observing the trajectory and use curvature information to set its scale. Motivated by the No-U-Turn Sampler (NUTS), we propose \emph{No-U-Turn Optimization} (NUTO). To our knowledge, it is the first direct analogue of NUTS for Hamiltonian optimization. Starting from rest, NUTO stops the exact flow at the first U-turn and restarts from the earliest objective minimizer reached by that time. This adaptive rule selects each integration time from the current trajectory without using curvature bounds. For an $\alpha$-strongly convex and $L$-smooth objective, write $\kappa=L/\alpha$. On positive definite quadratics, exact NUTO reaches a relative objective gap of at most $\varepsilon$ in $O\left(\alpha^{-1/2}\log(\kappa/\varepsilon)\right)$ total integration time. On general objectives in this class, every exact NUTO step with a finite U-turn time contracts the objective gap by a factor at most $(\kappa-1)/(\kappa+1)$. We prove that the U-turn time is finite near the minimizer in any dimension and from every initial point in one and two dimensions. A two-dimensional quadratic rules out a uniform accelerated one-step contraction for exact NUTO. A fixed-horizon safeguard using $\alpha$ but not $L$ contracts the gap by a factor at most $2/3$ at every restart and reaches a relative gap of at most $\varepsilon$ in $O\left(\alpha^{-1/2}\log(1/\varepsilon)\right)$ total integration time in every dimension. Experiments on quadratic and nonquadratic strongly convex objectives verify the identities and bounds used in the analysis.