Technical Summary: Accelerated Convex Optimization via Hamiltonian Dynamics with Deterministic Integration Time

Problem Statement

The paper addresses the problem of first-order convex optimization, specifically minimizing a differentiable convex function $f: \mathbb{R}^d \to \mathbb{R}$ given access to a gradient oracle $\nabla f$. The authors focus on achieving accelerated rates of convergence for both smooth convex and $\alpha$-strongly convex objectives.

While classical gradient descent achieves a convergence rate of $O(1/\epsilon)$ for convex functions and $O(\log(1/\epsilon))$ for strongly convex functions, Nesterov's accelerated gradient method improves these to $O(1/\sqrt{\epsilon})$ and $O(\sqrt{\kappa}\log(1/\epsilon))$ respectively. Recent work has attempted to derive these rates through continuous-time dynamical systems, often utilizing second-order differential equations. However, existing Hamiltonian dynamics-based approaches for optimization have been limited:

1. They often require the objective function to be quadratic.
2. When applied to general convex functions, previous guarantees (e.g., Fu and Wibisono, 2025) were stochastic, holding only in expectation over randomized integration times.
3. They typically rely on the endpoint of the trajectory, which does not yield acceleration for general convex functions without specific structural assumptions.

The goal is to develop a deterministic, Hamiltonian dynamics-based algorithm that achieves optimal first-order complexity for general smooth convex and strongly convex functions without relying on randomization or quadratic assumptions.

Methodology

The proposed approach leverages Hamiltonian Flow (HF) but introduces a novel perspective on how to utilize the trajectory for optimization.

1. Hamiltonian Dynamics Framework

The authors define a Hamiltonian system on the phase space $\mathbb{R}^{2d}$ (position $X_t$ and velocity $Y_t$) with the energy function:
$$H(x, y) = f(x) + \frac{1}{2}\|y\|^2$$
The dynamics are governed by:
$$\dot{X}_t = Y_t, \quad \dot{Y}_t = -\nabla f(X_t)$$
A key property of this system is energy conservation: $f(X_t) + \frac{1}{2}\|Y_t\|^2 = f(X_0) + \frac{1}{2}\|Y_0\|^2$. If initialized with $Y_0=0$, the function value $f(X_t)$ never exceeds $f(X_0)$.

2. Key Insight: Averaging vs. Endpoints

The central theoretical contribution is the observation that for convex $f$, the time-averaged position along the Hamiltonian trajectory provides a stronger descent guarantee than the trajectory's endpoint.

• Lemma 2 establishes a differential inequality showing that the average of the trajectory contracts the optimality gap.
• Corollary 1 demonstrates that a specific weighted average of the positions, defined as $X_{\text{avg}}(X_0; T) = \frac{2}{T^2} \int_0^T (T-t)X_t dt$, satisfies a contraction property:
  $$f(X_{\text{avg}}) - f(z) + \frac{1}{3T^2}\|X_T - z\|^2 \leq \frac{2}{3}(f(X_0) - f(z)) + \frac{1}{3T^2}\|X_0 - z\|^2$$
  This implies a universal contraction factor of $2/3$ for the optimality gap, provided the integration time $T$ is chosen appropriately.

3. Algorithm Design

The paper proposes two algorithms based on this insight:

• HFA (Hamiltonian Flow for optimization with Averaging): An idealized continuous-time algorithm. It iteratively lifts the current iterate to phase space, simulates the exact Hamiltonian flow for a time $T_k$, computes the weighted average of the trajectory, and optionally mixes this average with the endpoint to form the next iterate.

  • For strongly convex functions, the algorithm uses only the weighted average ($\lambda=0$).
  • For convex functions, it uses a mixture of the average and the endpoint ($\lambda=1$) to handle the lack of quadratic growth.

• dHFA-eg (Discretized HFA with Extragradient): A practical discrete-time implementation. Since exact simulation of HF is generally impossible, the authors discretize the flow using the extragradient integrator (a first-order method approximating the implicit integrator).

  • The continuous integral is replaced by a discrete weighted sum.
  • The algorithm maintains the same structure: simulate $N_k$ steps, compute the discrete weighted average, and mix with the final iterate.

Key Contributions

1. Deterministic Acceleration via Averaging: The paper proves that Hamiltonian dynamics-based methods can achieve accelerated convergence rates deterministically for general smooth convex and strongly convex functions. This contrasts with prior work (Fu and Wibisono, 2025) which required randomized integration times to achieve similar rates in expectation.
2. Novel Contraction Lemma: The authors derive Lemma 2 and Corollary 1, which formalize that the time-average of Hamiltonian trajectories contracts the optimality gap with a factor of $2/3$ (plus a residual term). This property was not previously established for general convex objectives.
3. Optimal Complexity: The proposed discrete algorithm, dHFA-eg, achieves the same iteration complexity as Nesterov's accelerated gradient method:
   • Strongly Convex: $O(\sqrt{\kappa} \log(1/\epsilon))$ gradient evaluations.
   • Convex: $O(\sqrt{L/\epsilon})$ gradient evaluations.
     Here, $\kappa = L/\alpha$ is the condition number.
4. Practical Discretization: The work bridges the gap between continuous-time dynamical systems and implementable first-order algorithms by utilizing the extragradient integrator, which only requires gradient access (no proximal oracle).

Results

The paper provides rigorous theoretical guarantees for the proposed algorithms:

• Strongly Convex Case: For functions satisfying $\alpha$-quadratic growth (implied by $\alpha$-strong convexity), running HFA (or dHFA-eg) with a constant integration time (or discretization steps) $T \propto 1/\sqrt{\alpha}$ yields a geometric convergence rate. Theorem 1 and Theorem 3 show the error decays as $(2/3 + \delta)^K$, leading to the optimal $O(\sqrt{\kappa} \log(1/\epsilon))$ complexity.
• Convex Case: For general convex functions, the algorithm requires increasing integration times $T_k$ (or discretization steps $N_k$) geometrically. Theorem 2 and Theorem 4 show that despite the increasing cost per iteration, the total complexity to reach $\epsilon$-accuracy is $O(1/\sqrt{\epsilon})$.
• Deterministic Guarantees: All convergence bounds hold for every execution of the algorithm, not just in expectation.

Significance and Claims

The authors claim that this work establishes Hamiltonian dynamics as a useful algorithmic primitive for deterministic accelerated convex optimization.

• Paradigm Shift: The work shifts the perspective from "sampling as optimization" (using optimization ideas to improve sampling) to "optimization via sampling ideas" (using Hamiltonian flow concepts to improve optimization).
• Robustness: Unlike previous Hamiltonian-based optimization methods that were limited to quadratic objectives or required randomization, this approach works for general smooth convex functions with deterministic guarantees.
• Theoretical Foundation: The paper provides a new differential inequality (Lemma 2) that explains why averaging the trajectory works, offering a deeper understanding of the relationship between continuous-time dynamics and discrete accelerated methods.

The authors note that while the analysis focuses on convex functions, the techniques may have implications for non-convex optimization and accelerated sampling (HMC), though these are left as future directions. The paper does not claim to outperform Nesterov's method in terms of asymptotic complexity but rather to provide an alternative, dynamics-based derivation that achieves the same optimal rates deterministically.