Hamiltonian Descent Algorithms for Optimization: Accelerated Rates via Randomized Integration Time
Authors: Qiang Fu
Andre Wibisono
Venue: NeurIPS 2025 spotlight ()
Keywords: Optimization
Hamiltonian Flow
Acceleration
Randomization
Primary area: optimization

Abstract: We study the Hamiltonian flow for optimization (HF-opt), which simulates the Hamiltonian dynamics for some integration time and resets the velocity to $0$ to decrease the objective function; this is the optimization analogue of the Hamiltonian Monte Carlo algorithm for sampling. For short integration time, HF-opt has the same convergence rates as gradient descent for minimizing strongly and weakly convex functions. We show that by randomizing the integration time in HF-opt, the resulting randomized Hamiltonian flow (RHF) achieves accelerated convergence rates in continuous time, similar to the rates for accelerated gradient flow. We study a discrete-time implementation of RHF as the randomized Hamiltonian gradient descent (RHGD) algorithm. We prove that RHGD achieves the same accelerated convergence rates as Nesterov's accelerated gradient descent (AGD) for minimizing smooth strongly and weakly convex functions. We provide numerical experiments to demonstrate that RHGD is competitive with classical accelerated methods such as AGD across all settings and outperforms them in certain regimes.

Hamiltonian Descent Algorithms for Optimization: Accelerated Rates via Randomized Integration Time
Qiang Fu Department of Computer Science Yale University qiang. fu@yale.e... edu
Andre Wibisono
Department of Computer Science
Yale University andre wi wibisono@yale. edu
Abstract
We study the Hamiltonian flow for optimization (HF-opt), which simulates the Hamiltonian dynamics for some integration time and resets the velocity decrease the objective function; this is the optimization analogue of the Hamiltonian Monte Carlo algorithm for sampling. For short integration time, HF-opt has the same convergence rates as gradient descent for minimizing strongly and weakly convex functions. We show that by randomizing the integration time in HF-opt, the resulting randomized Hamiltonian flow (RHF) achieves accelerated convergence rates continuous time, similar the rates for accelerated gradient flow. We study a discrete-time implementation of RHF as the randomized Hamiltonian gradient descent (RHGD) algorithm. We prove that RHGD achieves the same accelerated convergence rates as Nesterov's accelerated gradient descent (AGD) for minimizing smooth strongly and weakly convex functions. We provide numerical experiments to demonstrate that RHGD is competitive with classical accelerated methods such as AGD across all settings and outperforms them certain regimes.
1 Introduction
Optimization plays a central role in machine learning, with algorithms such as gradient descent (GD) and accelerated gradient descent (AGD) [Nesterov] 1983 serving essential tools for optimizing objective functions. growing body of work has explored optimization algorithms in the framework of continuous-timg dynamical systems, which provides insights into algorithmic behaviors and con- vergence properties. this paper, we develop a novel family accelerated optimization algorithms that are designed based the Hamiltonian flow.
Hamiltonian flow (HF) originates from classical mechanics, describing the continuous-time evolution of physical systems. At fundamental level, Hamiltonian flow governs how the positions and momenta of moving bodies evolve while conserving energy. Beyond its roots in physics, Hamiltonian flows have inspired computational algorithms such Hamiltonian Monte Carlo (HMC) [Duane ct al. 1987], a classical method widely employed for sampling from complex, high-dimensional
probability distributions (Neal et al.] 2011 Betancourt 2017 Hoffman al. 2014]. Due to its
effectiveness, HMC has found extensive applications in Bayesian inference, statistical physics, and
machine learning [Gelman et al. 1995 Kruschke 2014 Lelievre and Stoltz 2016).
There has been growing interest in exploring the connections between optimization and sampling, as they share deep theoretical foundations and many algorithmic similarities. Notably, the Langevin dynamies for sampling can be viewed as the gradient flow for minimizing the relative entropy or Kullback-Leibh (KL) divergence in the space of probability distributions [Jordan et al. 1998] Many works build on this perspective to use techniques from optimization to analyze Langevin-basse
algorithms [Wibisono] 2018 Bernton 2018 Durmus et al. 2019 Ma et al. 2021] develop novel
sampling algorithms inspired by optimization Salim et al.
2020 Lee et al. 2021 Lambert et al.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Diao et al. 2023| Das and Nagaraj 2023 Suzuki et al. 2023 Fu and Wilson 2024 Chen et al. 2025 In this paper, we strengthen the links between optimization and sampling in the opposite direction, by studying how to translate the Hamiltonian Monte Carlo (HMC), a classical sampling algorithm, to design new optimization algorithms, particularly for accelerated methods.
2022
Chen et al.
2022
In the links between optimization and sampling, there is significant theoretical gap regarding acceleration. In optimization, it is well known that greedy methods such as GD can be outperformed by accelerated methods such as AGD [Nesterov] [983] which have faster and optimal convergence rates with square-root dependence on the condition number for minimizing smooth and strongly convex functions under the standard first-order oracle model; see Appendix C.I for review. A similar acceleration phenomenon in sampling is still elusive, but there are some promising candidates. The underdamped (or kinetic) Langevin dynamics has an accelerated convergence rate in continuous time [Cao et al.. 2023], but in discrete time, algorithms based on its discretization still do not have the desired accelerated rates [Ma et al.) [021 Zhang et al.] 2023 Another candidate is the randomized Hamiltonian Monte Carlo (RHMC) [Bou-Rabee and Sanz-Serna 2017]. which is obtained by randomizing the integration time in HMC, and has been conjectured to have an accelerated convergence rate for sampling Jiang 2023]. In continuous time, the idealized RHMC indeed has an accelerated convergence rate in x divergeee for log-concave target distributions (Lu and Wang 2022]. On the algorithmic side, recent works have shown that for a Gaussian target distribution, HMC with carefully chosen integration time, either determined by the roots of Chebyshev polynomials or randomly drawn from exponential distributions, indeed achieves an accelerated mixing time with square-root dependence on the condition number [Wang and Wibisono 2023a Diang 2023 Apers let al. 2024). However, the proof that RHMC achieves acceleration in discrete time for a general target distribution remains missing. In this work, we study the optimization analogue of this question, by designing a new accelerated optimization algorithm based on the randomized Hamiltonian flow.
While Hamiltonian flows have found great success in sampling, their direct use in designing opti- mization algorithms is still relatively limited. Most existing Hamiltonian- optimization methods can be seen as the discretization of the accelerated gradient flow (AGF) [Su et al. 2016 Wibisono ctt al. 2016), which is the combination of HF with a damping term for dissipating energy: this is different from the HF we study in this work which does not have damping. We provide additional discussion of related work in Appendix A Pure HF without damping terms have rarely been studied for optimization. In fact, it obeys the law of energy conservation rather than dissipation, which is opposite to optimization tasks. Notable prior works include Teel et al. (2019). Diakonikolas and Jordan| 2021]. J. De Luca al. (2023] Wang 2024 Particularly, Wang (2024) show that Hamiltonian flows with velocity refreshment and Chebyshev-basd
integration times can achieve accelerated convergence for strongly convex quadratic functions, which is comparable to AGF with refreshment. Beyond quadratic functions, we demonstrate that HF with short-time integration and periodic ve- locity refreshment achieves the same -cneelcleed convergence rates as GD up to constants (see Theorem M).
This naturally prompts a question:
Can we develop accelerated optimization methods based on the Hamiltonian flow?
In this work, we answer this question affirmatively and demonstrate that HF with randomized integration time and its discretization yield accelerated convergence rates for minimizing strongly and weakly convex functions. Our principal contributions are:
We propose the randomized Hamiltonian flow (RHF) for optimization an analogue of RHMC. We establish its accelerated convergence rates of O (exxp- aa/5t)) a/5t))
for a-strongly convex functions and O(1 ) for weakly convex functions. These rates match the optimal accelerated convergence rates of AGF (Su et al. 2016 Wibisono et al. 2016) up to constants.
We study the randomized Hamiltonian gradient descent (RHGD) which is a discretization of RHF. Under L-smoothness assumption, RHGD achieves the overall iteration complexity of Ö(v L/o)
for a-strongly convex functions and O L/E) for weakly convex functions to generate an E- accurate solution in expectation, matching the optimal accelerated rates of AGD [Neterov 1983 2018 and its randomized variant [Even et al. 2021].
Organization The remainder of this work is organized as follows. Section 2 presents notations, definitions and a review of the Hamiltonian flow (HF) for designing optimization algorithms. Section 3 proposes the definition of the randomized Hamiltonian flow (RHF) and its accelcrated convergence
2

---

rates. Section 4 describes how to discretize continuous-ting RHF into an implementable optimization algorithm RHGD and establishes its accelerated convergence rates. Section | presents numerical experiments validating the effectiveness of our proposed methods. Section concludes the paper and discusses its limitations.
2 Preliminaries and reviews
2.1 Notations and definitions
Let |I-11 := 11-112 denote the Euclidean norm on the d-dimensional Euclidean space R2. A differentiable function IR R is a-strongly convex if f(y) 2 [(x) (V/()), x) g x112 for
0. We say is o-gradient-dominated [x)]( 2 2a(f(z) - f(=")) for any E R where x" = arg min f(z) is a minimizer of f. We say f is L-smooth if f(y) & f(z) + (Vf(z). x) + $ f1y x12 or equivalently [V](() fl(i)l s L| yll for any I2Y E Rd. We assume < 1 S L. We say å is an E-accurate solution in expectation Eff(2) - f(x*) I E. Let K == L/a denote the condition number. We use 9. == az to denote the time derivative of dimeddependett quantity gt. We define the flow map HF,, IR" x IRd Rd x Rd as HF, Xo Yn) = (X,, Yy), which is the solution to Hamiltonian flow (HF) time 7/ starting from (Xo, Yo). Given time-dependent random variable 2. we use of to denote its probability distribution. We identify probability distributions with their density functions. Let Exp(7) denote the exponential distribution with mean 1/7 for 0. Let
any 2;, E F. where f (weakly) convex
[n] = {1, ..., n). We use (b)) denote a S Cb for constant C' and use a Ö to denote (b)) up to logarithmic factors. We use a = (bb) to denote = Ch for constants C' > 0.
Problem setting. Our goal is solve the following optimization problem:
min f() #ER
(1)
where f R. + R is differentiable function, and x²' = arg min f(x) is minimizer of
2.2 Hamiltonian flow for optimization
The Hamiltonian flow
HF)
system of ordinary differential equations for (X,, Yi) E Rd x Rd:
x.=Y, Y, - =V=()(XX,)
(HF)
Define the energy (or Hamiltonian) function (xx y) := f(x) + 1 11/l122 A fundamental property of the Hamiltonian flow (HF) is that it conserves energy; Appendix B. for the proof.
Lemma (Energy Conservation). Along (HF) H(X,, Y)) = ((o. Yo) for all 1 2 0.
We exploit the conservation property of the Hamiltonian flow to design optimization algorithm by periodically refreshing the velocity to O. This idea results in the following Hamiltonian flow for optimization (HF-opt) algorithm, which also proposed and studied by Teel et al. [2019] Wang 2024). Below, II, (2, y) = x is the projection operator to the first component.
Algorithm Hamiltonian Flow for Optimization (HF-opt)
1: Initialize Xo E Rdd Choose integration time 7) > for k 2 0.
2: for k == 0, 0...... K do
3: Fk+1 = II, o HF, na (zx, 0)
b (evolve HF for time 77 and project to first component)
4: end for
5: return 2K
Lemma Timplies the following descent lemma of HF-opt; see Appendix B.l for the proof.
Lemma 2. For any k and M 0, HF-opt (Algorithm) 1 satisfies f(*++1) < f(æx).
HF-opt is an instance of new optimization principle, the "Lifl-Connervv-Pnijee (ICP) scheme, which is the same principle that underlies HMC for sampling; Appendix B for more details.
3

---

HF-opt is an idealized algorithm since it assumes we can solve the Hamiltonian flow (FF) We study convergence properties this and the next sections, and we study how to imp implement as a concrete discrete-time algorithm in Section 4 When f is smooth, we show that HF-opt with short integration time Ni has the following convergence rates under gradient domination and weak convexity in Theorem [ Note that the first conclusion in Theorem [ also holds under a-Strong convexity since it implies o-gradient domination. We provide the proof in Appendix [D.]
exactly.
Theorem 1, Assume f is T-smooth. Along Algorithm
with Te h S VT: from any xo Rdd
1. If is a-gradient- then [(Tx) - f(x")((=)))))))) - jah))* (f(zo) - f(x)))
2. I weakly convex, then fxx) f(x')((==)))))) 34 x21
hakk
Up to constants, the results in Theorems 1 match the convergence rates of GD under the same assumptions (see Theorem in Appendix C.I.I and Theorem [12 in Appendix C.I.2) and are derived based on the exact simulation of (HF). If we replace HF,, y,. with one-step leapfrog integrator [Sanz Serna 1992] for implementation, then HF-opt recovers exactly the GD algorithm (see Appendix D.2
and thus inherits the same convergence guarantees GD.
In this paper, we aim to achieve accelerated convergence rates analogous to Nesterov's accelerated gradient descent (AGD). Wang (2224) show that HF-opt achieves the accelerated convergence rate for minimizing strongly convex quadratic functions when the integration time 7/s is selected based on the roots of Chebyshev polynomials. Inspired by the randomized Hamiltonian Monte Carlo (RHMC) algorithm for sampling [Bou-Rabee and Sanz-Serna) 2017] where the integration time is independently drawn from exponential distribution, we study its optimization counterpart to explore accelerated convergence rates for a broader class of objectives beyond quadratic functions.
Randomized Hamiltonian flow for optimization
We propose new optimization counterpart of RHMC, called the randomized Hamiltonian flow for optimization (RHF-opt), where the integration time is drawn from an exponential distribution.
Algorithm 2 Randomized Hamiltonian Flow for Optimization (RHF-opt)
Initialize zo Rdd Specify 7t) for all t 2 0.
2: for k = 0.1...., K do
(set To 0) 4: Independently sample ты ~ Exp (Tx)))
3: Set the current time Tj Σ 2i
k-11_
5: Set 0x+1 II, HF (0x, 0)
> (evolve
HF) for time тк and project first component)
6: end for
7:
return 2g
In Algorithm 2 the k-th integration time тı is random variable drawn from exponential distribu- tion with mean (TT,T,,, where Tk the current time. Note that (t) can depend on time, Below, we choose (()) to be constant when f is strongly convex, and 7(t) x I/t when f is weakly convex.
3.1 Reformulation of RHF-opt as a continuous-time process
To rigorously state convergence rates of Algorithm 2 (RHF-opt), we first describe an equivalent formulation of RHF-opt as the following piecewise deterministic continuous-tim process that we refer as the randomized Hamiltonian flow (RHF):
1. Evolve (HF) between velocity refreshment events.
2. At random jump times governed by an inhomogeneous Poisson process with rate 7(t), we refresh the velocity to 0, and continue evolving (HF).
In the continuous-time perspective, denotes the actual time variable. The sequence (Tz) in Algorithm 2 (RHF-opt) represents the random refreshment times generated by cumulative sums

---

of independent exponential random variables with rates 7(Ta). Equivalently. the continuous-time process described above can be modeled as the following stochastic process:
dxx; = Y, dt, dY, -V(() YY,N,
(RHF)
where dN, := Σx21 ÔT, (dt) is the Poisson point process with rate ((), and & is the k-th time an event happens. Let Y,- be the left limit of Y. At each random time Tg. the second line in (RHF) updates Yr, YT -y-, which refreshes the velocity to Yr, 0. See also Even et al. 202
Appendix C] for a review of the Poisson point measure and the left limit update described above.
3.2 Accelerated convergence rates of the randomized Hamiltonian flow
We establish the accelerated convergence rates (RHF) for minimizing strongly and weakly convex functions. Our proof' use the continuity equation along (RHF); see Lemma 13 in Appendix F
3.2.1 For strongly convex functions
We show the following convergence rate of (RHF) under strong convexity; see Appendix F.1 for the proof. In the result below, the expectation is over the randomness in (X₂, Yi) R which comes from the random integration times in (RHF).
Theorem 2. Assume is a-strongly convex. Let (Xt; Yi) evolve following
with the 160 55 from any Xo p2d with Yo Then for any 2 we have
RHF
choice (() /
E [ -
S exp (-V a
E ((xx) - f(x') + a X x²1]a] 5
10
Compared with HF-opt with short integration time (Theorem 1p. RHF achieves faster convergence for strongly convex functions without smoothness assumption. Recall that the convergence rates for minimizing a-strongly convex functions are (eexp( 2at)) for the gradient flow (GF) and O(exp( - /at)) for the accelerated gradient flow (AGF) [Wibisono et al. 2016) (see Theorems 6 and 7 Appendix [.I.I). In comparison, RHF achieves a faster convergence rate than GF when a is small, and it matches the accelerated rate of AGF up to constants, albeit in expectation.
3.2.2 For weakly convex functions
We show the convergence rate of (RHF) under weak convexity; see Appendix F2 for the proof.
Theorem 3. Assume f is weakly convex. Let (X,, Yi) evolve following (RHF) with the choice
(t) 6 from any Xo E TRdd with Yú = 0. Then for any t. 2 0, we have
5 f(Xo) f(='((x))))))))))) 11xo xz 11)
- -(x)))
(t 1)
Compared with HF-opt with short integration time (Theorem 1p. RHF achieves faster convergence for weakly convex functions without smoothness assumption. Recall the convergence rates for minimixing weakly convex functions are O(1/L) for GF and O(1/(²) for AGF [Su et al., 2016 Wibisono et al., 2016) (see Theorems T0 and [1 in Appendix (C..2). h. In this case as well, RHF improves upon the rate of GF and matches the accelerated rate AGF. albeit in expectation.
The convergence guarantecs in Theorems 2 and 3 are still idcalized because they assume we can discuss practical implementation of RHF.
exactly simulate Hamiltonian flow (HF). In Section
4 Randomized Hamiltonian gradient descent
We study the discretization and implementation of the randomized Hamiltonian flow (RHF) as discrete-time algorithm. We consider two sources of approximation in the discretization process.
5

---

Approximate Poisson process. In RHF, velocity is refreshed at random times governed by Poisson process with rate (t). For small time increment 0, the probability of refreshment event occurring in [,, (++h) is approximately y(!) h, with the probability of multiple events occurring in the same interval being negligible (order o(h)). Thus, given zo E IR and yo = O, RHF can be approximated by alternating between a deterministic integration step of (HF) over time h generate a proposal and probabilistic accept-refresh step for & 2 0:
1. Generate proposal: (#8+1, 9R+1) HF, ( m&)
Øk++1
with probability 1 min(7(kh) with probability min(7(kh) h,
2. Accept-refresh: Mk++1 0
As + 0, the process above recovers RHF.
Approximate Hamiltonian flow. In practice, we need simulate the Hamiltonian flow (HF) using
a numerical integrator, such as the leapfrog integrator (Leimkuhler and Reich| 2004 Sanz-Serna
1992. Bou-Rabee and Sanz-Serna
2018 Accordingly, we replace the exact flow map HF,, with discrete snccrtt--tmeeeoee integrator TA I R" R x R given stepsize h. As first step, we consider T
be the implicit (backward Euler) integrator. The update for (Ix+1 Øk+1) (TK, yk) satisfies the following system of implicit equations:
Ik+1 2₁ hik+1:
(2a)
Ūk y/s = -VV
(2b)
By substituting ū6+1 in (2a) with yk KV (1x++1 from 2b). updates 2 can reformulated as
1k+1 = Prox ( + hyk),
(3a)
Uk+1 yk AV (
(3b)
where Proxaa = arg minyeR= {(()) + z bl - 2 is the proximal operator. we can implement the proximal operator for f. then the updates (3) above yield concrete algorithm that call the randomized proximal Hamiltonian descent (RPHD); see Appendix G. for more details on RPHD and its convergence analysis. However, the proximal step Baa not explicit for general and thus we make one further approximation to turn it into concrete algorithm.
Algorithm.
Let Jx43 = 2z + hyk. We approximate the proximal step (3a by gradient descent:
h2 fZ
F 3
This modification leads a practical algorithm that we call the randomized Hamiltonian gradient descent (RHGD), summarized in Algorithm Note that as h + 0, RHGD recovers RHF.
Algorithm 3 Randomized Hamiltonian Gradient Descent (RHGD)
1: Initialize Zo Rd and Vo
0. Choose stepsize h > 0 and refreshment rate 7ik > 0.
2: for = 0, 0.1...., K do
3: Fx+ 1 T4 hyk
4: Ft+1 = Ja+ 1 - (
5: ūk+11 yk hv (
ØK++1
with probability 1- min (Th h, 1) with probability min (7h h, 1)
6: yk+1 {0
7: end for
8: return ZK
4.1 Accelerated convergence rates of RHGD
RHGD serves as a practical implementation of the randomized Hamiltonian flow (RHF). In the following, analyze the convergence rates of RHGD under both strong and weak convexity.

---

4.1.1 For strongly convex functions
We show the following accelerated convergence rate of RHGD for minimizing smooth and strongly convex functions. The proof is deferred to Appendix G
Theorem 4. Assume f is a-strongly convex and L-smooth, Then for all k 2 0, RHGD (Algorithm with h S AVE' 7Tk Va, and from any 20, E I& satisfies
1+ vah)
- E ((00) - f(x))
72 F x x²1]3]
Corollary 1. Assume f is a-strongly convex and L-smooth. To generate xg satisfying (xf(x f(x")) & E, suffices to run Algorithm with
AVD 7k = va, and from any zo E R for
E [f(x)) - f(x²)) 11=000000 x² [19]
K (24V*+ log
8
Corollary shows that RHGD requires O(y (1e)) iterations to generate an e-accurate solution in expectation under smoothness and strong convexity. Recall under the same assumptions, GD achieves the iteration complexity of O( (1/)),,), whereas AGD achieves the improved iteration complexity of O / log(1/E)) (see Corollaries 3 and 4 in Appendix C.I.I). J. In comparison, RHGD is faster than GD, and matches the accelerated rate of AGD, albeit in expectation.
4.1.2 For weakly convex functions
We show the following convergence rate of RHGD for minimizing smooth and weakly convex functions. The proof is deferred Appendix G.3.3
Theorem Assume f is weakly convex and T-smooth. Then for all ls 2 0, RHGD (Algorithml with h < TVT. T 2(k+93K and from any E Rdd satisfies
17
14 IE | x1
(((()))-(2"))
12(k 882
Corollary 2. Assume f is weakly convex and L-smooth. To generate JK satisfying E[f(xk)
f(x')) S e, suffices to run Algorithm with
17 and any zi E Rdd for
TVE 2[449
K 686L E [110 x²
Corollary shows that RHGD requires O Olv L/e) iterations to generate an e-accurate solution in ex- pectation under L-smoothness and weak convexity. Recall under the same assumptions, GD achieves the iteration complexity of O(L/e), whereas AGD achieves the improved iteration complexity of O(vL/E) (see Corollaries 5 and 6 in Appendix C.1.2). In comparison, RHGD is faster than GD, AGD. albeit in expectation.
and matches the accelerated
4.2 Discussion
Unlike the convergence rates of GD and AGD, which hold deterministically for f( the convergence rate of RHGD holds in expectation, i.e., [xf(z)) - -f f(=') due to the random refreshment. Nevertheless, convergence in expectation can still imply high-probbbblityy bounds for (**) (x= via Markov's inequality. We also remark that the continuized version of AGD (CAGD) proposed by Even et al. [222] and studied by Wang and Wibisono [203b)) where the two variables continuously mix following linear ordinary differential equation and take gradient steps random times, similarly achieves accelerated convergence rate in expectation.
7

---

Proof Sketch. We first establish the convergence of the ideal algorithm RPHD (Algorithm 5 Using Lyapunov function Eg. we show that preserves the accelerated convergence via 1 S Ex (see Theorems 14 and 15). The analysis for the practical algorithm RHGD follows similarly but accounts for the approximation of the proximal step (īa) using gradient descent
We bound the
resulting error, which depends on the gradient norm (see Proposition D. and then incorporate it into
the Lyapunov decrease. Unlike prior works (e.g..[ [Wilson et al. [021 ). our analysis avoids explicitly tracking intermediate iterates, enabling flexibility in the choice of approximation for (3a).
5 Numerical experiments
In this section, we validate the empirical effectiveness of RHGD (Algorithm 3) through numerical
experiments on two canonical convex optimization problems: (1) quadratic minimization and (2) logistic regression. We compare our proposed algorithm RHGD with GD, AGD, and its continuized
version CAGD [Even et al., 2021], whose pseudocodes are listed in Appendix H.3 as Algorithms 6 7
and 8 respectively. We evaluate their performance under various condition numbers with fine-tuned or adaptive stepsizes. For the quadratic problem, we also evaluate the robustness of RHGD to the misspecification of strong convexity constant a. We denote the stepsize of GD, AGD and CAGD by 1) and the stepsize of RHGD by h to reflect their different scales in smoothness constant L. See Appendix H for full details on our experiments. Code is available at htttp: /eta::////ttb// com/ QiangFu09/RRas RHGD
5.1 Minimizing quadratic functions
Consider the quadratic optimization problem: min {f(x)= = 1 - where A Raxd is
=ERS
positive semi-definite matrix with the smallest eigenvalue a S and the largest eigenvalue I, 2 1. In our experiments, we set d = 100, select the stepsize for each algorithm via grid search and choose the largest value that ensures convergence and stability. Larger stepsizes result numerical instability or divergence. Specifically, we optimize 7) over geometric sequence S == {c/ L: : 2n, n E Z} with ratio 2, and optimize h over geometric sequence S == [Ve/L: c 2", n E 2} with ratio 22, See Tables 2 and in Appendix H.1.3 for the optimal stepsizes via grid search of each setting.
We consider both strongly convex (a 0) and weakly convex (a 0) quadratic minimization. For the strongly convex case, we fix L = 500 and test three condition numbers k E {100, 100, 10"} with a L/x. Since AGD, CAGD, and RHGD require to compute momentum parameters and refreshment rates, we first compare all algorithms using the exact value of a. Notably, when the condition number и: is large, the strong convexity constant
be extremely small (e.g., K = 10". a = 5 x 10-5), which makes an accurate estimation of a challenging in practice. To evaluate robustness, we also test with misspecified values á (0.01, 0.1, > a. In this section, we report results for x = 107 and â = 0.01; additional results are deferred to Appendix H...1 For the weakly convex case, we evaluate the same algorithms with appropriately configured parameters (see Appendix H.3) ). In particular, RHGD uses decaying
instead of a constant.
2(k+9)6
L0==10
L/b 10., 6
= 0. L=5x102
6D
ASD
ftx M0..-lee
RHED lours)
MX3
AGI
CAGO
CAGD
RH60 [sur)
RHCD (ours)
Iteration
Reration
Iteration2 2
Figure 1: Comparison between GD, AGD, CAGD, and RHGD (ours) on minimizing quadratic
functions with L 500 in three settings: (1) k 10" with exact a (left); (2) k 10" with misspecified â = 0.01 (middle); (3) a = 0 (right). We use optimal stepsizes via grid search for each setting. Each plot shows results averaged over runs.
8

---

Summary of experimental results. Figure presents results for the strongly convex setting with exact a (left), misspecified & 0.01 (middle), and the weakly convex setting (right). In the left plot, all accelerated methods clearly outperform GD. While slower than AGD and CAGD, which are known to be optimal under exact parameter knowledge, RHGD remains highly competitive during the early iterations. The middle plot highlights the robustness of RHGD to misspecification. The momentum parameters of AGD and CAGD, and the refreshment rate of RHGD are computed using overestimated values á 0.01, which are significantly larger than the true value While AGD and CAGD degrade significantly when using overestimated a, RHGD maintains stable performance and outperforms them in later stages. The right plot shows that RHGD achieves the fastest convergence among all algorithms, consistently improving over AGD and CAGD throughout the iterations, demonstrating its advantage in the weakly convex setting.
x 10
5.2 Minimizing logistic regression loss
We construct synthetic binary classification task using logistic regression with Ez-regularization
n
min #ERd
f(x)
log (1 cxp(-b.a x)) + |
n
where we set d = 100 and = 500. Details on objective generation is provided in Appendix H.2
We consider the strongly convex (a [10-3, 10 50) and weakly convex (a 0) settings. We report results for a E (110-4.00 0} and defer the others to Appendix H.2 Since the smoothness constant L unknown,
evaluate GD, AGD and CAGD using adaptive stepsizes the same way as in Hinder et al. 2020 through line search (see Algorithms 9 T0 and [1 in Appendix H.3). For implementation of RHGD, we also adopt similar adaptive stepsize strategy inspired by the line search in Hinder et al.) (2200) (see Algorithm 12 in Appendix H.3). We initialize the stepsize h = 1. At each iteration, h is
If the condition is satisfied, then we increase the stepsize by setting h < vI.I-A h and accept Tx+1 F2+11 otherwise, we decrease the stepsize by setting h <- v0.6 h and reject Ix+1 by setting T6+1 +- Tk.
updated based checking the condition: (i+++1) < ( h²
[V Il(
= 10
10a
56
10
187
GD
(16)
AGD
10
CAGD
RHGD 2Vol
10
AGD
CAGD
RHGD (W vv)
RHGD (ours)
10
15
107
10
10P
Iteration k
Iteration K
Figure 2: Comparison of GD, AGD, CAGD and RHGD on logistic regression with a E (10-4.0) We run each algorithm using adaptive stepsizes. For RHGD, we evaluate aa and 7 = 2/a for a > and evaluate ?/x 17/(2k + 18)h for a =
Summary of experimental results. Figure 2 presents the convergence behavior of all tested algorithms on logistic regression task with a E [10-1, 0} and adaptive stepsizes. We observe from the left plot that using a slightly larger refreshment rate, 7kk = 2 results in faster and more stable convergence, while Theorem ( setting the refreshment rate to 7 = Va. Our proposed algorithm RHGD with 7/- 2 and 7 Va are faster than GD in the late iterations and comparable to AGD and CAGD. The right plot presents the results in the weakly convex setting with adaptive stepsizes. For RHGD, choose the decaying refreshment rate 7 2(k+9))
17 All
accelerated methods consistently outperform GD, and RHGD exhibits comparable performance to baseline accelerated algorithms AGD and CAGD.

---

Conclusion and limitations
In this work, we propose the randomized Hamiltonian flow (RHF) and its discretization, the random- ized Hamiltonian gradient descent (RHGD), and establish their accelerated convergence guarantees for both strongly and weakly convex functions. Numerical experiments on quadratic minimization and logistic regression tasks demonstrate that RHGD faster than GD, and consistently matches or outperforms baseline accelerated algorithms such as AGD and CAGD.
We outline several promising directions for future research that build upon and extend this work. First, would be valuable to explore other integrators for discretization, such as the leapfrog integrator, which is commonly used in Hamiltonian Monte Carlo (HMC) and may improve numerical stability or efficiency the optimization context.
Second, a natural extension is to study whether our framework and convergence analysis can be generalized to broader classes non-convex functions, such as quasar-conver functions (Hardt et 2018). for which recent works have shown potential for accelerated convergence (Hinder et al. 2020 Fu et al. 2023 Wang and Wibisono 2023b].
Morcover, an important direction is the development of stochastic variant of RHGD, where gradients are estimated using mini-batches or variance reduction. This would make the method more suitable for large-scale optimization tasks where computing full gradients is computationally prohibitive. Finally, we hope that our analysis of randomized Hamiltonian flows for optimization can provide theoretical tools and insights toward validating a long- -tanditnn conjecture in sampling: randomized Hamiltonian Monte Carlo can achieve accelerated mixing time in KL divergence for sampling from strongly log-concave distributions.
Limitations. Similar to CAGD Even et al. 2021 our convergence guarantees for RHF and RHGD hold in expectation due their inherent randomness. While this differs from deterministic algorithms like GD and AGD, we can extend our results to high-probability bounds via concentration inequality. Additionally, while our rates ((exp_VVa/55) for RHF and O( + (a)/6)--)) for RHGD exhibit the same va dependence as optimal accelerated methods (AGF and AGD, see Appendix C.I.IJ. II the constants are somewhat larger. Nevertheless, our algorithm RHGD is still faster than GD and competitive with AGD in both theory and practice.
Acknowledgment
The authors thank the anonymous reviewers for their thoughtful feedback and Jun-Kun Wang and Molei Tao for insightful discussions.
References
Simon Apers, Sander Gribling, and Dániel Szilágyi. Hamiltonian Monte Carlo for efficient Gaussian sampling: long and random steps. Journal of Machine Learning Research, 25(348): 1-30, 2024.
Hedy Attouch, Zaki Chbani, Jalal Fadili, and Hassan Riahi. First-order optimization algorithms via inertial systems with Hessian driven damping. Mathematical Programming, pages 1-43, 2022.
Espen Bernton. Langevin Monte Carlo and JKO splitting. In Sébastien Bubeck, Vianney Perchet, and Philippe Rigollet, editors, Proceedings of the 3 Ist Conference On Learning Theory, volume 75
of Proceedings of Machine Learning Research, pages 1777-1798, PMLR, 06-09 Jul 2018
Alexandros Beskos, Natesh Pillai, Gareth Roberts, Jesus-Maria Sanz-Serna, and Andrew Stuart. Optimal tuning of the hybrid Monte Carlo algorithm. Bernoulli, 19555)155111554, 2013.
Michael Betancourt. A conceptual introduction to Hamiltonian Monte Carlo. arXiv preprint arXiv: 2017.
MJ Betancourt, Simon Byrne, and Mark Girolami. Optimizing the integrator step size for Hamiltonian Monte Carlo. arXiv preprint arXiv:1411.660 2014.
10

---

Nawaf Bou-Rabes and Andreas Eberle. Two-scale coupling for preconditioned Hamiltonian Monte Carlo in infinite dimensions. Stochastics and Partial Differrntial Equations: Analysis and Compu- lations, 9:207-242, 2021.
Nawaf Bou-Rabee and Andreas Eberle. Mixing time guarantees for unadjusted Hamiltonian Monte Carlo. Bernoulli, 29(1):55-104 2023.
Nawaf Bou-Rabee and Milo Marsden. Unadjusted Hamiltonian MCMC with stratified Monte Carlo time integration. The Annals of Applied Probability, 35(1):360-392, 2025.
Nawaf Bou-Rabee and Jesús María Sanz-Serna. Randomized Hamiltonian Monte Carlo. Annals of applied probability: an journal of the Institute of Mathematical Statistics, 27(4):2159 2194, 2017.
Nawaf Rou-Rabee and Jesús Maria Sanz-Serna. Geometric integrators and the Hamiltonian Monte Carlo method. Acia Numerica, 27:1 13-206, 2018.
Nawaf Bou-Rabee and Katharina Schuh. Nonlinear Hamiltonian Monte Carlo & its particle approxi- mation. arXiv preprint arXiv:2308.. 1491, 2023.
Nawaf Rou-Rabee, Andreas Eberle, and Raphael Zimmer. Coupling and convergence for Hamiltonian Monte Carlo. The Annals of Applied Probability, 30(3): 1009-1200, 2020.
James Brofos and Roy R Lederman. Evaluating the implicit midpoint integrator for Riemannian Hamiltonian Monte Carlo. In International Conference on Machine Learning, pages 1072-1081. PMLR, 2021.
Evan Camrud, Alain Durmus, Pierre Monmarché, and Gabriel Stoltz. Second order quantitative bounds for unadjusted generalized Hamiltonian Monte Carlo. arXiv preprint arXiv:2306.09513, 2023.
Yu Cao, Jianfeng Lu, and Lihan Wang. Complexity of randomized algorithms for underdamped Langevin dynamics. Communications in Mathematical Sciences, 19(7):18771155, 2020.
Yu Cao, Jianfeng Lu, and Lihan Wang. On explicit L'=convergence rate estimate for underdamped Langevin dynamies. Archive for Rational Mechanics and Analysis, 247(5):90, 2023.
Bob Carpenter, Andrew Gelman, Matthew D Hoffman, Daniel Lee, Ben Goodrich, Michael Be- tancourt, Marcus Brubaker, Jiqiang Guo, Peter Li, and Allen Riddell. Stan: A probabilistic programming language. Journal of Statistical Software, 76:1-32, 2017.
Shi Chen, Qin Li, Oliver Tse, and Stephen J Wright. Accelerating optimization over the space of probability measures. Journal of Machine Learning Research, 26(31):1 2025.
Tianqi Chen, Emily Fox, and Carlos Guestrin. Stochastic gradient Hamiltonian Monte Carlo. In International Conference on Machine Learning, pages 1683-1691. PMLR, 2014.
Yongxin Chen, Sinho Chewi, Adil Salim, and Andre Wibisono. Improved analysis for a proximal algorithm for sampling. Conference on Learning Theory, pages 2984-3014 PMLR, 2022.
Yuansi Chen and Khashayar Gatmiry. When does Metropolized Hamiltonian Monte Carlo provably outperform Metropolis-adjustte Langevin algorithm? arXiv preprint arXiv:2304.04724 2023.
Yuansi Chen, Raaz Dwivedi, Martin Wainwright, and Bin Yu. Fast mixing of Metropolized Hamiltonian Monte Carlo: Benefits of multi-step gradients. Journal of Machine Learning Research, 27 2020.
Xiang Cheng and Peter Bartlett. Convergence of Langevin MCMC in KL-divergence. In Algorithmic learning theory, pages 186-211. PMLR, 2018.
Xiang Cheng, Niladri S Chatterji, Peter L. Bartlett, and Michael I Jordan. Underdamped Langevin MCMC: non-asymptotic analysis. In Conference on Learning Theory, pages 300-323. PMLR, 2018.
11

---

Sinho Chewi, Murat A Erdogdu, Mufan Li, Ruoqi Shen, and Matthew S Zhang. Analysis of Langevin Monte Carlo from Poincare to log- -og-ooooeev. Foundations of Computational Mathematics, pages 1-51, 2024.
Amnk Dalalyan. Further and stronger analogy between sampling and optimization: Langevin Monte Carlo and gradient descent. In Conference on Learning Theory, pages 678-688 188.69. PMLR, 2017a.
Arnak S Dalalyan. Theoretical guarantees for approximate sampling from smooth and log-concave densities. Journal of the Royal Statistical Society Series B: Statistical Methodology, 79(3):651-676 2017b.
Aniket Das and Dheeraj Nagaraj. Provably fast finite particle variants of SVGD via virtual particle stochastic approximation. In Advances in Neural Information Processing Systems, volume 36, pages 49748 49760, 2023.
Bruno De Luca, Alice Gatti, and Eva Silverstein. Improving energy conserving descent for machine learning: Theory and practice. arXiv preprint arXiv:2306.0033: 00352, 2023.
Jelena Diakonikolas and Michael Jordan. Generalized momentum-based methods: A Hamiltonian perspective. SIAM Journal on Optimization, 31(1):915-944 5444, 2021.
Michael Ziyang Diao, Krishna Balasubramanian, Sinho Chewi, and Adil Salim. Forward- backward Gaussian variational inference via JKO in the Bures-War waaressnssrsttinnne space. In International Conference on Machine Learning, pages 7960-7991. PMLR, 2023.
Vu Dinh, Arman Bilge, Cheng Zhang, and Frederick A Matsen IV. Probabilistic path Hamiltonian Monte Carlo. In International Conference on Machine Learning, pages 1009-1018, PMLR, 2017.
Simon Duane, Anthony D Kennedy, Brian J Pendleton, and Duncan Roweth. Hybrid Monte Carlo. Physics Letters B, 195(2):216-222, 1987.
Alain Durmus and Éric Moulines. Nonasymptotic convergence analysis for the unadjusted langevin algorithm. The Annals of Applied Probability, 27(3): 2017.
Alain Durmus, Eric Moulines, and Eero Saksman. On the convergence of Hamiltonian Monte Carlo. arXiv preprint arXiv:
2017.
Alain Durmus, Szymon Majewski, and Blažej Miasojedow. Analysis of Langevin Monte Carlo via convex optimization. Journal of Machine Learning Research, 20(73):1-46 2019.
Alexandre d' Aspremont, Damien Scieur, Adrien Taylor, al. Acceleration methods. Foundations and Trends@ in Optimization, (112)):12245, 2021.
Mathieu Even, Raphaël Berthier, Francis Bach, Nicolas Flammarion, Pierre Gaillard, Hadrien Hendrikx, Laurent Massoulié, and Adrien Taylor. A continuized view Nesterov acceleration for stochastic gradient descent and randomized gossip. In Proceedings of the 35th International Conference on Neural Information Processing Systems, pages 28054-28066, 2021.
Qiang Fu and Ashia Camage Wilson. Mean-field underdamped Langevin dynamics and its spacetime discretization. In Proceedings of the 41st International Conference on Machine Learning, volume 235 of Proceedings of Machine Learning Research, pages 14175-14206. PMLR, 21-27 Jul 2024.
Qiang Fu, Dongchu Xu, and Ashia C. Wilson. Accelerated stochastic optimization methods under quasar-convexity. In International Conference on Machine Learning, pages 10431-10460. PMLR, 2023.
Andrew Gelman, John B Carlin, Hal S Stern, and Donald B Rubin. Bayesian data analysis. Chapman and Hall/CRC, 1995.
Mert Gürbüübalaaan, Xuefeng Gao, Yuanhan Hu, and Lingjiong Zhu. Decentralized stochastic gradient Langevin dynamics and Hamiltonian Monte Carlo. Journal of Machine Learning Research, 22(239):1 2021.
Moritz. Hardt, Tengyu Ma, and Benjamin Recht. Gradient descent learns linear dynamical systems. Journal of Machine Learning Research, 19429):1-44, 2018
12

---

Oliver Hinder, Aaron Sidford, and Nimit Sohoni. Near-optimal methods for minimizing star-convex functions and beyond. In Conference on Learning Theory, pages 1894-1938. PMLR, 2020.
Marcel Hirt, Michalis Titsias, and Petros Dellaportas. Entropy-based adaptive Hamiltonian Monte Carlo. In Advances in Neural Information Processing Systems, volume 34, pages 28482-28495, 2021.
Matthew Hoffmman, Pavel Sountsov, Joshua Dillon, lan Langmore, Dustin Tran, and Srinivas Vasudevan. Neutralizing bad geometry in Hamiltonian Monte Carlo using neural transport. arXiv preprint arXiv: 037044, 2019.
Matthew D Hoffman and Pavel Sountsov. Tuning-free generalized Hamiltonian Monte Carlo. In International Conference on Artificial Intelligence and Statistics, pages 7799-7813. PMLR, 2022.
Matthew D Hoffman, Andrew Gelman, et al. The No-U-Turn sampler: adaptively setting path lengths in Hamiltonian Monte Carlo. Journal of Machine Learning Research, 15(1):1993-1623, 2014.
Bin Hu and Laurent Lessard. Dissipativity theory for Nesterov's accelerated method. In International Conference on Machine Learning, pages 1549-1557. PMLR, 2017.
Qijia Jiang. On the dissipation of ideal Hamiltonian Monte Carlo sampler. Stat, 12(1))e629, 2023.
Richard Jordan, David Kinderlehrer, and Felix Otto. The variational formulation of the Fokker-Planck equation. SIAM Journal on Mathematical Analysis, 29(1):1-17, 1998.
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In International Conference on Learning and Representations, 2015.
Walid Krichene, Alexandre Bayen, and Peter L. Bartlett. Accelerated mirror descent in continuous and discrete time. In Advances Neural Information Processing Systems, volume 28, 2015.
John Kruschke. Doing Bayesian Data Analysis: A Tutoriil with R, JAGS, and Stan. Academic Press, 2nd edition, 2014.
Marc Lambert, Sinho Chewi, Francis Bach, Silvère Bonnabel, and Philippe Rigollet. Variational inference via Wasserstein gradient flows. In Advances in Neural Information Processing Systems, volume 35, pages 14434 1443-11447, 2022.
Yin Tat Lee and Santosh S Vempala. Convergence rate of Riemannian Hamiltonian Monte Carlo and faster polytope volume computation. Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, pages 1115-1121, 2018.
Yin Tat Lee, Zhao Song, and Santosh Vempala. Algorithmic theory of ODEs and sampling from well-conditioned logconcave densities. arXiv preprint arXiv:1812.06244 2018.
Yin Tat Lee, Ruoqi Shen, and Kevin Tian. Structured logconcave sampling with a restricted Gaussian oracle. In Conference on Learning Theory, pages 3993-3050. PMLR, 2021.
Benedict Leimkuhler and Sebastian Reich. Simulating Hamiltonian Dynamics. Number 14 in Cambridge Monographs Applied and Computational Mathematics. Cambridge University Press, 2004.
Benedict Leimkuhler, Daniel Paulin, and Peter A Whalley. Contraction and convergence rates for discretized kinetic Langevin dynamics. SIAM Journal on Numerical Analysis, 6226)::226-12558 2024.
Tony Lelievre and Gabriel Stoltz. Partial differential equations and stochastic methods in molecular dynamics. Acta Numerica, 15:681-880, 2016.
Jianfeng Lu and Lihan Wang. On explicit I,2- -ccovverreence rate estimate for piecewise deterministic Markov processes MCMC algorithms. The Annals of Applied Probability, 3333):1333-133,, 2022.
13

---

Yi-An Ma, Niladri S Chatterji, Xiang Cheng, Nicolas Flammarion, Peter L Bartlett, and Michael I Jordan. Is there an analog of Nesterov acceleration for gradient-based MCMC? Bernoulli, 27(3): 1942 1992, 2021.
Chris Maddison, Daniel Paulin, Yee Whye Teh, Brendan O' O'Donoghue, and Arnaud Doucet. Hamiltonian descent methods. arXiv preprint 1809 05042, 2018.
Carol Mak, Fabian Zaiser, and Luke Ong. Nonparametric Hamiltonian Monte Carlo. In International Conference Machine Learning, pages 7336-7347. PMLR, 2021.
Oren Mangoubi and Aaron Smith. Rapid mixing of Hamiltonian Monte Carlo strongly log-concave distributions. arXiv preprint arXiv: /tt::/708.000 07/ 14, 2017.
Oren Mangoubi and Aaron Smith. Mixing of Hamiltonian Monte Carlo on strongly log-concave dis- tributions Numerical integrators. The 22nd International Conference on Artificial Intelligence and Statistics, pages 586-595. PMLR, 2019.
Oren Mangoubi and Aaron Smith. Mixing of Hamiltonian Monte Carlo on strongly log-concave distributions: Continuous dynamics. The Annals of Applied Probubility, 315):2011--2045, 2021.
Oren Mangoubi and Nisheeth Vishnoi. Dimensionally tight bounds for second-order Hamiltonian Monte Carlo. In Advances in Neural Information Processing Systems, volume 31, 2018.
Siddharth Mitra and Andre Wibisono. Fast Convergence of 4-Divergence Along the Unadjusted Langevin Algorithm and Proximal Sampler. In International Conference on Algorithmic Learning Theory. PMLR, 2025.
Hadi Mohasel Afshar and Justin Domke.
Reflection, refraction, and Hamiltonian Monte Carlo. In Advances in Neural Information Processing Systems, volume 28, 2015.
Pierre Monmarché. HMC and Langevin united in the unadjusted and convex case. arXiv preprint arXiv:2202.00997. page 2, 2022.
Pierre Monmarché. An entropic approach for Hamiltonian Monte Carlo: The idealized case. The Annals of Applied Probability, 34(2):2243-2299 2024.
Cole C Monnahan, James T Thorson, and Trevor A Branch. Faster estimation of Bayesian models in ecology using Hamiltonian Monte Carlo. Methods in Ecology and Evolution, (3):333-344, 2017.
Michael Muehlehach and Michael Jordan. dynamical systems perspective on Nesterov acceleration. In International Conference on Machine Learning, pages 4656-4662. PMLR, 2019.
Radford M Neal et al. MCMC using Hamiltonian dynamics. Handbbook of Markov Chain Monte Carlo, 2(11):2, 2011. 2011.
Yurii Nesterov. A method for solving the convex programming problem with convergence rate O1)k2). Dokl akad nauk Sssr, volume 269, page 543, 1983.
Yurii Nesterov. Lectures on convex optimization, volume 137. Springer, 2018.
Akihiko Nishimura, David Dunson, and Jianfeng Lu. Discontinuous Hamiltonian Monte Carlo for models with discrete parameters and discontinuous likelihoods. Biometrika, 107-2))355-38,, 2020.
Brendan O' Donoghue and Chris J Maddison.
Hamiltonian descent for composite objectives. In Advances in Neural Information Processing Systems, volume 32, 2019.
Felix Otto. The geometry of dissipative evolution equations: The porous medium equation. Comm.
Partial Differential Equations, 26:101-174, 2001.
Ari Pakman and Liam Paninski. Auxiliary-variable exact Hamiltonian Monte Carlo samplers for binary distributions. In Advances Neural Information Processing Systems, volume 26, 2013.
Boris T Polyak. Some methods of speeding up the convergence iteration methods. USSR
Computational Mathematics and Mathematical Physics, 4(5):1-17, 1964.
14

---

Lionel and Jure Vogrine. Metropolis-adjussee Langevin trajectories: A robust alternative to Hamiltonian Monte Carlo. arXiv preprint arXiv:2202.132250 2022.
Gareth O. Roberts and Richard L. Tweedie. Exponential convergence of langevin distributions and their discrete approximations. Bernoulli, 2(4):341-363, 1996.
Jakob Robnik, G Bruno De Luca, Eva Silverstein, and Uroš Seljak. Microcanonical Hamiltonian Monte Carlo. Journal of Machine Learning Research, 24(311):1-34, 2023.
Adil Salim, Anna Korba, and Giulia Luise. The Wasserstein proximal gradient algorithm. In Advances in Neural Information Processing Systems, volume 33, pages 13366-13366 2020.
John Salvatier, Thomas V Wiecki, and Christopher Fonnesbeck. Probabilistic programming in Python using PyMC3. PeerJ Computer Science, 2:e55, 2016.
Jesus M Sanz-Serna. Symplectic integrators for Hamiltonian problems: An overview. Acta numerica, 1:243 11243-286, 1992.
Christof Seiler, Simon Seeiinstein-Sazzedee and Susan Holmes. Positive curvature and Hamiltonian Monte Carlo. In Advances in Neural Information Processing Systems, volume 27, 2014.
Bin Shi, Simon S Du, Michael I Jordan, and Weijie J Su. Understanding the acceleration phenomenon via high-resolution differential equations. Mathematical Programming, pages 1-70, 2022.
Weijie Su, Stephen Boyd, and Emmanuel J Candes. A differential equation for modeling Nesterov's accelerated gradient method: Theory and insights. Journal of Machine Learning Research, 17 (153):1-43, 2016.
Jaewook J Suh, Gyumin Roh, and Ernest Ryu. Continuous-tine analysis of accelerated gradient methods via conservation laws in dilated coordinate systems. In International Conference on Machine Learning, pages 20640-20661 PMLR, 2022.
Taiji Suzuki, Denny Wu, and Atsushi Nitanda. Convergence mean-field Langevin dynamies: Time-space discretization, stochastic gradient, and variance reduction. In Advances in Neural Information Processing Systems, volume 36, pages 15545-15577, 2023.
Denis Talay. Stochastic Hamiltonian systems: exponential convergence to the invariant measure, and discretization by the implicit Euler scheme. Markov Processes and Related Fields, 8(2):163-19, 2002.
Andrew R Teel, Jorge Poveda, and Justin Le. First-order optimization algorithms with resets and Hamiltonian flows. In 2019 IEEE 58th Conference Decision and Control (CDC), pages 5838-5843. IEEE, 2019.
Nilesh Tripuraneni, Mark Rowland, Zoubin Ghahramani, and Richard Turner. Magnetic Hamiltonian Monte Carlo. In International Conference on Machine Learning, pages 3453-3461. PMLR, 2017.
Santosh Vempala and Andre Wibisono. Rapid convergence of the unadjusted langevin algorithm: Isoperimetry suffices. In Advances in neural information processing systems, volume 32, 2019.
Jun-Kun Wang. Frictionless Hamiltonian descent and coordinate Hamiltonian descent for strongly convex quadratic problems and beyond. arXiv preprint 4rXiv:2402.11946 v3, 2024.
Jun-Kun Wang and Andre Wibisono. Accelerating Hamiltonian Monte Carlo via Chebyshev integra- tion time. In International Conference on Learning and Representation, 2023a.
Jun-Kun Wang and Andre Wibisono. Continuized acceleration for quasar convex functions in non-convex optimization. In International Conference on Learning and Representations, 2023b.
Yifei Wang and Wuchen Li. Accelerated information gradient flow. Journal of Scientific Computing, 90:1-47, 2022.
Andre Wibisono. Sampling optimization in the space of measures: The Langevin dynamics as composite optimization problem. In Conference on Learning Theory, pages 2093-3027. PMIR, 2018.
15

---

Andre Wibisono. Mixing time of the proximal sampler in relative Fisher information via strong data processing inequality. arXiv preprint arXiv:2502.05623, 2025.
Andre Wibisono, Ashia Wilson, and Michael Jordan. A variational perspective on accelerated
methods in optimization. proceedings of the National Academy of Sciences, 113(4))E7351-E7335 2016.
Ashia Wilson. Lyapunov arguments in optimization. PhD thesis, University of California, Berkeley, 2018.
Ashia C Wilson, Lester Mackey, and Andre Wibisono. Accelerating rescaled gradient descent: Fast optimization of smooth functions. In Advances in Neural Information Processing Systems, volume 32, 2019.
Ashia C. Wilson, Ben Recht, and Michael Jordan. Lyapunov analysis of accelerated methods in optimization. Journal of Machine Learning Research, 22 133)1444,, 2021.
Shunshi Zhang. Sinho Chewi, Mufan Li, Krishna Balasubramanian, and Murat A Erdogdu. Improved discretization analysis for underdamped Langevin Monte Carlo. In The Thirty Sixth Annual Conference Learning Theory, pages 36-71. PMLR, 2023.
Yichuan Zhang, Zoubin Ghahramani, Amos J Storkey, and Charles Sutton. Continuous relaxations for discrete Hamiltonian Monte Carlo. In Advances in Neural Information Processing Systems, volume 25, 2012.
Difan Zou and Quanquan Gu. On the convergence of Hamiltonian Monte Carlo with stochastic gradients. In International Conference on Machine Learning, pages 13012-13000 13022. PMLR, 2021.
16

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: See Abstract and Section
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how be expected to generalize other settings.
much the results
is fine to include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: See Section 0
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification. asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low images are taken in low lighting. Or speech-to-text system might be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question:
For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
17

---

Justification:
See Sections 3.2.1 3.2.2
and 4.1.2
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification: See Section 5 and Appendix H
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm.
(b) the contribution is primarily a new model architecture, the paper should describe the architccture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reprodueibility. the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
18

---

Answer: [Yes]
Justification: Anonymized code and related instruction will be provided in Supplementary materials.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.cm ec/
for more details.
While encourage the release of code and data, understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
//nips.cc/pp wwwppbblccgguiicuceccccccoe.oopp wet.ggddddee/eeebbiniinn ssiiisoliccyyyyyy for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: Appendices H.1.3 and H.3
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification:
See Section 5 and Appendices and H.2
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the enror bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
19

---

It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification: See Appendix
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't 't make into the paper).
9. Code of ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics https://neurips: atttss///oorrrps....ppbbb////// htcc/publcc//hhcccciideeeeelllld
Answer: [Yes]
Justification: We have reviewed the NeurlPS Code Ethics and confirm that our research complies with its principles. The work is purely theoretical and experimental in nature, does not involve human subjects, sensitive data, or real-world deployment, and presents foresecable ethical concerns. We have also ensured that anonymity is preserved in accordance with NeurIPS submission guidelines.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
This paper presents theoretical and algorithmic contribution in the area optimization, with no direct application to deployed systems or real-world data. As such, it does not raise immediate societal popacct-positive therefore do not address societal impacts in the paper. However, we acknowledge that foundational optimization methods could have downstream influence depending on their future application.
Justification:
negative-on its own. We
Guidelines:
The answer NA means that there is no societal impact of the work performed.
20

---

If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (c.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (c.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: The paper does not involve the release of datasets, pretrained models, or generative systems that could be misused. Our contribution is entirely theoretical and algorithmic, focusing on the analysis and development of an optimization method without direct ties to high-risk data model deployment.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g.. code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification: The paper does not use any external assets such as third-party code, datasets, or pretrained models. All experiments are implemented from scratch using standard Python libraries, and no existing resources requiring attribution or license compliance are used.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, possible, include URL.
21

---

The name of the license (e.g., CC-BY 4.0) should be included for each asset. For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the palasets.papersstt paperswi thcode. cow con/datases package should be provided. For popular datasets,
has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re- re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is available online, the authors are encouraged reach out to the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification: We release the implementation of our proposed algorithm in the supplementary material as anonymized Python code. The code self-contained, includes instructions for reproducing all experiments presented in the paper, and is organized for clarity. No datasets or pretrained models are included, and no human data is involved.
Guidelines:
The answer NA means that the paper does not release assets.
Researchers should communicate the details the dataset/code/moodl as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: This work does not involve crowdsourcing, human subjects, or any form of user interaction. All experiments are simulation-bard and conducted using synthetic or mathematical data.
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Bthics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals equivalent for research with human subjects
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Question:
Answer: [NA]
22

---

This research does not involve human subjects, user studies, or crowdsourcing. Therefore, Institutional Review Board (IRB) approval or equivalent was not required.
Justification:
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with
human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
Declaration LLM usage
Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, formatting purposes and does not impact the core methodology. scientific rigorousness, or originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification: LLM is not involved in our proposed methods.
Guidelines:
The answer NA means that the method development in this research does not involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy /tttps:/nneurpp... wwwperiisscccoooffeeee /c//Conferenccee22255////////// for what should or should be described.
MLMMLL
23

---

Contents
Introduction
Preliminaries and reviews
Notations and definitions
2.2
Hamiltonian flow for optimization
3
Randomized Hamiltonian flow for optimization
Reformulation of RHF-opt as a continuous-ting process
3.2
Accelerated convergence rates of the randomized Hamiltonian flow
3.2.1
For strongly convex functions
3.2.2
For weakly convex functions
Randomized Hamiltonian gradient descent
4.1
Accelerated convergence rates of RHGD
4.1.1
For strongly convex functions
4.1.2
For weakly convex functions
4.2
Discussion
5
Numerical experiments
5.1
Minimizing quadratic functions
8
5.2
Minimizing logistic regression loss
6
Conclusion and limitations
10
Related work
25
HiffCooneerve-rroeet scheme
27
B.
LCP scheme for optimization: Hamiltonian flow for optimization
27
LCP scheme for sampling: Hamiltonian Monte Carlo
28
B.2.1
Distributional properties of Hamiltonian flow
28
B.2.2
Hamiltonian Monte Carlo an LCP scheme
29
Optimization and sampling: algorithms and connections
30
C.I
Review optimization algorithms with convergence rates
30
C.I.1
Convergence under strong convexity or gradient domination
30
C.1.2 Convergence under weak convexity
31
C.2
Review sampling algorithms
32
Connection and comparison between optimization and sampling
33
Hamiltonian flow with short-time integration
34
D. Proof of Theorem
36
24

---

D.2
Implementation of HF-opt via leapfrog integrator as GD
36
Examples of HF-opt and RHF-opt on quadratic functions
37
Convergence analysis of the randomized Hamiltonian flow
38
Proof of Theorem
(convergence of RHF under strong convexity)
F.2 Proof of Theorem
(convergence of RHF under weak convexity)
40
Discretization analysis
41
Randomized proximal Hamiltonian descent
G.I.I
For strongly convex functions
G.1.2
For weakly convex functions
43
G.2
Approximation error
G.3
Convergence analysis of RHGD
46
G.3.1
Proof of Theorem
(convergence of RHGD under strong convexity)
46
G.3.2
Proof of Corollary
49
G.3.3
Proof of Theorem
convergence RHGD under weak convexity)
49
G.3.4
Proof of Corollary
51
H
Additional experimental details
52
Quadratic minimization
52
H.I.I
Comparison with baseline algorithms
52
Refreshment behavior
52
H.I.3
Choice of stepsize
53
H.2
Logistic loss minimization
53
H.3 Details of bascline algorithms
54
Helpful lemmas
57
A Related work
Hamiltonian Monte Carlo (HMC). HMC and its variants are widely-used sampling algorithms
implemented as the default samplers in popular Bayesian inference packages such Stan [Carpenter
et al. 2017] and PyMC3 [Salvatier et al. 2016). Notably, the No-U-Turn Sampler (NUTS) [Hoffman al. 2014). celebrated HMC-based algorithm that automatically tunes its parameters, serves as the default sampling method in Stan. However, establishing rigorous theoretical guarantees, such as non-asymptotic convergence rates and developing principled acceleration methods, remain active
areas of research [Talay] [002 Pakman and Paninski] 2003)] Beskos et al. 2013 Betancourt et al.
2014 20i4|Seiler al.] 2014 Durmus al. [2017] Mangoubi and Smith 2017 [ee et al. 2018 Bou-BoouBBaao
and Sanz-Sernal [2018] Lee and Vempala 201 8, Mangoubi and Vishnoi 201 8 Mangoubi and Smith
2019 Bou-Rabes
al. [2020] Chen et al. 2020 Bou- RabeR and Eberle 2021
Mangoubi and Smith
2021 Lu and Wang] 2022 Wang and Wibisono [023a
[0223a/Monmarhhh Monmarché 2022 Jiang 2023 [ and
Gatmiry| [2023] Camrud al.[[2023 [ Soou-Rabes and Schuh [023]] Bou-Rabee and Eberle [202
Monmarché 2024 Bou- Rabee and Marsden [005]. Many recent works focus on understanding
the non-asymptotic behavior HMC [Wang and Wibisono, 2023a Jiang 2023 Monmarché] 2024
Bou-Rabee and Marsden, 2025 These analyses not only quantify convergence rates to the target
distribution but also provide guidance on selecting optimal hyperparameters and developing robust
stopping criteria, thereby offering further insights for algorithmic improvement. A variant of HMC,
25

---

known as Randomized Hamiltonian Monte Carlo (RHMC), has been studied in HobuRaabe and Sanz- 2017]. An intriguing connection between RHMC and underdamped Langevin dynamics is explored in [Riou-Durand and Vogrine 2022 Cao et al.
2023 Jiang 2023 Leimkuhler et al.
2024]: :: specifically, the stochastic differential equation (SDE) characterizing RHMC reduces to the
underdamped Langevin dynamics in the limit [Cheng et al.
2018 Cao et al. 2020 Zhang et al.
2023]. Additionally, several variants of HMC have been proposed to address different challenges.
Some works introduce stochastic gradients to scale HMC to large datasets [Chen et al.
2014 Zou
and Gu 2021]. Others explore Euclidnnn geometry [Brofos and Lederman [202 I
or altered
dynamics, such as magnetic (Tripuraneni al.) 2017] reflection-based [Mohasel Afshar and Domke 2013), or discontinuous dynamics Nishimura et al. 2020]. There are also efforts on adaptation and tuning [Hoffman et al. [219 Hoffman and Sountsov [022]. well as decentralized or parallel implementations [Gürbüzzalaban et al. [021]_ I. Recent work has further proposed application-specffe improvements (Monnahan et [ |Robni et al.. 2023). Additional developments also include
continuous-time formulations [Zhang et al.) [012]. probabilistic integrators [Dinh et al.) (017].
nonparametric extensions (Mak et al. 2021 and entropy
methods (Hirt et al. [002]]
Accelerated gradient flow for optimization. Classical accelerated optimization algorithms are the heavy-ball -aal method proposed by Polyak (1964) and accelerated gradient descent (AGD) proposed by Nesterov| [198]] The continuous- time limit of these two methods corresponds to the accelerated
gradient flow (AGF). which is the combination of (HF) with a damping term for dissipating energy
(see Appendix C.1 for a review), and is different from the pure HF we study in this work. Most existing
Hamiltonian-baser optimization methods can be seen as the discretization of (AGF). Moreover,
Su et al. (2016), Krichene et al. [2015). Wibisono et al. [2016). Wilson et al. [2021]. Suh et al.
[2022] study continuous-time limits of (AGD), and Hu and Lessard [0117] I, Maddison al. [2018),
Muehlebach and Jordan [2019), O'Donoghue and Maddison [2019] Hinder et al. [2020]. Wilson
al. 2021]. Even al. [202T] Attouch et al. [2022], J, (Shi al. [022 Fu et al. [2023], Wang and
Wibisono [023b] design and analyze the accelerated methods as the discretization of (AGF) even
beyond convexity.
Hamiltonian flow for optimization. To the best of our knowledge, only a few previous works have explored optimization algorithms explicitly based on
Hamiltonian flow of the form (HF). Teel et al. [019] studied optimization methods derived from Hamiltonian flow with a velocity refreshment strategy. Specifically, they refresh the velocity to zero whenever the iterate approaches the boundary of region defined as {(z,)) 3) E Rd x Rd : (Vf(z), y) I O, llvll2 2 [[ [2))///L where L the smoothness constant, or after fixed timer expires. They established uniform global stability and convergence guarantees for minimizing smooth and strongly convex functions. Diakonikolas and Jordan [20TT) analyzed generalized Hamiltonian dynamics characterized by a time-dependent Hamiltonian H.. y, r) = hxr))((r/T) + (ha(()) (V), where h(T)) is a positive function of scaled time and a (-) is strongly convex and differentiable. They showed that along these Hamiltonian flows, the average gradient norm | f ( |dr decreases at an O(1/l) rate. Moreover, they demonstrated that broad family of momentum methods, applicable in both Euclidean and non-Euclidean spaces, can be derived from these generalized dynamics. This family includes classical methods such as Nesterov's 's accelcrated gradient method [Nesterov] 1983 2018]. Heavy-Ball method [Polyak] 1964),
and other well-know> accelcrated methods Wiibisono et 2016, Wilson et al.
2021
as special propose a
cases, which are different from what we consider in this paper. De Luca et al.
2023
Hamiltonian- based method with the Hamiltonian defined as Hz, = log F(x)
Fu log(Ily|13)
where À= > and Fo are user-specified parameters. They show that the proposed method together with some heuristics is competitive with Adam (Kingma and Ba 2015) in some deep learning
experiments, but no convergence-rate analysis was performed in the work. |Wang] (024] studies the Hamiltonian flow with velocity refreshment for minimizing strongly convex quadratic functions [xx) = _x2" Ax bT x with A E RRdxd and a = A < T.T: importantly, (HF) can be solved exactly when f is quadratic, which facilitates the analysis. By choosing the integration time mis related to the roots of Chebyshev polynomials, Wang [2024] shows that HF-opt achieves the convergence rate of and the total integration time O(1 l/va), which matches the total integration of accelerated gradient flow with refreshment (Suh et al. 2022
O((1 -
Randomization in optimization. The technique of randomly selecting integration times has been explored in optimization contexts. |Even et al.) (202T) study the "continuized" version of Nesterov acceleration, which also considers random update times to combine continuous time and discrete-time
26

---

perspectives. In their framework, the algorithmic variables follow linear ODE and take gradient steps at random intervals, maintaining the simplicity of continuous- timm methods and allowing for efficient discrete-time implementations. While based on a linear ODE rather than Hamiltonian flow, this continuized approach shares similar spirit with our randomized integration time perspective: both demonstrate how randomness in timing can yield rigorous theoretical guarantees and practical acceleration in optimization.
B Lift-Conserve-Projed scheme
We describe a new methodology to reason about optimization tasks based on conservation rather than dissipation properties, which call the Seff-Connevve-rjjeer (LCP) scheme, and which serves unifying principle across optimization and sampling.
Suppose want to solve the following optimization problem:
min f(x), #EX
where X' is the domain of optimization; for example, X' can be R constraint set, or the space of probability distributions P(RR). Suppose we are currently at state Tu E X. We describe procedure to update zy new state with smaller function value. We need the following ingredients:
A space Z and energy function H:: Z - R.
A lifting map L: X + Z which preserves J, i.e., f(x) H(L(x))-
A conservation map C: Z which preserves H. i... H(22) HH(((z)).
A projection map 2 which reduces f. i.e., H(z) 2 (P(())
The LCP scheme is algorithm LCP: X X that applies the lifting L, conservation C and projection maps sequentially:
LCP = P
Lemma 3. The LCP scheme is descent method, i.e., S(LCP(x)) S f(x).
Proof. By construction, ((PCCoL()) < H(Co
= H(L(x)) = f(x).
B.1 LCP scheme for optimization: Hamiltonian flow for optimization
Before describing HF-opt (Algorithm) I as a LCP scheme, we first prove Lemmas and below.
Lemma Along for all HX,,, Y,) HXu,, Yo).
Proof. Applying the chain rule and the HF) dynamics, we obtain
d H(X,, = (V. Xx, (V,H(X,
dt
= (Vf(())) Y) + (Y, VV((x) = 0.
Thus, HXe,, Y:) is invariant along HF
and (X,,, Yt) H(X., Yo).
Lemma 2 For any and TJk > 0, Algorithm
satisfies [(x++1) S [(xx).
Proof. In one step of Algorithm
HF from (Xo, Yo) (xy, 0) to reach (Xmx Yyn)
(I6+1, 1k+1) for some Vk++1
gd By Lemma f(x+11) f(xx) 11 < fII)).
L
Since (HF) is a conservative flow by Lemma we can choose = Rd -
which is the Hamiltonian function defined by Hx, f(x + | || L(x) C=
which is the Hamiltonian flow map with integration time 0, and IT, which is the projection
to the first coordinate. Given To Rd the LCP scheme is described
27

---

1. Lift: Lift the point E R$ to the augmented phase space R x RR via
L(xo) = (Io, 0).
Note here yo O is the minimizer of the kinetic energy 1lbll12.
2. Conserve: Evolve the Hamiltonian flow (HF) starting from (zo, 0) for duration v obtain
(Eags Mhy HF, (z,, 0).
3. Project: Project (Iay Myy) back to the original space by discarding the velocity:
11 (Tys Mn) Zn-
By Lemma
3 we have f(x,)) S (xo)). This is exactly the HF-opt (Algorithm !
B.2 LCP scheme for sampling: Hamiltonian Monte Carlo
In sampling, the goal is to generate random variable X Fd from target distribution P(RR). This is a fundamental problem that frequently arises in Bayesian statistics. Sampling algorithms typically employ random walks, where each iteration applies stochastic update to the current point. When the target distribution has the form V exp(-ff the sampling problem can be equivalently formulated minimizing the relative entropy (Kullback Leibler (KL) divergence) with respect over the space of probability distributions P(R"):
Sample X ~ v & exp(-f)
min KL(P 1))
PEP(R-)
where KL(p Sen p(x) log p(z)
v(z) de is the KL divergence between p and v. Many sampling algorithms can be interpreted as implementing optimization methods to solve the optimization problem (6) in the space of distributions; for example, the Langevin dynamics is the gradient flow for minimizing KL divergence under the Wasserstein geometry [Jordan et al.) 1998] [Wibisono) 2018). In contrast, another classical and widely used sampling algorithm is the Hamiltonian Monte Carlo (HMC, Algorithm 4) [uane et al. 1987, Neal et al. 2011], which often achieves better performance in practice compared to Langevin- bassd methods.
Algorithm 4 Hamiltonian Monte Carlo (HMC)
1: Initialize xo Rd Choose integration time 7ソ >> 0 for t: 2 O.
2: for k= 1,... K do
3: Sample velocity & ~ NO, Ta)-
4: Set (IR+1, vk-1) = HF, me ().
5: end for
6: return ZK
B.2.1 Distributional properties of Hamiltonian flow
Define auxiliary probability distribution 5( y) & exp (-f(x) 1 21 on the phase space
Rd x Rd The following lemma demonstrates that KL divergence in the phase space with respect is conserved along HF In the proof below, for simplicity we suppress the arguments in the integrals.
Lemma 4. Let (Ia, vc)
HF, (2o, Yo) denote the solution to (FF at time where (2t, v1) Pt-
Then we have
KL 1I KL D)
Proof. Since (æt, satisfies (æt,, ÿ1) = (yi, fxxx))) using the continuity equation in Lemma 14 with the Hamiltonian vector field (,(x,)) y) = (v, - -f(())) yields
(.p(( v) + (p((z.)) ( -v((x) )) 0. -
28

---

Computing the time derivative of (L(pille)
along HF)
we obtain
d dt
(L(
= d
dt /
P: log
Vt = -
Oepe log
Pt 14
+
P
depi
Pt
4 ( (V)(x) ))
Pt
log
+
depe
V/.
Pt / V log
y -Vx(x) ))
Pt
/ V log Pr.
y -V((x)) )) Pt + /
Vf(2)
)
y v)(()) )) Pr.
y
=0
/ -))))))))-)) = (
(-))())
)
- 0,
where V .V.,, Vy)T, and the third and the last equations follow from integration by part. Thus di {p+( 0, which implies KL(p: [|=) (L(Pol)e).
The next lemma shows the chain rule decomposition of KI. divergence. For a joint distribution
P E P(R4 x R2), let xK (x) f p(ær, v) dy be the X-marginal of p. and x (y 1x) (=) conditional distribution, we have the factorization p(z, v) = pK (x) (y xz). Lemma 5, For any joint distributions π E P(IRd x RR,, we have
gla.g) the
(L = KL {T)) Epx
(KL XIX (I ||x]
(8)
Proof. Using the definition of KI. divergence and the conditional distribution, we obtain
/ pxx xx xIx log
x² x
(L(P x) plog =
x
/ xx xIx log
TJ I xxx xxx
px
p log
T
S p² polog" log
px TX xx pix
prx
log x
= KL(6* || T + Exx [KL(prIx |
B.2.2 Hamiltonian Monte Carlo as an LCP scheme
We now describe that HMC is an instance of the LCP scheme on the space of probability distributions. Note one step of HMC from æ3 to #&+1 can be described as follows:
1. Lift: lift PO E P(R") to po(z,, y) Po
(z)
exp (1))l) P(R Rd).
2. Conserve: run Hamiltonian flow (HF) from an initial point (æo, vo) Po with integration
time to get (I,, vny) := HF, (To: yo) ~ Pn-
3. Project: marginalize (I, y) to get P (x) = J (Pn(2,y)dg
In the above, if 3g ~
X then along HMC, Tk+1 ~ pxx where = me is the integration time.
In the initial lifting, since Po Y|x Then we have
- (O, by Lemma 5 we have KL v) KL D).
(L ||D) S KL(P,) 1] = (L || D)
KL vv)
where the first inequality follows from Lemma and the next equality follows from Lemma
This shows HMC is an instance of the LCP scheme, and that it is descent method in KL divergence.
29

---

C Optimization and sampling: algorithms and connections
In this section, review foundational algorithms in convex optimization and log-concave sampling, with a focus on their theoretical convergence behavior and structural similarities. We first review the convergence guarantees of optimization algorithms for minimizing strongly and weakly convex functions. We then review sampling algorithms commonly used for generating samples from log- concave distributions. Based these algorithms, we draw connections between optimization and sampling, emphasizing both their algorithmic parallels and the fundamental gap in convergence guarantees most notably, the presence of acceleration in optimization and its absence in current sampling algorithms. These insights motivate our development of randomized Hamiltonian based methods that aim unify and extend ideas from both domains.
C.1 Review of optimization algorithms with convergence rates
In this section, we revisit some classical optimization methods (for minimizing f) along with their convergence rates. The classical greedy methods in optimization gradient flow (GF) in continuous-time and gradient descent (GD) in discrete-time with stepsize vj >> 0, given by
X, -X(():
(GF)
Fk+1 2k f
(GD)
The classical accelerated methods in optimization accelerated gradient flow (AGF) in continuous- Wibisono et al. 2016 and accelerated gradient descent (AGD) in discrete-
time (Su et al. 2016
time Nesterov 1983
2018 with stepsize 1j O, given by
X, + ((t) VS(X)) =0,
(AGF)
rk+1 = yk V/ f(k),, yk+1 Ix+1 + B 2g),
(AGD)
where B(t) > the damping parameter and 33 > the momentum parameter.
C.1.1
Convergence under strong convexity or gradient domination
Now we review the convergence guarantees of the methods mentioned above for strongly convex or gradient-dominated functions. Notably, strong convexity implies gradient domination, and thus any convergence guarantee under gradient domination also holds under strong convexity.
Continuous-time flows.
Theorem Assume f: Rd > R is o-gradient-dominatee Let X₃ E Rd evolve following GFF from any Xo E Rd. Then for any 2 O, have
f(X.) f(x)) S exx(-22a)(((xx)
Proof. Taking the time derivative of f(X,) - f(x"), we obtain
dt (S(x,) - f(x))) = (V))),) X²) = - -VVx((X)) - -xx( - f(x)))
where the inequality follows from a-gradient domination. Applying Grönwall's inequality completes the proof.
Theorem 7. Assume f: Idd R is a-strongly convex. Let X₁ Rdd evolve following
AGF with
3(1) = 2/a from any Xo E Rdd Then for any t 2 0, we have
s(x.) f(x") < exp(-Vat)
(f(X)) f(x ((0)+
a 2
Xo
Xo x² 1/8
Va
Proof. Define the continous-time Lyapunov function:
& = exp(Vat) [(xx)) (()))f(x')) + a
1 X, - 1012)
X,
+
2 Va
30

---

We can show & S O along AGF with 3(t) = 2/a for 2 0. For complete proof, see the proof Wilson et [2021 Proposition
Remark 1. Comparing Theorem O and Theorem
observe that (GF) converges at rate of
exp( 2ot) under a-gradient domination, which also holds under a-strong convexity. In contrast, (AGF)) achieves a faster rate exp(-vatt under o-strong convexity. Since vo 2o for small
T this demonstrates the acceleration effect of (AGF) compared to (FF).
Discrete-time algorithms.
Theorem 8. Assume f: I + R. is gradiien-ddmmintted and L-smooth. Then for all ls 2 0, along GD with r S 1, from any zo Rd. we have
f(*x) - f(x") = (1 an)* (f(xo)) f(x)))
Proof. Define the discrete-time Lvapunov function: Eg (1-a7) (f(x)))) We can show Ex+1 I Eg for all k 2 along (G)). See Wilson 2018 Appendix B.1.1] for more details.
O
Corollary 3. Assume f: F - R is aa-gradient--oe dominnate and L-smooth. To generate IK satisfying f(œk) - f(x*) & E, it suffices to run (GD) with = F. and from any Io E R for
[[(n) - -x(x²)
K 2 x log
Theorem 9. Assume J: Rdd + R is o-strongly convex and L-smooth. Then for all k 2 0, along 1- Van
(GD)) with 3x-
/t/ 1) S from any Zo = 1o E Rdd, have
f(xx) f(x') s (1 v (f(mo) - f(x²)()x=+))))))()))
a 2 100
x=1 =²)
Proof. A complete proof can found in the proof of Aspremont et al. 2021 Corollary 4.1.5).
Corollary 4. Assume f: Rd R a-strongly convex and L-smooth. To generate æ satisfying
[(ax)-f(C - S e, it suffices to run (AGD) with B4 VK+T and from any Io, E R for
/K-1
K KK log f(xo) f(x')(xxx))))))))))) + 2 2 x=
Remark 2. Comparing Corollary and Corollary 4 we observe that (GD improves upon GD by reducing the iteration complexity from (K log( 1/E)) ) to Oly /oloo (/E)) where L/a a is the condition number. This demonstrates the acceleration effect of (AGD) over GD for strongly convex functions.
C.1.2 Convergence under weak convexity
Now we review convergence guarantees of the aforementioned methods for weakly convex functions.
Continuous-time flows.
Theorem 10. Assume f: R2 > weakly convex. Let X, E Rd evolve following GF from any X, Rdd Then for any & 0, we have
f(Xi) - f(x") < Xn - x=
2t
Proof. Define the continuous-time Lyapunov function: & 11x x01 +(f(X))) -((()))(((z)) We
can show E, S 0 along GFF for 2 See Wilson 2018 Appendix B.2.2] for more details. D
Theorem 11. Assume f: Rd I. is weakly convex. Let X, Rd evolve following AGF with ((1) from any Xn Rdd and Xo E Rdd, Then for any 2 0, we have
f(X.) f(x*) 5 X
r" 1
t2
31

---

Proof. Define the continuous-timg Lyapunov function:
ε = +=((((())) -(xxxx + X1 X. x²
We can show & < 0 along AGF with ((t) 3/t for t 2 0. A complete proof can be found in the proof Su et al. [2016] Theorem 3].
Remark 3. Comparing Theorem T0 and Theorem observe that (GF) achieves convergence
rate of (1//t), while (AGF) improves this to ( This confirms the acceleration effect of (AGF)
GF for weakly convex functions.
Discrete-time algorithms.
Theorem 12. Assume f: Rd R is weakly convex and L-smooth. Then for all k 2 along (D
with S I from any To E IR., we have
f(xx) 5(x*) < 200 x= 112
2n/h
Proof. Define the discrete-time Lyapunov function: Ex = || x=11 + mk(f(xx)
f(x*) We
can show Ex+1 S E5 along (G) for all k 2 0. A complete proof can be found in Wilson 2018 Section 2.1.2].
Corollary 5. Assume J: Rd + R is weakly convex and L-smooth. To generate satisfying [(œx) f(x*) S e, it suffices to run (D) with = + from any Bn IRd for
L ro - 1
K2
Theorem 13. Assume f: Rd TR is weakly convex and L-smooth. Then for all l: 2 along (AGD) with 3x
k-1 S I from any zo, E IRd, we have
E+2
21
x=1
f(xx) - f(x")
n/h
Proof. A complete proof can be found in the proof of Su et al. 2016 Theorem 6).
Corollary 6. Assume f: R2 + R weakly convex and L-smooth. To generate æk satisfying f(xx) f(x*) I e, it suffices to run (GD) with Bx
k+2 I and any zo, y0 E R for
R-1
2L 20 2²112
K
Remark Comparing Corollary 5 Jand Covollary o we observe that to reach an e-accurate solution, (G)) requires (LL=)) iterations, while (AGD) only needs O(vL/e) iterations. This confirms the accelerated convergence of AGD for smooth and weakly convex fumctions.
C.2 Review of sampling algorithms
A natural greedy dynamics for sampling e is the Langevin dynamics (LD) in continuous-time:
dx,- (X(,) + V2dB.,
(LD)
where B, is the standard Brownian motion. A simple discretization of LD is called the umadjusted
Langevin algorithm (ULA):
T&+ = 21. 1) + /2
(ULA)
where Ea ~ No0, /) is an independent Gaussian noise, and v) >> stepsize. However, (ULA) is biased algorithm, which means for each fixed step size it converges distribution [Roberts and Tweedie 1996.. There have been many results on the biased convergence
biased limiting
guarantee of ULA [Dalalyan] 201 7a
Durmus and Moulines 2017 Cheng and Bartlett 2018
32

---

Durmus et al., 2019 Vempala and Wibisono, 2019 Chewi et al. 2024). but due to the bias, it does not have a matching convergence rate with the continuous-tim Langevin dynamics.
An alternative, unbiased discretization of (LD) is the Proximal Sampler (Prox-S) Given the stepsize 1) 0, the update is given by:
Lee et al. 2021
2k EIX (- xx) = (Za,,n))
yk
(Prox-S)
8 x (. yk),
3k++1
yk
where 7(x,y) x exp (-f(z) - 2n - 8/l The Proximal Sampler has been shown to have convergence guarantees that match the Langevin dynamics convergence rates from continuous time; see e.g. Lee et al. [202T]. Chen et al. [2022). Mitra and Wibisono [2025), Wibisono [2025]. Note that
HMC
(Algorithm with f/
also a greedy sampling method discrete-time assuming we can
simulate
(HF) exactly.
Accelerated methods for sampling remain an active area of research. A natural candidate is the underdamped Langevin dynamics (UL)):
dxx = d,d,
(ULD)
dy, = BY, Vf( dt 28 dB
where 3 > O is the damping parameter. Lu and Wang 2022 show that (ULD) has accelerated convergence rate in x² divieeegee continuous time. However, establishing similar acceleration in KL. divergence remains challenging. Furthermore, standard discretizations of (ULD) suffer from being biased [Ma et al., 2021 Zhang et al., [2023] and thus do not exhibit acceleration.
Another candidate to achieve the same acceleration as (AGF) in KL divergence and 2- Wasseeesn distance is the accelerated information gradient flow (AIG) Wang and Li 2022 Chen al. 2025]
X. = =Y, - V(( V (x
(AIG)
where de is the law of X₁. However, discretizing the AIG flow as a concrete algorithm poses significant challenges: the implementation is hindered by the unknown score function V log H4, and the analysis is further complicated by the non-smoothness property of the entropy functional under the Wasserstein metric. Thus, both the development of accelerated sampling methods and the improved analysis of existing methods to show acceleration are still largely open.
C.3
Connection and comparison between optimization and sampling
Langevin dynamics (LD can be interpreted as the Wasserstein gradient flow the Kullback-Leiblee (KL) divergence. More precisely. consider the target distribution v(x) exp(-f Then the Bakker-Plancks equation of (LD). which corresponds the evolution of the law of (LDhis
Ocp = V. (wr log )
where pe Law(X,) and Vw, (L(KL - loVlog log +) is the Wasserstein gradient of the functional (Llllvv) with respect to the 2- 2-Wasserstein metric in the space of probability distributions (R.)). This interpretation, originally developed by Jordan et al. (1998) and later formalized in the language optimal transport by Outo [200T], provides a variational characterization of Langevin dynamics and connects sampling algorithms with the theory of gradient flows in metric spaces; see also [Wibisono] 2018) for a discussion on the algorithmic guarantees.
We summarize the convergence and mixing rates of the aforementioned optimization and sampling methods in Table I Judder the following assumptions:
(SC) f is a-strongly convex + is a-strongly log- log-concave + KL(- [|>) is a-strongly convex.
(WC) f is weakly convex + is weakly log-concave + KL(- || 1)) is weakly convex.
(Sm) f is L-smooth + // is L-log-smooth.
33

---

Method
Assumption
Optimization
Sampling
(WC)
GF 1/t
LD
1/t
Greedy (cont.)
(SC)
GF
exp( -2a)
LD
(WC)+Sm)
GD
1/(k)
Prox S
1/(nk)
Greedy (disc.)
(SC)+(Sm)
GD
(1 om)
HMC
(1 (1-ah?/1
(WC)
AGF
1/t²
AIG
1/1²
Accel. (cont.)
(SC)
AGF
exp(- - Vat)
AIG
exp(-
(WC)+(Sm)
AGD
1/(nk2)
missing
Accel. (disc.)
(SC)+(Sm)
AGD
(1 - Van)
missing
Table 1: Comparison of convergence rates for optimization and sampling methods under different assumptions omitting constants, where & denotes the continuous time; & denotes the iteration count; denotes the stepsize and & denotes integration time of HMC.
Under Assumption (A1), the convergence rates given in squared distance for optimization (e.g.. || x= 1I2) and 2- Wasserstein distance for sampling (e.g., W3 (px, v)). Under Assumption (A2), the convergence rates given in sub-optimality gap for optimization (e.g. f(*x) f(x") and KL divergence for sampling (e.g., (L(Hx|lv)).
Table highlights the structural parallels between optimization and sampling methods under various convexity and smoothness assumptions. both continuous and discrete-time settings, classical greedy methods exhibit matching convergence behavior: gradient flow (GF) corresponds to Langevin dynamics (LD), and gradient descent (GD) aligns with the proximal sampler (Prox-S) or Hamiltonian Monte Carlo (HMC). Similarly. accelerated gradient flow (AGF) and the accelerated information flow (AIG) achieve analogous accelerated rates in continuous time. However, an essential gap emerges in the discrete-time setting: while accelerated optimization methods such accelerated gradient descent (AGD) are well established and enjoy fast convergence rates, their counterparts sampling notably absent.
D Hamiltonian flow with short-time integration
In this section, show that HF-opt (Algorithm D achieves the non-accelerated convergence rate with short integration time 7ソ for gradient- daddinnt-dominated and weakly convex functions. These rates matches the convergence rate of gradient descent (GD) (with h?) under the same assumptions. We first show a descent lemma for HF-opt similar to that of GD.
Lemma 6. Assume f is L-smooth. Then Algorithm with mi = h < VI satisfies
h2
f(x+1)) < f(xx) - 4 [V](2))11
Before proving Lemma 6 introduce the following lemmas that useful the proof.
Lemma 7 (Lee al. (2018) Lemma A.5). Given a continuous function y(t) and positive sealars m, such that S (l) S m + L, f +))(s)) ds, we have y(t) S m cosh( VTt).
We can show the following bound on the velocity along Hamiltonian flow. Lemma 8, Assume f is L-smooth. Then along
(HF) from any Xo E Rd with Yo = O, we have
Y < f cosh Lt).
34

---

Proof. Note that along
HF) we have
Yall (Y,, vf(x.))
||X|||
= -|(
(9)
dt
||'ll
|
Furthermore, we have
VS(X))l (V)())) (((()))) |V*)(X))X| LI
(10)
[V
Integrating I0) yields
VV(()]I s (V [ || ds.
(11)
Integrating 2 and applying
yields
| & |ool + /
+ L S (t-s)]lY,]dds
Suppose < h. Then we have || = vl) + - ->)||=]]| ds. By Lemma we conclude that for 0 t < h:
|| = V cosh Lt).
Choosing / = h completes the proof.
We can also show the following lower bound on velocity along Hamiltonian flow for short time. Lemma 9, Assume is L-smooth. Then along HF) with 0
-tz from any Xo Rd with
Yn = 0. we have || 2 122 ([xo()
Proof. Note that along HF) have
Y =V (x-)v
Therefore, by Taylor expansion around O, we have
Y, Yo + 1oo Rs = -VV + R.,
where R2 = YY (Yo + (Ý)) is the remainder term which can be written as
R. 1/' L0" V, dr S( ('
(1-s)8,ds s) = - 1 -- ()-s))2((Xx))
ds.
Thus we have
| 12 < ( (1- (V=))]l'(((xx))))) do 1, / (1 (1- s)
Applying Lemma with YYll S fXxo) cosh Lt), we obtain
RR || L L / (t Vf cosh( ds
$ V cosh(( Vtt) / (t s)s
(LL).
If / S V then we have
e I cosh( VTt) < cosh (1) < (1-1) (22
(1)=0(111)))
)
35

---

Therefore, by triangle inequality.
| 2 [ |e
- - LIV] cosh LE)
=1 (1 0 FT. T.s.. (ossh))))..)) [VS(X))|
VS(X))]l
Proof of Lemma 6.
We are now ready prove Lemma 6
Proof. Let (IX- 11) HF, (zR, 0) be the solution of (HF) at time h starting from (Zy. 0). By Lemma 1 we have ((*++1) = (xxx /1 Applying Lemma with h S J
VE. we obtain
f(x++1) S f(xx) - 122
4 [+(x))
D.1 Proof of Theorem
Theorem Assume f is L-smooth. Along Algorithm 7 with 7i = VT.
1 from any zo E Rd:
1. f f is a-gradient- then f(xx) - f(x") S (1- (f(#o) - f(x)))
2. If f weakly convex, then ((xx - f(x²) 3411z0 xx112
h2kk
Proof. If f is dogmintent-dominattd, using Lemma yields
[(x41) S [(xx) 2 (J(xx) [(x))) ( (11
ati
ati²
((xx))((x))
which implies
f(xx) -fx) < (1 (1- ah²) x ((zo))f(a=)))
Theorem 2 in Wilson et al. based descent lemma similar Lemma Thus we directly invoke that theorem to prove our Theorem If f is weakly convex and h < VL' then Theorem 2 in Wilson et al. (2019 implies
2019 establish the convergence rates for weakly convex functions
f(xx) - {(x)) 32||00 1²1 + (1)(0(z))) [(x)))(())))))))))))))))}()))-
(32 + 2L 100 x 12
h2k
h2k
34
x=1l" 11?
h²2
D.2 Implementation of HF-opt via leapfrog integrator as GD
Let Leapfrog, : Rd x pd + nd x Rd denote the Icapfrog integrator map with stepsize h 2 0. which is numerical approximation of HFr. More specifically, if we denote (#x+1, yk+1) Leapfrog,, (zy, yx), then it satisfies
3k+ 8k VV(()))
(12a)
36

---

Fk+1 = + hy
(12b)
h
Uk+1 Uk+ (((x+)))
(12c)
Replacing y in 12b and (2c with with (12a), we can rewrite 12 as
h2 v f(x)),
Tk+1 Ikk + hy:
(13a)
2
h (Vf(=*)) + vf(=++1)).
Mk+1 yv
(13b)
Thus we replace HF,, HFne (Ix, 0) in Algorithm (HF-opt) with Leapfrogm, (Ix, 0), we obtain
The 2
(=()));
2k+1
which equivalent to gradient descent with stepsize Tf 22. Note that we refresh yk++1 to be zero before the next iteration, and thus we only focus the update of x. This shows that we can view gradient descent not only as a discretization gradient flow, but also as a discretization HF-opt with one-step leapfrog integrator.
Examples of HF-opt and RHF-opt on quadratic functions
Example (Quadratic functions). Consider the quadratic function f(x) = - Az, where A E Raxd is symmetric and al 1 A < LI, then HF-opt with Tpp- h 2/1 satissiee
ahi
k 1120 x²1
I 1=1 s 1
4
h ZVI. the total integration time achieve |æak- x² < satisfies K 2 8/L log
Imo-="" x====11.
Example (RHF-opt for quadratic functions). Consider the quadratic function f(x) 2 TAx, Ax, where idddd symmetric and al I A I LI, then RHF-opt with y(t)
satisfies
2a
E 1| - 2²113] <
E [|220- -
10000==11""" 2=1
4a
If = 2, the expected total integration time to achieve E
[||C x01 I 6 is K E|TT 2
B|11z-==''] matching that of accelerated gradient flow with refreshment and HF-opt with Chebyshev-based integration time [Wang 2024j. Note that the expected total integration time of RHF-opt smaller than the total integration time HF-opt shown in Example 7
2. log C
Va
Before proving the conclusions in Examples I and and
we first invoke two lemmas from Wang 2024
Lemma 10 WWag 20244] Lemma 2.2). For quadratic function f(x) = 1 T Ax, RHF-opt (Algo-
rithm 2 satisfies
K
x"
II k==
cos v VA) (zo x²),
where VÀ is the matrix square root of A, i.e. VAVA=A A
Lemma 11 (Wang 2024 Lemma A.4). The eigenvalues of the matrix I cos (ALVA) are
Àラ II K-1 I cos (o,), E [d]. where 01, .2........ ... .., aa are the eigenvalues of A.
Proof of Example
37

---

Proof. Using Lemmas 10 and 19
if 77 = h
S
1
1
we obtain
2/02
2VI
FK x²1
cos(hv\))
(10 -000=x)
x²)
k=0
II cos 2 (kw/o)) 11:0 - 2211
max je|d]
k==0
ah?
-100
x²1
4
Thus the total integration time to generate a solution satisfying ||T - x² 112 S is
h K h
log
llog 2
log
ah?
ah
E
a
where the equality holds when 2/L
Lemma 12. If r ~ Exp(7), then we have Elcos"
(VoT)) = 7"+10
25
Proof. See the proof Proposition 2 in Jiang 2023
Proof of Example 2
Proof. Using Lemma 10 and taking the expectation, we obtain
K-1
2
E x - x= 11 =
II
cos
(T
(1o - xx")
A=
K-1
max jEld]
E/cos 2
(Th / vojil
E|xx0 x
E
x=1
k==
K
20 SE(4] 722 40,
min
Ela00 - =x"1'
20, K
<
exp
min jEld
E E x11
722 + 40,
where the second equality follows from Lemma 12 Thus the expected total integration time is
B/Tx] max 7² + 40; log max 7 jE(d]
72 + 40
7 2
1
2
1
loog
log
2
log
20,
20,
2a
?
g
Vo
where equality holds when 22/a.
F Convergence analysis of the randomized Hamiltonian flow
Let Hly denote the operator that maps function é: Rd x Rd + R to Ny Rd x Rd IR given by (TT y) = (5x, 0). Then we provide the following continuity equation for any smooth test functions along the randomized Hamiltonian flow (RHF) defined in Section which is the essential tool for establishing its convergence.
Lemma 13. 7, = (X,, Yz)
of evolve following RHF. For any smooth de: Rd2d
(z,) (Vo,(2.) + (z) - (2(Z)))
dt R (0 (Z,) = Ot
(14)
where b(Z,) (Y,, -x(())) is the Hamiltonian vector field.
38

---

Proof. The time derivative can be expressed as taking the limit:
E El Zz nn) Del (2x)
dt E(,)(2,))
lim 1-+0
Thus we first study the short time behavior of RHF. Using the interpretation at the beginning of Section the probability of refreshment occurring small interval with width h close to (t)h.
Thus the RHF from to & + h can be approximated by the following procedure for small h:
Run (F)) with deterministic integration time h: 2ith (Xith: V(+N) (2,)
Zeth
with probability 1 - -1((,,,
Accept-refresh: Z++h
(X 0)
with probability 7(th.
We can decompose Elor+n (*+th) (xx))))
((tt+((24h)) - (Z,) = El (Z++h) - 2e ( + + -
+ ((ooe(++tn) di (Z++,))
For the first two terms the right hand side, perform Taylor expansion and obtain
ao. at (Zzth) + 0(h3)
Bl (o (7++h))) E
h
Blor(Z++h) 0r
(V (1) b(z)) + O(h²)].
For the last term, we obtain by the probabilistic accepttrreec step
(Z)4))))h)) (e(Z())) E [1 (t)))) (tth (Zetn) ((t)))))))))(( de (Z(th))
(t)h E - (Z(th))
Thus we obtain
d
1ort (2+nh) - (2))
E (d.(Ze) (Ze))
lim
dt
h-0
h
h Dde (Z(+h) + (VVVV( + (t)h (UIvi))Ze)) + O(h3)
E
=lim h-+0
h
Oo: Øt
- ob(22))) -
E
+
F1 Proof of Theorem 2 (convergence of RHF under strong convexity)
Theorem 2. Assume f is a-strongly convex. Let (X,, Y.) evolve following
RHF
with the choice
(t)
16a 5
from any Xo IR with Yo O. Then for any 2 O, we have
- exp (-V a 5
E [(xx) f(x')
1 x x01(3]]
Proof. We construct the following Lyapunov function:
& =xp exp (Vg
a E
f(x,) f(x*) + a
X, x²
5
Yi
(15)
10
Let E, = E f(Xi) f(x*)= + a
X₁ x" + /
Apply the chain rule, and we have
exp (1 a
Eه + exp (v/g) غ.
E V
V 5t
+exp
39

---

In order to show & - 0, it suffices to show E, - -V Apply Lemma 13 by taking or = Es, and we obtain
X1 x² +
(-x(xx)) )
Y
E
(VI(X.),)))
X x +
7())a
5 Y
+
E
|xx x²11?
X1
10
a
( (() 1 55)
(Xe - x², x-,,,,,, (1) + (V= 2(1)
E8
X1, vf(xi))) +
||x.11
2
2/2
3a (X. x², Yi)
E
(J(X,) -(x)))
|x x"
5 |1aa1?
5
2/5
5
aa
2/
20
1 a
E
||, x= 11
+
(X, xx, Yt) + 2/ 5
5
5v5
5
2
a
E
X x²1 + $15
a (x+ xx, Y1) + 4 1111
5
5
5
|V
-V
2V
5
T
(X, - x²) + v.
where the first inequality follows from a-strong convexity:
(x X1, Vf(x))) s f(x)) f(x,) - a _11x, - =x"
2
Thus we have & S Eo. which implies
f(x))
exp (-V6²) C 5
E ((xx) f(xx)
10 1o x x²113]]
F.2 Proof of Theorem 3 (convergence of RHF under weak convexity)
Theorem 3. Assume f is weakly convex. Let (X,, Yt) evolve following
RHF
with the choice
((t) II from any Xo E Id with Yo = O. Then for any t 2 O, we have
5. E f(Xo) - f(x"(((==)))))))))- + 115o 11
([f(X,) - f(aa))
(t 1)2
Proof. We construct the following Lyapunov function:
E
E
(t (f(x,) f(x))) + X, x² +
t 1+ 1
Y
2
7
3
11x, 10113
(16)
4
Apply Lemma
13 by taking Φ = E,, and we obtain
(L + 1)2
V (X.), Y2) + ++1 (f(X)) -((x))
E =E
4
2
X1 x² + +1
)
Vn vf(()) ))
701)
[Ix,- x-12
1+1 2)
+
(+) (X, - x²' + _
X1 x" +
Y,
2
2
t+ Yos 1 Y/ >
3
+ E
X - x² +
+
(Xe - x,,,0, xi)
2
2
40

---

(t 1)2
(VI(X)), Yi) + t+1
(((x)))(xx")) + (
Xx - x=
++
Y 5 Yv
t 1
V s(x:))
2
7(1) (1+ 1)
(X, - x² 7(1) (1+1) 1)2
3 (X, x Yi)
||2/13
+
2
8
( 3 7(t) (t +1)
3(1 +
7(0) (t + 1)²
(X. -0, +
||&||
2
4
8
t + (x) f(x'(((x))))))))))) (x" X1, ( 0
2
where the inequality above follows from the choice ((t) and weak convexity:
(a* Xr, Vf((.))) S fxx") f(x.).
Thus have & S Eg. which implies
5E f(Xo) f(x*) l|Xoo x²1
[X())) f(x))]
s
(t + 1)2
G Discretization analysis
G.1 Randomized proximal Hamiltonian descent
Based the implicit integrator formulation (3, we propose the randomized proximal Hamiltonian descent (RPHD) algorithm:
Algorithm 5 Randomized Hamiltonian Proximal Descent (RPHD)
1: Initialize To E Rdd and Yo = 0. Choose refreshment parameter " > 0, step size h > 0.
2: for k 0, ., K do
3: + = I'k + -hyk
4: Ik+1 P (#
5: Øk+1 yk hV fV
0s+1
with probability (rah,, 1)
6: yk+1 10
with probability min(7uh, 1)
7: end for
8: return TK
G.1.1 For strongly convex functions
We now state the convergence rate of RPHD for minimizing strongly convex functions.
Theorem 14. Assume is a-strongly convex. Then for all is 2 0, RPHD (Algorithm 5 with
0<h h 1,
7k va and any Zo Rd satisfies
1 Vah
-k
(((xx))((x"))
- fxx)) + ||:00 x²
[[((x)) (
1²1
6
72
Proof. We construct the Lyapunov function:
/ ahh &
Es
1
E
f((x)) - f(x²)= + + a
Ib
x
+
6
6
72
Va
We also define
6
27
L =
f(xx) - f(x*) +
Ib
x +
yk
72
va
41

---

In order to show Ex+1 Eg S O, it suffices to show L - Lx S step, we have
6
s/h
LB+1- By the accept-refresh
Tx+1 = -1-7kh)) IR [(0at1)- - f(x") +
6 va
72 Fk+l x² +
Wk+11
+ nhh E [ ( +
|| - x²1]]]
72
2
6
E
f(xk+1) f(x²)((+))))))))
#k+1 x²
va Mk++1
72
a²/hh
6 Mk++
E
|| xx1 x²1
1k41 x²
72
Note that we hide E in the calculation below for simplicity. Taking difference between Lx+1 and La and applying Lemma 15
we obtain
a
6
L
La f(zN+1) f(zx) +
1b+1 - x² +
yk+1
24
xx" +
Uk
72
v
V
a 1/2h
Uh++1 19)
| - x ==112-
Ik+1 x² +
72
Vax
f(x++1 - -((xx) + a
Tk+1 2b +
(JN+1 - Bk),, IR+1 - xx" +
Va ūh+1
36
6 (ūk+1
ad
Vah
Tk+1
Tk +
yk)
(xx+1 x² (ix+1)
18++
III
For we apply a-strong convexity and update (2a] to obtain
ah? ((V
I (VI(Ft+))
xx) |.
18++ 1 112
For 11, we apply updates 22 and
2b
to obtain
ah
Mh+1 (f
1),
T241 x
+
yk-
36
va
ah
x²) Vah
Vah
(jk+1, Ik+1
(VS(Tx+1), - =K+1) - (V
36
6
For III, we apply updates
2a
and
2b) and expand obtain
a
III
lik+1
v
(f*++)ll
Va
ah?
vah²
122
10x+1|1
(
V (x(+11111
6
Combining the calculation above, we obtain
Vah?
Vah 37ah2
5ah
L LA s
(V)())+))
+
110k+1/12
(0 - x,, (1++1)
6
3
72
36
Vah (V](x++1)) x- - -k4+1)
h
V [
(((++11)
6
2
aa
Vah
37ah²
5ah
(Vf(x+41), H2+1)
+
|1
(0x+1 x², xm+1)
6
72
36
Vah
2/2
h2
(f(x*) f(xx+1))
1|
|[
(17)
12
42

---

Since L++1 consists of f(x*) (2x+1). we can write f(x") - (Ix++1) in terms of Lu+1:
f(x*) f(xx+1) = - Lk+11
2x+1 x²
यk+1
va
+ a h/
6
Shtz l')
|106+11 - x=12 112- xk+1 x² +
72
va
11 Ix+zll2 + (Va an
Lk++1
(0n+1 xx (n++2)
+ Vah
||
Substituting f(x²) f((++1) in 17 with the relation above, we obtain
Vah
35a
//
ah
Lk+1 Lu 5
Lk+1
1| -
(0R+1 x², (8++1)
6
432
9
Val
43rrh
1:2
|1ūx+21l 112
4
72
2
val²
2/22
+
(V]( D++1)
( x,, Ūk++1).
(18)
36
Now we control (18
Applying Lemma and assuming a < 1 and h S 1, we have
Vah2
2/2
V
Vf((x++1).... 0k+1)
(xx+1 - x= z",0"+11
6
36
2t
ah
a²/²/2
2222/2
(f(*++1)1*
luk+1 2
1|0 2k+1
1i 1
12
12
72
72
2
Tah²
α
2/22//
V
||
||
| - Jk 1
12
72
72
Plugging this into
18
we obtain
Vah
29a
ah
L
LE
Lk+1
|
Ik+1l
(xx+1 xt, - ,N++1)
432
Vah
ah?
5h2
+
||
V
[x(++11)1
2
12
Val
0x
2/2
ah
Vah
Tx++1
1x*
1
(xk+1
,",ūh++
1
6
27
9
12
Vah
a 2/2h
3
Lk+1
Tk+1
x² +
Øk+1
6
27
2/a
Vah
Lk+1-
6
Thus we have Eg < Ep, which implies
f(((x))f(+1)))
1
Vah
-k
f(0o) - f(x*)(++++)+)))))))))- + a
| - x x²1
6
72
G.1.2 For weakly convex functions
We now state the convergence rate of RPHD for minimizing weakly convex functions.
Theorem 15. Assume is weakly convex. Then for all k 0, RPHD (Algorithm 5 with h >
Th 204 and any To E Rdd satisfies
45E [
11
[ff(xx) - f(x))]
4/2 8)2
43

---

Proof. We construct the following Lyapunov function:
h2 + 8)2
-(=0))>((x))))) + 1
(k: + 8)/
2
3
Es E
rk x=
yk
+ 4
1rx
x²11" 112
we derive E 1 by accept-refresh step:
h?2k + 992
(k: + 9)h
2
Ex+1 = -1 -1-180 hh) E
(f(FA1))-f(r)) f(x")) xh+1 - x²
Mo++1
+ 4
xx+1 - x=1
9
3
(2 + 9)2
3
+ 7ah E
(f(IR+1) - [(x))) + || - x=12 112
| xx1
9
4
h² + 9)3
(f(r - ((x²)) + 1
xk+1 x² + (k+ + 9)4
2
3
E
Mk++1
+
|
x=
9
3
4
17
| - 2²11 xk+1 x² (A: + 9)h
+
E
Dk+1
4(k
+ 9)
3
Note that we hide E in the calculation below for simplicity. Taking difference between E and Eg and applying Lemmal 15
we obtain
(2 + 9)2
(2 +
8)2
Ex+1
Eg
(f(I2+1) f((x))
(f(xx) - f(x)))
9
1
(k: (k+
2
x² + (k- - 8)h
Tk+1 x=" +
Uk+1
2
2
3
3
1k+11
x²1
3
T0 x. 11
+
17
|| =x112 112-
xR+1 x²"
(k: + 9)h
Uk+1
4
4
4(k: 9)
3
(A: + 2/
88
(k +
(k + +8)222
(f(*++1) - f(x))))++++
(f(#2+1) f(xx))
9
9
9
(k + 9)h
(k + 8)h
(k + 9)h
0b+1
Ik +
Uk+1
FR+1
xx +
Uk+1
3
3
3
(k: + 9)h
(A: 8)h
2
3
3
Tk+11
1k+1
Uk
(ok+1 2641 x²)
| xxx1
2
2
IV
17h
17(1: + 9)42
(Ix+1 xx, )))
11
6
36
For Il, we apply weak convexity and update 2a
to obtain
(k + 22
( Jx+1 xx) (I: +&+
(V (V(( Met1).
9
For III, we apply updates
2a
and
2bb to obtain
h +
(k + 2)
V (((#++1) F8+1 - x² (k + 9)h
||I
1eik+1
5k+1
Uk+11
3
3
4h
4(k: + 9)h2
(k (k+ (Vf( -xe+1)
3 (Wk+1, 10 26+1 - -x*> +
11 1
9
(k + 8K(K)(+++ 9)/h"
f 1)
For IV, we apply updates
2a
and 2b and expand to obtain
8122 IV
4(k 8)h²
(k (k+8)21
18++
2
(V (V(( D
[
18
44

---

For V, we apply update 2a to obtain
3h
3h2
1U--1, 2k+1 - x²)
11ū++112
2
4
Combining the calculation above, we obtain
(2k + 17)h²2
(k: + 8)12
Ex+1 F&
(f( [(x)))
(Vf(Ix+1); xk+t)
(k: + 8)h*
(I: 9)h²
59h²
(A 8)
(V((ox+1):00++1)
+
11ūx+112
[**+))))
36
36
18
(k + 8)12
+ 8)h2
(f(*x+1)- - f(xx)) +
(Vf(
xk+11
3
3
(k: + 8)12
59h2
(I: + 1
(Vf(Ix+1))004)
1|u 112
[
3
36
18
(k + 8)
59h²
(k + 2)
11
V f 1)1
3
36
18
h2
59h²
(I: + ht
((k +
11
[+(xx++1) 1
3
36
18
(k + 2)
(k: + //
59h²
[
V f((+++))
h2
01++1
11
36
18
36
(k 2)
23h²
[((+++))]|
V
11
s 0.
36
36
where the second inequality follows from Lemmal and the last inequality follows from Lemma
17 the third inequality follows from weak convexity, Thus we have Es Lo. which implies
16
45E [|100-
x=]
[[f(xx)
f(x))
2 + 8)2
G.2 Approximation error
Starting from F we run proximal point update with stepsize h² to obtain #x+1 and run gradient descent with stepsize 1:2 to obtain J&+1- The following proposition bound the error under smoothness.
Proposition! Lei 0x+11 Prox,2 (roxx2/(5xx5 (5xx-)) and Tk41 = x&+ 1. (( If ʃ is L-smooth
and h T/..T. then
2
| 2n+1
[V(+++))
2L
Proof. We use the following updates to prove this proposition.
$x+1 -4- 112 h (ix+1))
(19)
Jb+1 = -4- f
(20)
(V) - 22 < L 12 - vll..
(21)
where (2) follows from RHGD (Algorithm 3 and the last relation follows from L-smoothness of we obtain
for any x, E Rdd Subtracting (19) from (00
| - 2 h1 (V[l f
I 12 Ix+
8
(V
Using 40 in Lemma
18 we have
[ < 2 - +
2
2I |x+1 -241 2
45

---

Thus we have
| #x+1 11 S 21,"1"1<<x00
S /
then rearranging the relation above yields
21/2//8
| #x+1ll 1 -L [V(
G.3
Convergence analysis of RHGD
Since we lose update (2a for RHGD we construct two dummy iterates 2x+1 and ūk+1 satisfying
Tk+1 Th hÿj+1,
(22)
yk+1 1/: --h (#x+1).
(23)
Substituting 1 in 22 with Øk+11 yk hV from (3) yields Fx41 Proxx2 (Ix 4
We define the error term g as
g ==
Ik+1 ēx+1 + h(i++1 xn+1).
Then we can write
Ek+1
2k Bb+1 + Tx+1 2k+1
hÿR+1 + Ik+1 0b+11
hūk+1 3k-1 -641 + h(x+1 Dk+1)
hik+1 + g
(24)
The next lemma controls the error term 1 Proposition 2. If f is L-smooth, then we have 1| < 2(1 + -2 - #x+1ll?
Proof. Using updates
2b 23 and L-smoothness of f, we have
g
2
| fx+11 + h(0r+1 - +h++1) 1)
< 2|| - -1+1/1 27: 11 ūc+2l 12
= 2||x4+1 - ix+1ll² + 2/ V f(Āx+1) - (
s 2|| - -24+1112 + 2 | Px+1ll2
2(1 131*)|lz4411 fx+ 112
G.3.1 Proof of Theorem 4 (convergence of RHGD under strong convexity)
Theorem 4 Assume o-stroogly convex and L-smooth. Then for all k 2 0, RHGD (Algorithm
with h I WI Th Va and any Zo E Rdd satisfies
Vah
[[f(x)) f(x))]
E
[[((0)) f(x²) + 72 |1:00 x= ==113]
Proof. Consider the following function
a
6
L4 = E f((x) - f(x*) +
Ik
x=
(25)
72
We will bound LE+1 La in terms of LE+1, similar to the proof of Theorem follow calculation Section G.I.I and hide E below for simplicity:
14 in Section
G.
Cx+1 La = f(0x+1)= - f(xx) + 72 (1
2
0a41 - x=
Wk+1
23
x=
yk
Va
Va
46

---

a 2/2h
va 9/-11 11)
| - -x-12
2x+1 x²
6
(ūk+1 ykk) IK-1 x² + 6
f(x++1)
f((x)
24 + 2x+11
va yh+1
36
Va
a
ah
(ox+1 - x², (i++1) Vah 1/ 11.
Fk+1
+
(ūk+1 y1.)
72
6
For we apply a-strong convexity and (24) obtain
(Vf(2+41) mb)
2 [ xxll
(Vf(#++1) hik+1 + gk+1)
hhih++ + 1
2
ah2
(VV 21
18k+
(26)
+ (Vi(=)+)) ( ahl (ū
9
(27)
For 11, we apply
(4 and 2b to obtain
ah ||
6
Uk+1
gh h
(I(+++1), Fk+1
ih+11
36
Va
va
ah
Vah
Vah
(U++1, Jx+1 - x²) +
1 112 +
(Vf(Ix+1), x² - Ix+1) - (VVf(#141) Øk+1)
36
6
(28)
va
G h xk+1-1 - x²)
+
(G #k+1).
(29)
36
6
For III, we apply updates
24
and
2b and expand to obtain
ah
|II
11ū
+
v((x+11)11
72
h
va
ah2
Vah2
112
11 11
112
V
(((x++1),
V [ (xx+1))
72
6
2
ahi
ük+1
6
v[(x++))
1
a
9 11?
36
h
72
ah?
Vah²
1
11ū++1
1|2
(V
V
( ||
(30)
6
oh
Vah
(i
Ih+i)
(Vf(
g
1|
(31)
36
72
Note that
26
and 330
keep the same as upper bounds of I, and III the proof of Theorem 14
(see Section G.
and thus we have
Vah
13a
(Vaah
Vah
ah?
26
30
Cx+1
1|-- - -x+11l2-
+
432
5h
[
V
29
and can be viewed the terms. Collecting the terms, obtain
Vah
(V Gkri
6 (V 9h
(32)
+ Va (i+1 g ah( g
ah
36 (ū+ gh g
(33)
47

---

+
a
g
Tk+1 - -x")
37a
19 11?.
(34)
36
72
Applying Lemma 16
we can upper bound
32
33 and
respectively:
(V((I++))
+
(hV
f vagk+t)
6
212
| ff (x
+
2
1
1
Vf((+++)l1++
a
11
h2
12
12
5h2
2
V [ 11
11 k4+1l 112
24
h2
12
33
11 gk+1) + ((-h)
(( ((-h)iik+ g
6
36
vah
v
ach
ah?
1uk+1
1
+
llu+tll 11? + alll 112
1
11
11 11?
24h
4
72
72
Voh
19ah
Vaa
+
1lūx+all
+
+a
6
72
24h
72
34
1
kk+ a 2/(((<+ 12)))11=)))) -z"))
37a
| k-+1
1||
36
72
va
h22
37a
9
112
1x" - -x2+1
72/2
72
72
Since 7 h = Vah+ < and a S we have
5h2
Vah
19ah?
222222
29
S
[f(
+
+
11ūx+a11
11
1100
1x+111
24
6
72
72
7a
Va
va
+
+
+
12
24h
72h
5
(ah
19ah
22/p22
[[(x++)))
+
+
llūx+all
1
1|00
x2+1l12
24
6
72
72
144 + 42ah2 + +3vah + va |1
+
72h²
5h2
(Vah
19ah?
2/22/2
|
[[(xx+1))1 +
+
llūx+1
1|2
1|00"
xx+1l12
24
6
72
72
95
|1
11
36h²
Combining the upper bounds of 26
+
28
+
30
and
27
+
29
+
31
we obtain
Vah
Ta
//2
17ah2
5h2
LK+1 Lb s
Lk+1
||x"
xx+ill
11
11
|/
[xx++1111
6
432
72
24
95
19ght 112
36h2
Vah
95
5h2
C +
gh
[xx+1)11
(35)
36h
K+1
24
For RHGD, we first choose h <
Then applying Proposition
and Proposition yields
/I
11 1 5255522 (1+ 2) ||
6L2
$x+1 ?1?
S 3|
it 11
< 1 2
[f
If we choose h < 1 1 we have
9522A4 0(1-21463)
5. Thus we obtain from 335
4VI
24
Vah
95
--aah Vah
Cx- L4 <
Cx+1 122
[
Cx41,
24
6(1 - 2L
6
48

---

which implies
(1+
vāh
-
[[f(xx) - s(x))) S Cs -
Lo.
6
G.3.2 Proof of Corollary 1
Proof. If we choose h = AVI. then we obtain from Theorem 4
-K
B[f(oR) f(x))) S 1
Lo
1
Co.
24 L
24vR
where Co = B (x(0) - f(x²) + 1
x² ||2| Let
([f(xx) ((x') 1 24
-K
K
(-21 K
Lo =
24/K*1 (
Lo S eexp
221
Lo So,
which solves
Co
2 (24V* 1) log
G.3.3 Proof of Theorem (convergence of RHGD under weak convexity)
Theorem 5 Assume f is weakly convex and L-smooth. Then for all k 2 0, RHGD (Algorithm) 3 with E SVI' Tk
17 and any Do E Rd satisfies
2(k+9)h
[1:00 x x1] 12(k + 8)2
(f((z))-f(7))
Proof. Consider the following Lyapunov function
( + 8)2
1
(A: + 8)h
3
Eg E
(f(xx) f(x")) + 25 x²
yk
+
z²1|"
9
We will bound Ex+1 Eg terms of E similar the proof of Theorem 15 in Section G.1.2 We follow the calculation in the proof of Theorem 15 and hide E below for simplicity:
Ex+1 Es = 2k 9)2
A + 8)2 (f(xx) - f(x"))
(f(*+41) - f(x"))
9
Tkt1 - + (k: + 9)h
Fk xx + (k + 8)h
#k+1
1/
2
3
3
|k41 x x²1 318 200 - x21 +
||ERA11 - x x²11 2
(k: + 9)h
12
TK+1 x² +
Uh+1
4(k +
3
(A: 2)
(k+88122
(k: + 8)212
(k+ + 8)
(f(x*+1) - f(x*))
(f(*++1) - f(x)))
9
9
9
(k 9)h
(k + 8)h
(k + 9)h
Fb41
Fx +
Uk+t
Mss Fh+1 x² +
Uh++1
3
3
(I: + 9)h
(I: + 8)h
3
Tb+1
+ 2
(0k+1 - Tb. Tb41 x²)
| - =xx|
2
3
4
49

---

17h
17(k + 9)/22
(J8+1 x², -1-11)
1 11
6
36
For I, it simplifies to
(2k 17)h2
((xx+)))((x*)))
9
For II, we apply weak convexity and 24 to obtain
(k 8)
(k: 8)
(VI(xx+)) Dx+1) 1)+ (888)22²
8)2h² [V 1
(I vk)
9
9
For III, we apply
24 and (2b) to obtain
V 8)h2
(k: + 8)h2
x= (k+ 9)h UK+1
III hin++1 + 9
3 J0+t
Fx41
4h
4(k 9)h?
(k +))2
3 (Ūk+1, Ik+1 - x²) +
11
(V (Vf(xx+1), - x4-1)
9
3
(A: + (k
+
(k + 99hh
[Vf(z=+1), xk+1) +
Ix-1 1 x²) +
1c 8k+1).
9
3
For IV, we apply updates
2a
and
2b and expand to obtain
8h2
4(k + 8)43
9 (Vf(xx+1), Dk+1) (k: + 8) 8)
IV =
l 11
fx*++1))
9
18
4h ( De+1)
(k: + 8)12
8)1?
( vf(*x+1)) g 1 11.
3
3
For V, we apply update 2a to obtain
V
3h 2 11+1 x")
3h2
1ū++1 2 +
3
g 19
Tk+1
x²)
3h
(
/ 2 1|
3
2
Note that we obtain the same terms as in the proof of Theorem 15 (see Appendix
G.1 and the error
terms involving thtz For the error terms, apply Lemma 16 to obtain
(k + 2
(9 vf(xx+1)) + (k: (k+8)/2
(A: + 9)h
99t
( kt++ (f(
(G
9
3
17h
( k 1h+11 1) + 2 14441, xx) _
gh
(k: 8)2
1
(gh+ 2 fxx+1))) + (6++8)+++4 h 2 (xx++1) + +g((t= (kk 9)ght) hix+1)
17
5
9 (-h) +
(k + ++)g k 9
(Ie+1 - -x")
7
1
4(h: + 8)2
(K + 2)
(k
|9gh 11
|V ))
2|
|V
9
144
144
(A: + 9)2
1/2
17
17ha2
25(k + 9)2
|
+
||ū++1
1| 1
|1gh
1
11 1|
|
6
4
36
12
||
x11
|
112
4(k + 9)2
4
(I: + 2)
23h²
[(kk + (8)2
9(k + +92
[V[(Tx+1]112
11ūx 1|
Bx+1 +
+7)
|1 112
72
36
(k + 9)2
9
4
(k: + 8)2
23
440(k: + 8)2
[
|| 11
+
Ea+1+ +
+
|1 11
72
36
(I: 9)2
(k + 2
23h²
41 + 8)2
1 11
Ex+1
1 k++1
113
72
36
(k + 9)2
9
50

---

where the third inequality follows from the relation: k + - [k 8) and the last inequality follows from the relation: 7 S (k+s) for k 2 O. Thus, combining the calculation in the proof of Theorem 15 and the calculation above, we obtain
(k: + 8)
23h?
(A: +9hh²
Ex+1 Es S
IV [2(
11
1|
llūk+1 11 +er
36
36
36
(As + h²
41 + 8)2
V ff(
19 | 11
+
ExTI.
(36)
72
(k
9)2
Applying Propositions 2 and
with the choice h S
TVT. S 4//8
1
we have
41 8)2
164(k: + +8)²
L2
1 11
(1+ L2h(t) -(1+L?h²)
[V
1- 21
82(k: + +8)2
1,2
[[
3
1 1-2L415
(k 2)
[f(
where the second inequality follows from h S //.... and the third inequality follows from h S 1 Combining with (36). we have
7VE.
Ex+1 <
(k 9)2
Ex+1
Ex S (K + 9)2
Ex+1
Ex
+ 8) + 10)
Taking the product, we obtain
FR
Fx-1
P. Ed
(k + 8)2
(k + 7)2
g2
Ex
Eu S
Eg
Ex-1
Bx_2
(k+ + () + 99)
(k+ 6) + 8)
8 10
9(k + 8)
Eb - Eo.
8(k + 9)
This implies
- [if(xx)-((x))
E.
12 + 8)2
64h (f(xo) - f(x²)) + 200 - x x=1
IE
12 + 8)2
9
E 72/2 (f(xo)
fxx) ) + 13|| Fi x 1121
112(k: + 8)2
E (36T.22 1000
_2=112 + 13 220 1|]
h?2 + 8)2
14 |||00
x= [|2]
12(k+ + 8)2
where the third inequality follows from L-smoothness of and the last inequality follows from h < TVI
G.3.4 Proof of Corollary 2
Proof. If we choose h
TVT." I_ obtain from Theorem 5
[[f(xx) - f(a))} 686L E [|000 x² [
(K++ 8)2
Let
686L IE. [|100 11
686L E. 12:00 [|2]
S E,
(K + 8)2
K2
51

---

and the last inequality is satisfied whenever
686L E
a x²
K
8
H Additional experimental details
In this section, provide experimental details supplement of Section All experiments were implemented Python 3.10.12 12 and executed with the default CPU runtime. No GPU or specialized hardware used. Most experiments complete within one minute, while some high- condition-number or fine-resolution runs (e.g., quadratic minimization with x = 10²) take up to 5-6 minutes. The total compute required is modest and can be reproduced standard CPU-based environments.
H.1 Quadratic minimization
To generate symmetric positive semi-definite (SPSD) matrix with prescribed condition number, we construct matrix A QAQ", where Q E Rddd a random orthogonal matrix obtained via QR decomposition of standard Gaussian matrix, and A diag(Ar ........ Aa) is diagonal matrix with eigenvalues linearly spaced between a and L. This construction ensures that A is SPSD with spectrum controlled by the given maximum and minimum eigenvalues.
H.1.1 Comparison with baseline algorithms
In the main paper, due to space constraints, we reported only a subset the experiments for quadratic minimization: (1) 10 with exact a, (2) 10? with overestimated 0.01, and (3) 0 with L = 500. Here, we include the complete set of experiments to provide a more comprehensive evaluation. Specifically, we consider:
(1) E {10s, 10 107), = 500 with exact = L/K;
(2) x (108, 10 107), 500 with overestimated E (0.01, 0.1, 1}:
(3) with L E (5 10 10 10*).
These results allow us to evaluate how the performance of each algorithm scales with different condition numbers and parameter estimation errors.
Figure 3 shows the convergence results for setting (1) with exact a under condition numbers x e {10', 10º }. RHGD consistently outperforms GD while being comparable to AGD and CAGD.
Figure 4 presents the results for setting (2), where E (0. overestimated. We observe that while the performance of AGD and CAGD degrade significantly when a is poorly estimated, RHGD maintains robustness across different values of a, demonstrating its practical advantage under parameter uncertainty.
Figure 5 provides the results for setting (3), i.e., when a 0 (weakly convex), with smoothness constants L E (5 x 103 x 10a). RHGD outperform AGD and CAGD in late iterations while being noticeably faster than GD.
H.1.2 Refreshment behavior
To better understand the structure and dynamics of our randomized algorithm, we visualize the objective values function Poisson time, reflecting the continuous-time intuition behind velocity refreshment.
In the case of homogeneous Poisson process, the refreshment probability is constant across iterations, ie., 7%k = Va. This corresponds to the strongly convex setting, where refreshment occurs at a uniform rate. We simulate this process by drawing independent inter-arrival times AT; Exp(1k) with fixed rate 7 = va, and define the cumulative Poisson clock as T Σ AT, We then plot the objective value against Tk. rather than the iteration index. In contrast, the inhomogencous Poisson
52

---

L/a = 10
L/a 10
10'
107
f(x k)--(x
10
(x_.k--(xAa))
10"4
GD
GD
10-9-
AGD
10:4-
AGD
CAGD
CAGD
10-11
12:31
RHGD (ours)
RHGD (ours)
10-
10
122
10P
102
107
201
107
12
Iteration
Iteration
Figure 3: Comparison between GD, AGD, CAGD, and RHGD (ours) on minimizing quadratic functions with & E {10', 108) and optimal stepsizes via grid search. All algorithms use exact Each plot shows results averaged over 5 runs.
L/a= 10', 0=1
L/a = 10", d=1
GD
10'-
AGD
10"
AGD
10"
CAGD
CAGD
RHGD (ours)
[(x
10F-
RHGD (ours)
10"1
(xx)
10
10.
10.20
10'
107
101
10
10
10
10
20P
10
10
10
10
Iteration k
Iteration K
Figure 4: Comparison between GD, AGD CAGD and RHGD (ours) on minimizing the quadratic function with with = 10" and optimal stepsizes via grid search. All algorithms use misspecified (0.1, 1}. Each plot shows results averaged over 5 runs.
process reflects the weakly convex setting, where the refireshment probability decays with iteration. Specifically, we consider a time-varying refreshment rate "í 2(K+9)T and simulate the process
17
using non-stationary exponential samples with rate Tk. i.e. A7; ~ Exp(Te) and Te = Σ AT, This mimics the decaying refreshment frequency used in the weakly convex regime.
In the strongly convex setting, choose 107 with L 500, and h VI/L. In the weakly 500 and
convex setting, we choose iteration versus the accumulated Poisson time Tk. thereby aligning our discrete-ting time algorithms with their continuous-timg interpretations. We also overlay the actual refreshment events markers on the plot, which allows us to visually compare the algorithm's 's progress with the stochastic timing of velocity refreshment. These visualizations confirm that our refreshment mechanisms closely match the intended Poisson-driven behavior and provide an intuitive connection between the discrete-time algorithm and their continuous-time limit flow.
/1/L. Then we plot the objective value at each
H.1.3 Choice of stepsize
When a > O, we fix the smoothness constant (largest eigenvalue) to be 500, and choose the optimal stepsizes via grid search summarized in Table When = O. we evaluate different smoothness constant L, and choose the optimal stepsizes via grid search summarized in Table
H.2 Logistic loss minimization
The feature vectors a; E RRd are generated with i.i.d. standard normal entries, and the ground-truth parameter vector x= E RRd is also sampled from standard Gaussian. Binary labels are assigned according to b, = sign(a) xt + 0.1 E.), where & ~ (/ 1) adds Gaussian noise to simulate label uncertainty.
53

---

a=0 x
a= 5=
30-1
(ours)
14
(ours)
Iteration k
Iteration k
Figure 5: Comparison between GD, AGD CAGD and RHGD with their optimal stepsizes via grid search for minimizing quadratic functions with 0 and L E (5 x 10 x 10"}. Each plot shows results averaged over runs.
RHGD Refreshment vs. Homogeneous Poisson Jump
RHGD Refreshment vs. Inhomogeneous Poisson jump
105-
RHGD
RHGD Refresh (actual)
Refresh (actual)
Hamageeneous Poisson Jump
30
Inhomogeneous Poisson Jump
10
Objective
Objective
20
00-1
10-1
10
10
1000
2005
100D
6000
10
20
30
Timemiteration x stepsize
Time Rteratio x stepsize
Figure 6: Comparison of actual refresh events in RHGD with theoretical Poisson jump times. Left: Th = va vs. homogeneous Poisson process with rate ar. Right: 7 2(K+ vs. inhomogeneous
17
Poisson process with rate ((t) 2(+18h* The r-axis shows time kh with v0.002. Blue dots: actual refreshes; gray dashed lines: Poisson jumps.
In the main paper. we only report the results of a E {10-4.0} 03. Here we provide the remaining commonly used
results corresponding to (10-3, 10-5). $). The setting
10 corresponds
regularization level in practice, providing well-conditioned objective. In contrast, a = 10 yields a more ill-conditioned problem, which serves as stress test for the algorithms but less typical in real-world applications. Figure 7 presents the convergence behavior of GD, AGD, CAGD, and RHGD under both settings. We observe that RHGD consistently outperforms GD and remains competitive with AGD and CAGD across both values of a. Notably, RHGD using 7 2/a consistently achieves faster convergence than " va. These results further confirm the robustness and practical efficiency of RHGD under varying degrees of strong convexity.
H.3 Details of baseline algorithms
For each method, we assume the objective function f is L-smooth and a-strongly convex, where setting = 0 corresponds to weakly convex functions.
GD
AGD
CAGD
RHGD
103
1)
I
1) I
I
h
VI
103
17
I
7)
I
I
h VI
107
h =
Table 2: Stepsizes of GD. AGD, CAGD and RHGD in the strongly convex setting (a > 0) under
different condition numbers x with fixed L = 500.
54

---

L
GD
AGD
CAGD
RHGD
10a
1 =
1 = T
7) == T
h VL
10 77 8L
1 162
1J = SZ
h 8VL
x 10 77 8L
162
7= SZ
h SVL
Table 3: Stepsizes of GD. AGD, CAGD and RHGD in the weakly convex setting (a = 0) under different smoothness constants L.
10
10
10a
10-3
10-5
(00)
10
GD
AGD
RXA)
10"
10'9
GD
AGD
10-12
CAGD
CAGD
RHGD 2va)
RHGD 2ve)
19
(y: vva
10-15
(v:
20P
10
10
10
20"
10"
Iteration K
Iteration K
Figure 7: Comparison of GD, AGD, CAGD and RHGD logistic regression with
{10-3 10-9). We run each algorithm using adaptive stepsizes. For RHGD, we evaluate * v 0 and 7 2/a.
Parameter formulas of Algorithm 7
The update rules in Algorithm 7 depend on parameters
8g. which differs depending on whether the objective strongly convex (a > or weakly convex
-vo if > 0,
(a 0). The specific formula is as follows: 8a
if a
R
The update rules in AlgorithmB3 depend on parameters dg. 8g and 17, which differ depending whether the objective is strongly convex (a 0) weakly convex (a = 0). The specific formulas are summarized Table
Parameter formulas Algorithm 8
Adaptive variants. To improve robustness in practice, we also implement an adaptive stepsize scheme for GD, where the stepsize TJk is adjusted multiplicatively based on the observed decrease in objective value:
[1.1k if f(x++1) < f(xx) The [
7
0.6m%, otherwise
The same mechanism can be applied AGD, CAGD and RHGD variants. We present the adaptive variants of GD, AGD, CAGD and RHGD below, which are called Ada-GD, Ada-AGD, Ada-CAGD and Ada-RHGD. For all logistic regression experiments, we initialize ron and ho 1. When
0, the momentum parameter 34 is computed using the updated stepsize 7 as 8g = T4 T4./om
which reflects the dependence of acceleration the current stepsize. When 0, the momentum
parameter simplifies to 3g k-1 which is independent of the stepsize and follows from Nesterov's R42
acceleration for weakly convex functions.
Algorithm Gradient Descent (GD)
1: Initialize Zo. Choose stepsize 1/L.
2: for = 0, 0,1....; K
3: Tk+1 .Ek fz(x)
4: end for
5: return 2KK
55

---

Algorithm 7 Accelerated Gradient Descent (AGD)
1: Initialize and yo. Choose stepsize 0 < S 1/L.
2: for 0.1,...: K do
3: Ik+1 y4 TV(a)
4: yk+1 1 + (K( FK)
5: end for
6: return 2K
Algorithm 8 Continuized Accelerated Gradient Descent (CAGD)
1: Initialize zo and To 0. Choose stepsize 0 < S L/L.
2: for k == 0, 1, ....., K do
3: Sample ~ Exp(1) and set Tk+1 = TT + Th
4: yk = r& (3k I&)
5: Tk+1 yk 1, f
6: Zk+1 zk 8% (yk 2k) 176 ((kk)
7: end for
8: return ØK
Parameter
> 0
0
0₂
(1 - exp(-2var7
Ty Te+1
8% tanh (voTT
0
Txn 2
?/k
Table 4: Parameter choices Algorithm for different regimes of a.
Algorithm 9 Adaptive Gradient Descent (Ada-GD)
1: Initialize zo and stepsize 7o > O.
2: for k == 0, 0, K
do
3: $1+1 = I6 176 V fzx)
4: if fāx++1) < f(xx)=
V then
5:
17++1 = 1.1 T7
b Increase stepsize Accept trial step
6:
#k++1 -
7:
else
8:
1]k+1 0.6 7K
Decrease stepsize b Reject trial step
9:
2x41 Ih
end if
11:
end for
return JK
Algorithm 10 Adaptive Accelerated Gradient Descent (Ada-AGD)
Initialize To. yo. and stepsize T/o O.
2: for k = 0....... K- do
3:
$t+1 yk 7iK f
4:
if f(xx+1) < (wk)
f[l) then
5:
17 1.1 7Tk
b Increase stepsize Accept trial step
6:
Tx+1 Tx++1
7:
else
8:
7]++1 0.6 TK
& Decrease stepsize Reject trial step
9:
Øx+1 = Ik
10: end if
11:
Uk+1 = Tk+1 + 3x xx))
12:
end for
13:
return ØK
56

---

Algorithm 11 Adaptive Continuized Accelerated Gradient Descent (Ada-CAGD)
1: Initialize 2o, 20 2u, To 0, and stepsize ?/ 0.
2: for k = 0, ... K do
3: Sample т Exp(1) and Tk+1 Tи Th
4: Compute 02 using 7/k, Tk. Ta and TR+1 as shown in Table
5: yk = Iy 00( x&)
6:
Tk+1 yk Th V (uk)
7:
if f( f(kk) Iu [y))
then
8:
7]++1 = -1.1-1 77k
> Increase stepsize Accept trial step
9:
#k+1 8k+1
10:
else
7/++1 0.6 1
b Decrease stepsize Reject trial step
12:
Jk+1 Ick:
13: end
14:
Compute 0z and m using updated 11-11 Th and Tr shown in Table
15: 2k+11 = 2k + (Bk - 2ạ) 776 V f(y))
16:
end for
17:
return 2K
Algorithm 12 Adaptive Randomized Hamiltonian Gradient Descent (Ada-RHGD)
1: Initialize zo. Yo 0 and ha 0. Choose refreshment parameter " 0.
2: for == 0, 0, K do
3: Ik+7 = h4
4: āk+1 x - 1/ V (Tx+T))
if (( < [ - IVV )l
5:
then
6:
h&41 v1.1 .hk
> Increase stepsize Accept trial step
7:
Øx+1 = .x+1
8:
else
9:
h&+1 V0.6 ha
b Decrease stepsize Reject trial step
Fk+11 Tk
11: end
12:
ūk+1 yk hg41 V (3
yk+1 Øs+1 with probability min (7ah441, 1)
with probability min (7x4441,1)
end for
15:
return
I Helpful lemmas
Lemma 14. Let vi E Rd be a family of vector fields and suppose that the random variables t + Za evolve according to
2. = ===v)(Z)
Then, the law Pr of Zu evolves according to the continuity equation
O.p. + V (prvs) 0.
(37)
Proof. Given smooth test function Φ : Ied R. we obtain by the chain rule:
(VD(Z)). 20) (
di Blo(2.) -
(V)(Z)
For the left hand side, we can write
d d B(((Z)) di pc(=)o(2)dz 0.p(())d(2)dz.
57

---

For the right hand side, applying the integration by part, we have
((VV(Z)). = /
ff (0)()) dz.
Thus have
I ( = f (=)()) )
Since this holds for every test function Φ, we obtain dipe + V (peei) O.
Lemma 15 (Three- (Three-point identity). For all x, y, E Rdd, we have
|| - y/l || = =1|2 = 2, x v) lly =||?.
(38)
Proof. Expanding the squared norm and rearranging yields the claimed identity. Lemma 16 (Young's inequality). For all
E R= and p > O, we have
(z. v) S p|01|| 4p 11y11
(39)
Proof. We have
pr
2| +
- |1yl| (0r, y) 2 0,
1
2/P"
4p
which implies the conclusion.
Lemma 17. For all k: 2 O, we have 2k+17 < k+8
Proof. It suffices to show 2k+17 k+8
$ 3. Since
k+8 S 1, we have
2k+17 k+s
2 + 1 k+8
S 3.
Lemma 18. For all x, E Rd, we have
| + v/1² < 2||21|1 + 211
(40)
Proof. || y112 (2|10|12 21|y/13) (||=||12 - 2(x, v) + ||ub13) -1 y112 < 0.
Lemma 19. For
1. we have cos ( (x) 5 S.2
Proof. Let g(x) cos (ar) 302² 1. Then g (x) = - sin $2n) + and g"(xx -2 cos (2x)
Since < r - 1/2 S E. we have cos(2x) 2 1/2 which implies g"(x) s for x E [o, 1.. Thus g(xx)
is monotonically decreasing for x E [0, }] which implies g'(x) S g0( = -0. Thus g(x) is also
monotonically decreasing for x E j0, 2.. Then we have g(x) cos)(x) + =1=-- S 9(0) = 0.
which implics (x) < x² 2
58


Reviews:
[{"review_id": "4ygIfZO5CB", "reviewer": "Reviewer_KAWd", "summary": "This paper proposes an optimization method inspired by Hamiltonian Monte Carlo (HMC), which follows the system’s equations of motion. At random intervals, the momentum is reset to zero, causing the state to converge to a (local) minimum rather than oscillating around it. The approach aligns with recent Hamiltonian-based optimization techniques, such as [Wang 2024]. To the best of my understanding, the primary difference is that in [Wang 2024], momentum truncation occurs after fixed evolution times, whereas in this work, those truncation times are sampled at random.\n\nThe authors provide theoretical convergence rate bounds which, as far as I can tell, are comparable to those established in prior work on related algorithms. Given these similarities, I find it difficult to clearly assess the novelty of the proposed method relative to the existing literature.", "questions": "1. As you mentioned, most existing Hamiltonian-based optimization methods use a damping term for dissipation energy. You highlight that your works (along with [Wang 24]) is not so. My question is that why should that be an important feature? Since, as far as I can say, setting the momentum to zero (either at random or fixed intervals) in effect plays the role of friction and damping, causing the state to converge to a (local) minimum rather than oscillating around it. Can you comment on this?", "limitations": "One limitation is that the established bounds hold in expectation due tot he randomness of the algorithm which is specified in the paper.", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n1. The paper is well-written. The notations are clear, and the formal derivations are rigorous. \n2. In practice, (on the toy examples that they provide), their algorithm is comparable to continuized AGD (CAGD).\n3. Theoretical bounds on the convergence rate are proved. \n4. [After rebuttal] An Interesting and deep relation between the proposed optimizer and HMC is established. \n\nWeaknesses:\n1. The significance of the contributions, compared with similar methods such as \"Frictionless Hamiltonian Descent and Coordinate Hamiltonian Descent for strongly convex quadratic problems and beyond\" (https://arxiv.org/pdf/2402.13988) is either not clarified or the contributions are minimal. \n2. No comparison is made with any existing Hamiltonian-descent-based optimization algorithms, such as [Wang 2024]. \n3. The comparison is only carried out on toy models.", "was_revised": true, "final_justification": "In the rebuttal discussions, I realised that the authors have presented an interesting theoretical bound between their approach and HMC via a scheme that they call LCP.\n\nRemaining insufficiencies:\nThe authors should spell out the comparisons with [Wang 2024].", "rebuttal": "Thank you for the comments and feedback. Please kindly find our response to the questions and concerns below.\n\n**1. The significance of the contributions, compared with similar methods such as [wang 2024] is either not clarified or the contributions are minimal.**\n\nAs we claim in line 69-70 and line 141-142, [wang 2024] only establishes the accelerated convergence of HF-opt via Chebyshev-based integration time for **quadratic functions** whereas our paper establishes accelerated convergence rates via randomized integration time for **general strongly and weakly convex functions**. In general, the algorithm in [Wang 2024] is not implementable due to the exact simulation of Hamiltonian flow, whereas we propose an implementable algorithm in discrete time that preserves the accelerated convergence rates. We believe that this is a significant contribution.\n\n**2. No comparison is made with any existing Hamiltonian-descent-based optimization algorithms, such as [Wang 2024].**\n\nWe will clarify the comparisons with [Wang 2024]. We would like to note that [Wang 2024] focuses on quadratic functions, while our work treats general strongly/weakly convex functions. We would also like to highlight that in the case of the quadratic objective function, our result shows RHF-opt achieves a sharper accelerated convergence rate without having to assume smoothness (finite L), while the result of [Wang 2024] requires smoothness (finite L), see Appendix E.\n\n**3. The comparison is only carried out on toy models.**\n\nWe would like to clarify that our experiments include two widely studied and representative convex optimization problems: quadratic minimization and logistic regression. These are standard benchmarks in the literature and are commonly used to evaluate the behavior of optimization algorithms, especially in the context of understanding convergence and acceleration. We agree that evaluating the method on larger-scale or nonconvex problems would be an interesting direction for future work.\n\n**4. Why should setting the velocity to zero be an important feature?**\n\nOur work is inspired by the Hamiltonian Monte Carlo (HMC) algorithm for sampling, where refreshing the velocity is the key to decreasing the KL divergence (see Appendix B.2). The HF-opt we propose is a direct translation of this principle (that we call the Lift-Conserve-Flow/LCP principle, see Appendix B) to optimization. Both our work and [Wang 2024] strengthen the link between HMC and optimization. Our work also study the acceleration in optimization from a new perspective and proposes novel accelerated dynamics and algorithms as candidates of accelerated optimization methods.\n\n**5. For novelty**\n\n- Our work is the first to study the Hamiltonian flow for minimizing general strongly convex, gradient dominated and weakly convex functions.\n- Our work is the first to establish the acceleration for strongly and weakly convex functions based on Hamiltonian flow with randomized integration time in both continuous-time and discrete-time."}, {"review_id": "aazLvRQVxH", "reviewer": "Reviewer_9m2g", "summary": "The paper proposes to add a downward jump term to the velocity to the Hamiltonian flow such that at random Poisson times (which can be non-homogeneous), the velocity is reset to zero. By randomizing the integration time, the paper shows that the resulting randomized Hamiltonian flows achieves accelerated convergence rates in continuous time, similar to those for accelerated gradient flow. The paper also studies the discrete-time algorithm based on randomized Hamiltonian flows, and obtained theoretical guarantees for expected suboptimality,  which enjoy the same convergence rates as Nesterov's accelerated gradient descent in both strongly convex and weakly convex settings.  Numerical results are also provided to show the efficiency of the proposed algorithm.", "questions": "(1) In your equation (RHF), I think you should write $Y_{t-}dN_{t}$ instead to be more rigorous.\n\n(2) The Poisson intensity $\\gamma(t)$ is constant for strongly convex setting and decreasing for weakly convex setting. That reminds me of choosing constant stepsize for strongly convex setting and decreasing stepsize for Nesterov's accelerated gradient descent. I am wondering if there are any connections here.\n\n(3) It would be helpful if the author(s) can add some discussions (if not already) the intuitions why the proposed method can accelerate. Also, $\\gamma(t)$ is a function of time in general, and that is indeed the choice in the weakly convex setting. But $\\gamma(t)$ is independent of the Poisson arrivals in the model. I am wondering what is the intuition to choose $\\gamma(t)$ this way, instead of for example choosing $\\gamma(t)=\\phi(t-\\tau_{i})$ between two Poisson arrivals $\\tau_{i}$ and $\\tau_{i+1}$, i.e. reset the Poisson intensity after the velocity hits zero.\n\n(4) It seems that you missed quite a few references when you discuss underdamped Langevin algorithms, for example, Chau and Rasonyi (2022) Stochastic Gradient Hamiltonian Monte Carlo for Non-convex Learning, Dalalyan and Riou-Durand (2020) On sampling from a log-concave density using kinetic Langevin diffusions, Gao et al. (2022) Global Convergence of Stochastic Gradient Hamiltonian Monte Carlo for Nonconvex Stochastic Optimization.\n\n(5) In the reference Andre Wibisono, Ashia C Wilson, and Michael I Jordan, proceedings should be Proceedings.", "limitations": "Yes.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 3, "originality": 4, "strengths_and_weaknesses": "Strengths:\n\n(1) The continuous-time and discrete-time methods proposed in this paper are novel to the best of my knowledge. Interestingly, the proposed method can achieve the same accelerated convergence rates as Nesterov's accelerated method. \n\n(2) The paper is very well written, and the analysis seems to be rigorous.\n\n(3) Numerical results are promising.\n\nWeaknesses:\n\n(1) It would be great if the author(s) can provide some guidance when it is better to use Nesterov's accelerated method and when it is better to use your proposed method, especially because it works under expectations only. \n\n(2) In practice, stochastic gradient is often used, and it would be interesting to investigate the sensitivity to gradient noise for the proposed method. But I understand that this is beyond the scope of the paper, and should be left as a future research direction.", "was_revised": true, "final_justification": "I am satisfied with author(s)' response. I am keeping the score.", "rebuttal": "Thank you for the positive comments and feedback. Our responses to the questions and concerns are provided below.\n\n**1. It would be great if the author(s) can provide some guidance when it is better to use Nesterov's accelerated method and when it is better to use your proposed method**\n\nWe appreciate the reviewer’s helpful suggestion. While we do not yet have a complete theoretical characterization, our experiments suggest that the proposed method is more robust to parameter misspecification. In particular, when the strong convexity constant is small, unknown and must be estimated heuristically, our method tends to perform better than Nesterov’s accelerated method, which can be sensitive to such inaccuracies.\n\n**2. Stochastic gradient variants**\n\nThis is a very interesting direction, especially since the stochastic gradient variants are more applicable and scalable in large-scale settings. We would be happy to explore this in future work.\n\n**3. In your equation (RHF), I think you should write $Y_{t^-}dN_t$**\n\nThank you for pointing out. We followed the same notation about the Poisson process as [Even et al., 2021] in the submission. We will change it as the reviewer suggested to be more rigorous.\n\n[Even, et al. \"Continuized accelerations of deterministic and stochastic gradient descents, and of gossip algorithms.\" NeurIPS 2021.]\n\n**4. Connection between Nesterov's AGF (AGD) and RHF (RHGD)**\n\nThis is a very good catch. The choice of $\\gamma$ is similar to the choice of damping parameter. However, the constants are not totally the same. We are interested in exploring the connection between RHF (RHGD) and AGF (AGD) in the future.\n\n**5. Intuition on why randomization can lead to acceleration**\n\nBy energy conservation, if we initialize the velocity to be zero, we can decrease the function value as we evolve the Hamiltonian flow (HF). Then we study how long we should evolve HF. As we show in Theorem 1, the short-time integration only recovers the same non-accelerated convergence rates as GD, which implies that the short-time integration doesn't efficiently decrease the function value, and we need potentially longer integration time. Another intuition comes from sampling, namely there is a conjecture that Hamiltonian Monte Carlo with randomized integration time can achieve accelerated mixing time for sampling. This has been shown in the idealized continuous-time setting in [Lu and Wang, 2022], and discussed in further details in [Jiang, 2023]. Our work can be seen as an optimization analogue of this question, and we show that randomized integration time does indeed lead to acceleration, both in continuous and discrete times.\n\n [Lu and Wang, “On explicit $L^2$-convergence rate estimate for piecewise deterministic Markov processes in MCMC algorithms’’, Annals of Applied Probability, 2022.]\n\n [Jiang, \"On the dissipation of ideal Hamiltonian Monte Carlo sampler.\" Stat 12.1 (2023): e629.]\n\n**6. Intuition on the choice of $\\gamma(t)$**\n\nIn our setup, $\\gamma(t)$ serves as the intensity of the Poisson process, and we chose it in this specific form primarily to make the convergence proof work. While this choice may seem somewhat technical, its resemblance to the time-varying damping coefficient in Nesterov's accelerated gradient flow [Su et al, 2016] lends further plausibility. Exploring alternative designs is indeed interesting, and we leave this for future investigation.\n\n[Su, Boyd and Candes, \"A differential equation for modeling Nesterov's accelerated gradient method: Theory and insights.\" Journal of Machine Learning Research 17.153 (2016): 1-43.]\n\n**7. Reference missing and wrong capitalization**\n\nThank you for pointing out these issues, we will correct them in the revision."}, {"review_id": "IpNSiR1akq", "reviewer": "Reviewer_QLTJ", "summary": "This paper studies the Hamiltonian flow for optimization (HF-opt). The authors show that HF-opt has the same convergence rates as gradient descent for minimizing strongly and weakly convex functions. The authors also propose the randomized Hamiltonian flow (RHF) by randomizing the integration time, which achieves accelerated convergence rates in continuous time. This paper also studies a discrete-time implementation of RHF as the randomized Hamiltonian gradient descent (RHGD) algorithm, which achieves the same accelerated convergence rates as Nesterov’s accelerated gradient descent (AGD) for minimizing smooth strongly and weakly convex functions.", "questions": "1. Theorems 2 and 3 establish the convergence rate in continuous time without smoothness assumption. For the discrete time case, Theorems 4 and 5 need the L-smooth assumption. What is role of L-smooth when discretizing a continuous system?\n\n2. Why can randomness accelerate Hamiltonian flow? What is the intuition?\n\n3. Can the authors elucidate the physical principles underlying the descrete-time Algorithm 3? For example, what does each of the four steps on lines 3-6 mean? There are many accelerated algorithms developed from the continuous-to-descrete view, providing an intuitive physical interpretation would significantly advance our understanding of acceleration mechanism.", "limitations": "The proposed descrete RHGD algorithm needs two gradient computations at each iteration, which may make RHGD two times slower than the standard AGD.", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n\n1. This paper propses the randomized Hamiltonian flow (RHF) for optimization and stablishes its accelerated convergence rates of $O(exp(-\\sqrt{a/5}t))$ for $a$-strongly convex functions and $O(1/t^2)$ for weakly convex functions. \n\n2. This paper proposes the randomized Hamiltonian gradient descent (RHGD), a discretization of RHF. Under L-smoothness assumption, The authors establish the $\\widetilde O(\\sqrt{L/a})$ complexity for a-strongly convex functions and $O(\\sqrt{L/\\epsilon})$ for weakly convex functions. These complexities matches the optimal accelerated rates of AGD. \n\n3. The RHGD is a new algorithmic formulation of acceleration, expanding the family of accelerated algorithms with a new member. It may advance the understanding of acceleration mechanism from the view of Hamiltonian flow.\n\n4. The theory is solid and the proofs are organized well.\n\n5. The paper is well-written.\n\nWeaknesses:\n\n1. The RHGD algorithm in Algorithm 3 needs two gradient computations at each iteration. In most machine learning applications, gradient computation constitutes the most time-consuming operation. This makes each step of Algorithm 3 two times slower than the standard AGD. Especially, in Figures 1 and 2 which uses the iteration as the X-axis, RHGD performs similar to AGD, making RHGD almost two times slower than AGD when using time as the X-axis.\n\n2. The convergence rate of RHGD holds in expectation. The authors argue that  convergence in expectation can still imply high-probability bounds for via Markov’s inequality. However, Markov’s inequality makes the algorithm $1/\\gamma$ (or $log\\frac{1}{\\gamma}$) times slower when the convergence holds with probability at least $1-\\gamma$.\n\nIn conclusion, this paper is well-written. The theory is solid. The Hamiltonian flow perspective of acceleration seems interesting. However, it seems slower than AGD and lacks practical utility.", "was_revised": true, "final_justification": "I agree to accept this paper", "rebuttal": "We thank the reviewer for the positive and constructive feedback. Our responses to the questions and concerns are provided below.\n\n**1. What is the role of L-smooth when discretizing a continuous system?**\n\n$L$-smoothness plays a central role in our discretization and analysis. Specifically, we assume that the objective function is $L$-smooth to ensure that the discretized dynamics accurately approximate the behavior of the continuous system. In the context of optimization, $L$-smoothness is a standard assumption when transitioning from continuous-time dynamics to discrete-time algorithms. For instance: discretizing gradient flow to gradient descent requires smoothness to ensure stability and guarantee convergence under appropriate step sizes (see Theorems 6 and 8 in Appendix C.1.1). Similarly, discretizing accelerated gradient flow into accelerated gradient descent also relies on smoothness to control discretization error and preserve acceleration (see Theorems 7 and 9 in Appendix C.1.1). In our work, L-smoothness enables us to bound the approximation error (see Proposition 1 in Appendix G.2), which is the key to the convergence of Algorithm 3 (RHGD).\n\n**2. Why can randomness accelerate Hamiltonian flow? What is intuition?**\n\nAs we show in Theorem 1, the short-time integration only recovers the same non-accelerated convergence rates as GD, which implies that the short-time integration doesn't efficiently decrease the function value, and we need potentially longer integration time. Another intuition comes from sampling, namely there is a conjecture that Hamiltonian Monte Carlo with randomized integration time can achieve accelerated mixing time for sampling. This has been shown in the idealized continuous-time setting in [Lu and Wang (check)], and discussed in further details in [Jiang, 2023]. Our work can be seen as an optimization analogue of this question: we show that randomized integration time does indeed lead to acceleration for acceleration, both in continuous and discrete times.\n\n[Lu and Wang, “On explicit $L^2$-convergence rate estimate for piecewise deterministic Markov processes in MCMC algorithms’’, Annals of Applied Probability, 2022]\n\n[Jiang, \"On the dissipation of ideal Hamiltonian Monte Carlo sampler.\" Stat 12.1 (2023): e629.]\n\n**3. Can the authors elucidate the physical principles underlying the discrete-time Algorithm 3?**\n\nWe thank the reviewer for this excellent question. Since our method is derived from discretizing a randomized Hamiltonian flow, the algorithm naturally admits a physical interpretation inspired by classical mechanics, where $x_k$ represents position and $y_k$ corresponds to velocity. Below we explain each step (lines 3–6) from this perspective: \n\n- Line 3 performs a half-step position update using the current velocity, consistent with the Leapfrog integrator in Hamiltonian dynamics. It reflects how a particle’s position changes under its inertial motion, prior to any forces being applied. \n\n- Line 4 is a force-induced correction to the position, using the gradient of the potential energy (objective function). Physically, it corresponds to the second half of the position update, now taking into account the effect of the force field. The form resembles a position Leapfrog step and is critical for stability and accuracy.\n\n- Line 5 updates the velocity according to Newton’s second law $\\dot{Y}_t=-\\nabla f(X_t)$, which reflects how the gradient affects the velocity, pushing the system toward low-energy regions.\n\n- Line 6 corresponds to a random velocity reset. With a small probability proportional to the refresh rate $\\gamma_k$, the velocity is zeroed out to inject dissipation and prevent the system from accumulating excessive momentum or oscillations. This mechanism plays a key role in balancing inertia (acceleration) and stability, and is crucial for escaping flat regions or poorly conditioned directions.\n\nWe will incorporate this interpretation into the final version to clarify the physical intuition behind RHGD. \n\n**4. Two gradient evaluations of Algorithm 3**\n\nWe appreciate the reviewer’s observation regarding the number of gradient evaluations. It is true that Algorithm 3 (RHGD) requires two gradient evaluations per iteration, which arises naturally from the discretization of the underlying Hamiltonian flow. In fact, this two-gradient structure appears to be inherent in many established discretizations of Hamiltonian dynamics, such as the Leapfrog integrator widely used in Hamiltonian Monte Carlo and related methods. From our perspective, this structure is not merely a cost, but a design choice that contributes to the robustness and stability of RHGD. In our experiments, we observe that RHGD is more robust to parameter misspecification compared to other first-order methods, potentially due to the richer feedback provided by evaluating the gradient at multiple points. We recognize that gradient cost is a valid concern in practice. An interesting direction for future work is to explore gradient-efficient variants of RHGD while retaining its acceleration and stability properties.\n\n**5. Worse high probability bound via Markov’s inequality**\n\nWe appreciate the reviewer’s observation. We agree that Markov’s inequality yields loose bounds, and our intention was not to claim tightness, but to demonstrate that the convergence in expectation can be converted into a high-probability guarantee without additional assumptions, which is consistent with some prior works, e.g., [1] and [2]. Given the randomized velocity refresh in our algorithm, stronger concentration results would require assumptions such as bounded variance or martingale structure. To keep the analysis general and assumption-free, we opted for the Markov-based bound. We agree that deriving tighter bounds under additional structure is an interesting direction for future work and will clarify this in the revision.\n\n[1] Mathieu Even, et al. \"Continuized accelerations of deterministic and stochastic gradient descents, and of gossip algorithms.\" NeurIPS 2021.\n\n[2] Jun-Kun Wang, and Andre Wibisono. \"Continuized Acceleration for Quasar Convex Functions in Non-Convex Optimization.\" ICLR 2023."}, {"review_id": "r8brmuoxDJ", "reviewer": "Reviewer_DNKQ", "summary": "This paper presents new connections between optimization and Hamiltonian dynamics. Specifically the authors study the Hamiltonian version of the gradient flow dynamics. They show that for periodic resetting of the velocity, the exact integration yields convergence rates that match deterministic gradient descent, in both weakly and strongly convex/PL condition cases. Aspiring to improve these rates to match those of accelerated gradient descent (AGD), the authors consider the idea of randomizing the reset/integration time. Typically they propose a non-homogeneous Poisson process to govern the resets. Within each period, they further disco ties the Hamiltonian dynamics to obtain and implementable algorithm (RHGD), which has expected convergence rates matching AGD. I am quadratic opt simulation and logistic regression problems, the performance of RHGD is similar to other accelerated methods and more robust in some circumstances.", "questions": "Major:\n1. In the paragraph \"Approximate Poisson process.\" an acceptance-rejection scheme is described. However, I can think of alternative approach that first samples a path/trace of the Poisson process for $K$ steps. Indeed, this can be done totally independently of the dynamics I think. This gives a sequence of inter-arrival times. Then, within each subinterval of that sequence, you can discretize the HF dynamics. Will this approach also work? If not, shat is the drawback of this approach compared to yours?\n2. You propose an implicit (backward Euler) integrator. Is explicit Euler not stable here? Can you elaborate?\n3. You mention \"Nevertheless, convergence in expectation can still imply high-probability bounds...via Markov’s inequality.\" However, traditionally in optimization, Markov is not enough and you need a light-tail assumption and stronger concentration inequalities to get high-probability bounds. I think this is firmly beyond the scope of this paper, but I would still appreciate further comment (or correction) on this brief comment you made.\n4. All of your quadratic instances in Section 5.1 have minimizer $x^\\ast = 0$. This is a bit non-standard (usually a linear term is added), but perhaps WLOG. Can you elaborate on this choice?\n\nMinor:\n1. Is the phrase ``$\\alpha$-dominated graident\" very common in the literature? I more commonly have seen it referred to as the Polyak-Lojasiewicz (PL) Condition, and I might suggest that nomenclature.\n2. Why is the constraint $\\alpha \\leq 1$ needed? Most common in the literature is to simply assume $0 \\leq \\alpha \\leq L$.\n3. Although they are defined in the notation section, are big O and big Theta ever actually used in the paper? I could not find them. (And in fact, I really appreciate how your bounds are explicit!)\n4. I think $HF_{\\eta}(x, y)$ is first used in Algorithm 1 and needs a proper definition before that.\n5. Why does Theorem 1 need $L$-smoothness but Theorem 2 as well as results for the exact traditional gradient flow do not?", "limitations": "yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 4, "originality": 4, "strengths_and_weaknesses": "Strengths:\n1. In my view this is a high-quality submission. The results are technically sound and seem mature. Although I did not read the appendix in detail, the claims are well supported by extensive proofs. The paper is also written well, well organized, and clearly articulates the main ideas and results.\n2. To my knowledge the results of this paper and quite significant and interesting. The most similar previous results are Wang [2024], who use Chebyshev polynomials to set the reset times, and achieve results only on strongly convex quadratic functions. This paper presents a significant leap forward, with a new idea of randomized reset times, and results that hold across a much wider class of problems -- problems where the PL condition holds and weakly convex problems. Furthermore, the results significantly strengthen the connections between sampling and optimization, both of which are core topics in machine learning.\n3. To the best of my knowledge, there are no overlapping works in the literature and this work appears to present original new insights, which I think will be valuable.\n\nWeaknesses:\n1. My reading of this paper is quite positive and I don't have many strong weaknesses. However I will mention that I would appreciate if the authors could provide more insight/intuition on *why* the idea of randomized reset/integration times following a Poisson process actually leads to acceleration. I understand the \"real\" details are in the proof, but to strengthen the impact of this work some further intuition in the main body (which I could not find) would be quite helpful.\n2. I furthermore have several questions below, which I don't inherently view as weaknesses per se, but I would appreciate to see addressed.", "was_revised": true, "final_justification": "The authors' response was primarily to questions that I had and my score/evaluation of the paper was already positive (5). Based on their response and my assessment of the other reviews, I maintain my score.", "rebuttal": "We truly appreciate the reviewer’s insightful and encouraging comments. Below we provide our responses to the questions raised.\n\n**1. Alternative scheme for simulating the Poisson process**\n\nThank you for the interesting suggestion. Indeed, pre-sampling the Poisson process trace and then simulating the dynamics within each interval is a valid and intriguing alternative. While our current method uses an accept-refresh approach that tightly couples refresh times with the dynamics, exploring pre-sampled refresh traces as a potential alternative is an interesting direction, and we would be excited to investigate it in future work.\n\n**2. Is explicit Euler not stable here? Can you elaborate?**\n\nTheoretically, using the explicit Euler scheme to discretize our flow does not yield accelerated convergence rates. This is consistent with prior work:  [1] shows that when the Euler method is applied to discretize high-resolution ODEs for acceleration, the resulting algorithm fails to exhibit acceleration. The key reason is that the stepsize must scale with the strong convexity constant, which limits the convergence rate and prevents acceleration. In contrast, more carefully designed discretization schemes such as symplectic or implicit integrators can better preserve the geometric structure of the flow and support accelerated behavior.\n\n[1] Shi, Bin, et al. \"Acceleration via symplectic discretization of high-resolution differential equations.\" Advances in Neural Information Processing Systems 32 (2019).\n\n**3. Rough high probability bound by Markov’s inequality**\n\nYou’re absolutely right. While Markov’s inequality can technically yield a high-probability bound from expectation, such bounds are loose and not meaningful without additional assumptions. We’ve revised the text to clarify that stronger concentration requires light-tail or boundedness assumptions, which are beyond the scope of this work.\n\n**4. $x^*=0$ for the quadratic minimization experiments**\n\nThank you for pointing this out. We chose $x^*=0$ for simplicity, as one can always shift a quadratic function to have its minimizer at the origin without loss of generality. This normalization simplifies the presentation and does not affect the dynamics or convergence behavior of the algorithms.\n\n\n**5. Intuition on why randomization leads to acceleration**\n\nAs we show in Theorem 1, the short-time integration only recovers the same non-accelerated convergence rates as GD, which implies that the short-time integration doesn't efficiently decrease the function value, and we need potentially longer integration time. Another intuition comes from sampling, namely there is a conjecture that Hamiltonian Monte Carlo with randomized integration time can achieve accelerated mixing time for sampling. This has been shown in the idealized continuous-time setting in [Lu and Wang, 2022], and discussed in further details in [Jiang, 2023]. Our work can be seen as an optimization analogue of this question, and we show that randomized integration time does indeed lead to acceleration, both in continuous and discrete times.\n\n[Lu and Wang, “On explicit $L^2$-convergence rate estimate for piecewise deterministic Markov processes in MCMC algorithms’’, Annals of Applied Probability, 2022]\n\n[Jiang, \"On the dissipation of ideal Hamiltonian Monte Carlo sampler.\" Stat 12.1 (2023): e629.]\n\n**6. $\\alpha$-gradient domination vs PL inequality**\n\nThe condition we referred to as “$\\alpha$-dominated gradient” is indeed also known as the Polyak–Łojasiewicz (PL) condition, which is a more commonly used term in the optimization literature. We used the term “gradient dominated” following some prior works, but we agree that “PL condition” is more standard and widely recognized. We are happy to update the terminology in the revision to reflect this, and clarify the equivalence where appropriate.\n\n**7. Why assume $\\alpha \\leq 1$?**\n\nThank you for the observation. In our analysis (e.g., line 1445), we assume $\\alpha \\leq 1$ to simplify the expression involving step size $h$ and to ensure terms incorporating $\\alpha$ remain bounded. This assumption is natural in practice, as most real-world problems satisfy $\\alpha\\leq 1$, and it helps keep constants manageable. That said, the analysis can be extended to the general case $\\alpha \\leq L$ via rescaling. We will clarify this in the revision.\n\n**8. Where are big O and big Theta used?**\n\nWe used big O in the summary of contribution (line 79-line 87) and we used big Theta in related work discussion (line 1047).\n\n**9. The definition of $HF_{\\eta}$**\n\nWe defined $HF_{\\eta}$ in Section 2.1 (Notations and definitions, line 105). We will make this more prominent before Algorithm 1 in the revision to improve clarity.\n\n**10. Why does Theorem 1 need $L$-smoothness but Theorem 2 as well as results for the exact traditional gradient flow do not?**\n\nThe key to establishing Theorem 1 is  Lemma 6 in Appendix D, which is a stronger descent lemma and requires $L$-smoothness to bound the magnitude of velocity. Intuitively, HF-opt needs small integration time, which can be viewed as a discretization, and thus we need smoothness. In contrast, neither gradient flow nor randomized Hamiltonian flow needs small integration time and thus we don’t need smoothess in our analysis."}, {"review_id": "dAHqarssxJ", "reviewer": "Reviewer_ZMTX", "summary": "Let me start with a statement of (what I think is) the main result.\nThat is that there is an implementable approximation of Hamiltonian dynamics for convex optimization that has a provably accelerated convergence rate.\n\nNow for a summary. It is shown that an idealized version of Hamiltonian flow for convex optimization in discrete time achieves the convergence rate of gradient descent on the same class of functions when the step size (or integration time) is small. Inspired by the work of other authors, who have demonstrated that randomizing the integration time can speed up convergence, the authors show that a continuous-time limit of Hamiltonian flow with appropriately randomized integration times achieves accelerated convergence on convex functions. Presumably motivated by this continuous-time hint, the authors then go on to present a discretization of the continuous-time flow--that is, an implementable algorithm--and prove that the discrete-time dynamics achieves an accelerated convergence rate.", "questions": "**Experiments.**\nThere are a few things wrong with the experiments.\nOne problem is the range on the y-axes. In the most egregious example, the y-axis goes all the way down to $10^{-77}$, in another it goes to $10^{-23}$, and in many others it goes to $10^{-15}$.\nWhat bit precision is being used in the experiments?\nIn single precision, machine epsilon is merely $10^{-7}$. In double precision that improves to something like $10^{-15}$.\nValues of $f_k-f^{\\star}$ that are smaller than machine epsilon are not sensible. At that point it is not the performance of the algorithm so much as cancellation effects that are being measured.\nThis needs to be fixed.\nThe second problem is that many of the experiments don't actually show faster convergence for the accelerated algorithm. For convex or strongly convex functions with the strong convexity constant correctly specified, we should definitely see the accelerated algorithm converging faster on average than gradient descent. The story seems to be more complicated than that, in fact it looks in Figure 1 like the two types of algorithms are converging at the same rate. I'm wondering if there is something wrong with the code, or if perhaps the vast range of the y-axis is obscuring any differentials in behavior.\nBecause of these two problems, there is also a third problem, which is that the experiments as presented simply don't support the claim in the main text (see for example, the paragraph at line 280) that RHGD converges faster than GD.\n\n**Readability**. My other main issue with this paper has to do with readability, which I'm going to break into two pieces: lack of overall narrative, and other choices in the writing.\nWith what follows and the suggestions I make, my goal is simply to be helpful. My concerns regarding readability did not influence how I scored the paper. I am of the opinion that the quality of the written paper is not on par with the quality of the mathematical results, but I think this can be fixed without much trouble.\n\nNarrative. There isn't a narrative arc in this paper. In the summary, I wrote my impression of what I think the story might be. In the beginning of the paper the authors do a good job of identifying a gap in the literature---how to derive accelerated optimization algorithms from ideas in sampling---that serves as motivation for the main results. But after that the paper is mostly a list of theorem statements. Is the narrative I put in the summary what the authors had in mind (namely, that the fact that the continuous-time limit of randomized integration-time HMC turned out to have an accelerated rate motivated the search for a discretization that could preserve that rate)? If so, it would be worth slipping in a few sentences here and there that make it clear. This would be helpful to the reader in a paper with several algorithms and proofs of convergence. Speaking for myself, although they're cool, I'm just not sure what the place of the continuous-time results (Theorems 2 and 3) is if not to serve as motivation to search for Theorems 3 and 4.\n\nAlso along the lines of narrative, I wonder if the authors would consider promoting the discussion of lift-conserve-project schemes to the main paper? Descent lemmas are valuable in optimization. The observation that Hamiltonian dynamics gives a descent lemma for free is really nice. I think it would be worth putting that and the proof of the descent lemma in the main paper. One possibility would be to relegate some of the material in the experiments section to the appendices to make room.\n\nAnd while I'm talking about LCP schemes---the authors claim that this perspective is new. My question is, new to whom? If they mean the optimization/ML community then that is certainly plausible. But in physics the idea is folklore to the point where I don't think it even has a name. And I would be surprised if it wasn't also known in numerical analysis (but maybe it isn't!). Can the authors please clarify what they meant? Secondly, I think we should be careful not to imply (I think it's happening accidentally) that we can obtain a descent lemma for absolutely any $f$. For Hamilton's equations to be well-defined I believe we need $f$ to be differentiable at the very least.\n\nMore about the writing.\nNone of the math in this paper was new to me but it was still a difficult read. I think that part of the reason why is that the paper is absolutely teeming with acronyms. This really slows a reader down (for example, I got totally lost trying to keep RHMC, RHF, RHF-opt, RPHD, and RHGD straight). I think it would be worth dropping some of the acronyms, reserving them perhaps only for implementable algorithms such as GD and RHGD. There is a similar problem with excessive use of lemmas for well-known results such as Young's inequality. A sentence in a proof that reads ``we go from step A to step B via an application of Young's inequality'' is much faster to read than ''we go from step A to step B via Lemma 16'' and then I must flip several pages to check the statement of Lemma 16.\n\nApart from that, there are specific sentences and paragraphs that could use some rewriting for clarity. For example, no convergence result is provided for Algorithm 2 (and that's fine), but then the sentence in line 154 should be edited. Another example are the two paragraphs that begin at lines 176 and 185, respectively. We can't directly compare rates of a discrete-time dynamics with a continuous-time dynamics (like HF-opt and RHF in line 176).\n\n**Questions.**\nHF-opt is not an implementable algorithm. But having used an approximation of the Prox operator to approximate the Hamiltonian flow in the construction of RHGD, do the authors know what might happen if they did the same thing in HF-opt? Would the convergence rates of Theorem 1 be preserved?\n\nI was surprised by the discussion following the statements of Theorems 2 and 3, specifically the bit about smoothness. And are we sure that smoothness is really needed to prove a convergence rate for HF-opt? The relevant descent lemma does not require it. Could the authors please clarify what they are trying to say there?\n\n**One last thing.** Markov's inequality is quite simple to state and apply. It may be worth doing so in the paper to quantify deviations from the expected convergence rate of RHGD since the possibility of doing so is mentioned twice anyway.", "limitations": "Yes.", "rating": 5, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "The mathematical results of this paper are interesting, original, and relevant, and deserve to be published. The experiments need some work (they are not properly implemented or interpreted) and the whole paper could do with some rewriting here and there for clarity. I'll expand on these two points in the next section. Here, let me just say that the reason for my tepid score are the issues with the experiments. If the authors fix the experiments and the associated discussion in the experiments section, I am happy to raise my score to a firm accept.", "was_revised": true, "final_justification": "This is mainly a theory paper. The theorems look solid and are relevant to the community. I had some concerns regarding the clarity of the exposition and a number of issues with the experiments, but the authors seem to have understood my concerns and are addressing them. I am raising my score to an accept.", "rebuttal": "We thank the reviewer for the detailed and constructive feedback. Our responses to the questions and concerns are provided below.\n\n**1. Issues on the experiment**\n\nRegarding the y-axis scale, we agree that values below numerical precision are less meaningful. We re-ran the experiment with y-axis truncation at $10^{-14}$ to reflect numerical precision limits, and as the reviewer suggested, the acceleration of RHGD over GD became more evident. This confirms that the original plots already demonstrate accelerated convergence before reaching $10^{-14}$, particularly in the later stages of optimization. We will incorporate this change in the revised version by truncating the y-axis appropriately to improve visual clarity. Finally, we note that in better-conditioned settings, the advantage of RHGD over GD is more visible even in the early iterations (see Figure 3 in Appendix H.1). \n\n**2. Issue on readability**\n\nWe sincerely appreciate the reviewer’s thoughtful and generous feedback regarding the narrative and presentation. \n\nYour interpretation is essentially correct. More precisely, our motivation stemmed from the observation that the randomized HMC exhibits acceleration for Gaussian sampling, and this inspired us to search for an optimization analogue that could preserve similar accelerated behavior to bridge the gap between optimization and sampling. We will revise the introduction and technical sections to make this narrative more explicit and to help guide the reader through the progression of results.\n\nWe also appreciate the suggestion to promote the discussion of lift-conserve-project (LCP) schemes and the associated descent lemma to the main body. We agree that this is a compelling and intuitive idea, and we will move that discussion (including the proof) into the main text. To make space, we are happy to shift some experimental details to the appendix as suggested.\n\nWe fully agree that the lift-conserve-project (LCP) idea is well known in physics, and possibly in numerical analysis as well. Our claim of novelty is intended relative to the optimization and machine learning communities, where this perspective is, to our knowledge, not widely recognized or explicitly used in algorithm design. One of our goals is to make this viewpoint explicit and show how it leads to useful guarantees. Even within the MCMC literature, while HMC is often motivated by physical principles (e.g., symplecticity), the LCP interpretation offers a clean and concrete explanation for its behavior that is not always emphasized. We also agree that a descent lemma requires regularity in $f$, and we will clarify that differentiability is assumed.\n\nWe agree that the excessive use of acronyms may hinder readability, and we will revise the paper to reduce or eliminate non-essential acronyms, keeping them only for key algorithms like GD and RHGD. We also agree that referencing standard results like Young’s inequality through numbered lemmas is unnecessarily indirect. In the revision, we will inline such standard tools where appropriate to improve the flow of proofs.\n\n**3. No convergence result is provided for Algorithm 2**\n\nWhile we do not provide a direct convergence result for Algorithm 2 as written, we note that it involves exact simulation of Hamiltonian flow and is therefore a piecewise continuous-time process. To enable analysis, we equivalently reformulate it as the RHF process (a combination of Hamiltonian flow and a Poisson clock) and provide convergence guarantees for it in Theorems 2 and 3.\n\n**4. Do the authors know what might happen if they did the same thing in HF-opt? Would the convergence rates of Theorem 1 be preserved?**\n\nIf we use the implicit integrator with Prox approximation to discretize HF-opt, we will get gradient descent (similar to the leapfrog integrator shown in Appendix D.2) and then preserve the same convergence rates of Theorem 1. We will include this scheme explicitly in the appendix in the revised version.\n\n**5. And are we sure that smoothness is really needed to prove a convergence rate for HF-opt? The relevant descent lemma does not require it. Could the authors please clarify what they are trying to say there?”**\n\nWhile Lemma 2 provides an initial descent property, it is not sufficient to establish the convergence rates of HF-opt. For that, we rely on a stronger descent lemma (Lemma 6 in Appendix D), which does require smoothness. We will clarify this point in the revised version.\n\n**6. Markov's inequality is quite simple to state and apply. It may be worth doing so in the paper to quantify deviations from the expected convergence rate of RHGD since the possibility of doing so is mentioned twice anyway.**\n\nWe appreciate the reviewer’s observation. We agree that Markov’s inequality yields loose bounds, and our intention was not to claim tightness, but to demonstrate that the convergence in expectation can be converted into a high-probability guarantee without additional assumptions, which is consistent with some prior works, e.g., [1] and [2]. Given the randomized velocity refresh in our algorithm, stronger concentration results would require assumptions such as bounded variance or martingale structure. To keep the analysis general and assumption-free, we opted for the Markov-based bound. We agree that deriving tighter bounds under additional structure is an interesting direction for future work and will clarify this in the revision. \n\n[1] Mathieu Even, et al. \"Continuized accelerations of deterministic and stochastic gradient descents, and of gossip algorithms.\" NeurIPS 2021.\n\n[2] Jun-Kun Wang, and Andre Wibisono. \"Continuized Acceleration for Quasar Convex Functions in Non-Convex Optimization.\" ICLR 2023."}]

Author rebuttal:

Meta-review: This paper studies Hamiltonian flow approaches to optimization, rather than to sampling, where the approach has been more popular. In particular, the paper shows that a randomized Hamiltonian flow achieves an accelerated rate in expected optimization error for both the strongly convex and weakly convex cases. It then shows that a discretized version also achieves accelerated rates with an additional smoothness assumption, which is standard in convex optimization.

The approach is interesting, given the surprising fact that very few existing works study Hamiltonian flow for optimization. Among these, this paper appears to be the most satisfactory, providing new instances of accelerated first-order convex optimization algorithms (albeit in terms of expected optimization error). Moreover, Appendix B establishes a correspondence between sampling and optimization. I believe this work makes a fundamental contribution to convex optimization theory.

All reviewers are positive toward this paper. Reviewer QLTJ gave the lowest score of 4, noting that the proposed algorithm is slower than AGD in practice. Nevertheless, I believe the theoretical contribution is already sufficient, and the reviewer also explicitly stated that they agreed with accepting this paper. Reviewer KAWd was initially confused by the correspondence between optimization and sampling, but raised their score after the confusion was resolved during the author–reviewer discussion period.

Given the above, I recommend accepting this paper as a spotlight. I would not mind if my recommendation were bumped up.
Decision: Accept (spotlight)