Pith. sign in

REVIEW 3 major objections 4 minor 36 references

High-Order Langevin Diffusion Yields an Accelerated MCMC Algorithm

T0 review · 3 major / 4 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read The paper proves that a third-order Langevin MCMC algorithm samples strongly log-concave targets in $O(d^{1/4}/\varepsilon^{1/2})$ steps for ridge-separable potentials, the first rate below the $O(d^{1/3})$ barrier.

desk verdict Genuinely interesting third-order Langevin paper with a plausible d^{1/4}/eps^{1/2} rate for ridge-separable targets, but Theorem 2's Chebyshev interpolation step has a real pointwise-nonnegativity gap that needs repair. read the letter →

arxiv 1908.10859 v2 pith:SD475ZUJ submitted 2019-08-28 stat.ML cs.DScs.LGmath.OCstat.CO

Wenlong Mou , Yi-An Ma , Martin J. Wainwright , Peter L. Bartlett , Michael I. Jordan This is my paper · ORCID
classification stat.MLcs.DScs.LGmath.OCstat.CO MSC 60J2265C05
keywords MCMCthird-orderLangevindiffusionWasserstein-2distancemixingtimelog-concavesamplingridge-separablepotentialsChebyshevinterpolationhigh-ordersmoothness
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Sampling from a smooth, strongly log-concave density is usually limited by discretization error, with mixing times scaling at best as $O(d^{1/3})$ without extra assumptions. This paper argues that lifting the dynamics to a third-order Langevin system makes trajectories smooth enough that a carefully split integrator can do better, and it proves two mixing-time bounds. For potentials with ridge-separable structure, covering Bayesian logistic regression and one-layer neural networks, the bound is $O(d^{1/4}/\varepsilon^{1/2})$ in Wasserstein-2 distance, with no incoherence or high-order smoothness assumptions. For general potentials accessed through a black-box gradient oracle, the bound becomes $O(d^{1/4}/\varepsilon^{1/2}+d^{1/2}/\varepsilon^{1/(\alpha-1)})$ under $\alpha$-th order smoothness. If these proofs are right, this is the first result below the $O(d^{1/3})$ barrier for log-concave sampling in the general setting.

What carries the argument

The load-bearing object is a third-order Langevin system, obtained from the general complete-recipe form $dx_t=(D+Q)\nabla H(x_t)dt+\sqrt{2D}\,dB_t$ by setting $x=(\theta,p,r)$, $H=U(\theta)+\frac{L}{2}\|p\|^2+\frac{L}{2}\|r\|^2$, $D=\frac{1}{L}\operatorname{diag}(0,0,\xi I)$, and $Q$ a skew-symmetric matrix coupling $\theta,p,r$ through a parameter $\gamma$. This lifts the problem to $3d$ dimensions; the Brownian motion and $\nabla U$ enter through different variables, so each step of the algorithm reduces to integrating a deterministic function along a straight line. The argument then carries two pieces: a synchronous-coupling proof with an explicit Lyapunov matrix $S$ gives exponential contraction at rate $1/(5\kappa^2+50)$, and a three-stage splitting scheme controls the one-step discretization error through a recursion whose dominant term is $O(\kappa^8\eta^5 d/L)$. For ridge-separable potentials the straight-line integral is exact, eliminating the approximation term in the error recursion; for general potentials it is approximated by Lagrange interpolation at Chebyshev nodes, giving the $\varepsilon^{-1/(\alpha-1)}$ term.

What would settle it

Compute, with rigorous interval arithmetic, the largest eigenvalue of $SM_t+M_t^T S$ for the explicit $S$ and for Hessians at the extremes $mI$ and $LI$ over a fine grid of condition numbers $\kappa\in[1,10^3]$; exhibit any $\kappa$ where it exceeds $-1/5$, or check the sign conditions of Lemma 5 at $x=4/(5\kappa^6)$ and $x=4/\kappa^3+40/\kappa^5$. A single violation would disprove the exponential contraction in Proposition 1 and, with it, Theorems 1 and 2.

Watch

Extended reading notes

Core claim

The central discovery is that a third-order discretized Langevin algorithm samples from a strongly convex $L$-smooth target to Wasserstein-2 accuracy $\varepsilon$ in $O(d^{1/4}/\varepsilon^{1/2})$ iterations when the potential has the form $U(\theta)=\sum_i u_i(a_i^T\theta)$, and in $O(d^{1/4}/\varepsilon^{1/2}+d^{1/2}/\varepsilon^{1/(\alpha-1)})$ iterations when $U$ is $\alpha$-th order smooth and only gradients are available. The third-order dynamics introduce a momentum-like pair $(p,r)$ so that the gradient $\nabla U$ enters only through an integral of $\nabla U$ along a straight line; for ridge-separable potentials this integral is computed in closed form by the Newton-Leibniz formula, and for general potentials by Chebyshev-based Lagrange interpolation. The continuous-time dynamics are shown to contract exponentially in a weighted norm defined by an explicit Lyapunov matrix $S$, and the discretization error incurred per step is controlled by a three-stage splitting argument. The theorems absorb condition-number factors and require knowledge of $\kappa$ and $L$ to set the stepsize.

Load-bearing premise

The load-bearing premise, if it gives way, collapses the central claim: the explicit Lyapunov matrix $S$ satisfies the spectral bounds that all eigenvalues of $SM_t+M_t^T S$ are at most $-1/5$ and all eigenvalues of $S$ lie in $[1/(5\kappa),\kappa^2+10]$, and these bounds are verified only by handwritten algebra rather than machine-checked.

Editorial extensions

If this is right

  • For Bayesian generalized linear models and one-layer neural networks, posterior sampling to Wasserstein-2 accuracy $\varepsilon$ takes $O(d^{1/4}/\varepsilon^{1/2})$ iterations, improving on the $O(d^{1/3}/\varepsilon^{2/3})$ randomized-midpoint rate whenever $\varepsilon$ is small.
  • The $\varepsilon$-dependence of the black-box algorithm improves automatically with smoothness: $\alpha$-th order smoothness gives $\varepsilon^{-1/(\alpha-1)}$ instead of $\varepsilon^{-1}$, so high-resolution posterior computations benefit more.
  • The algorithm's per-iteration cost is one gradient evaluation for ridge-separable potentials and $\alpha$ gradient evaluations under black-box access, so the iteration bounds translate to runtime bounds when $\alpha$ is treated as constant.
  • No incoherence conditions on the data vectors and no higher-order smoothness on the component functions are needed for the $d^{1/4}$ rate, so the result applies to arbitrary design matrices in logistic regression.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The success of the third-order lift suggests a hierarchy: higher-order lifts with more auxiliary variables may push the dimension exponent below $1/4$, at the cost of worse condition-number dependence; the paper itself conjectures this trade-off.
  • A testable extension is to apply the exact straight-line integration to any potential whose functional form admits a closed-form path integral, not just ridge-separable sums; Theorem 1 would transfer to any such potential.
  • Because the Chebyshev interpolation error is controlled by $\alpha$-th derivatives, the method should be especially competitive in regimes where the target is very smooth and high accuracy is requested, an empirical prediction one could check on Gaussian-process posteriors.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 4 minor

Summary. The paper proposes a third-order Langevin diffusion and a discretized sampling algorithm (Algorithm 1) for strongly convex and L-smooth log-concave targets. It claims two main results: (Theorem 1) for ridge-separable potentials, a Wasserstein-2 mixing time of O(kappa^{19/4} (d/L)^{1/4} epsilon^{-1/2} log(d kappa / epsilon)) under only strong convexity and Lipschitz smoothness; and (Theorem 2) for general potentials with alpha-th order smoothness and black-box gradient access, a mixing time of O(L_alpha kappa^6 sqrt(d/L) epsilon^{-1/(alpha-1)} + kappa^{19/4}(d/L)^{1/4} epsilon^{-1/2}). The continuous-time part constructs an explicit Lyapunov matrix S and reduces exponential contraction to univariate eigenvalue inequalities; the discrete-time part uses a three-stage splitting that reduces the one-step error to the quality of a gradient approximation along a straight-line integral.

Significance. If Theorem 1 is correct, it is a significant contribution: it would be the first sampling bound below the O(d^{1/3}) barrier for strongly convex Lipschitz-smooth targets without incoherence or higher-order smoothness assumptions, at least for the ridge-separable class. The paper is unusually concrete: the continuous-time contraction proof is written out in detail, the Lyapunov matrix is explicit, and the algebraic reductions are stated as lemmas. The discrete-time error analysis is modular through Proposition 2, and the ridge-separable theorem does not rely on the questionable interpolation argument. However, the proof of Theorem 2 contains serious gaps, detailed below, so the advertised general-smoothness acceleration is not established by the current argument. The paper also provides reproducible-style explicit constants in Appendix C, which is a strength.

major comments (3)
  1. [Section 4.2.3, Proposition 2, Lemma 9] The sentence 'the weights in Lagrangian interpolation at Chebyshev nodes are non-negative' is false. For the Chebyshev nodes of Section 3.3 with alpha = 3, after rescaling to [0,1] the nodes are t1 = (1 + sqrt(3)/2)/2, t2 = 1/2, t3 = (1 - sqrt(3)/2)/2, and the middle Lagrange basis function satisfies ell_2(1) = -1/3. Since Proposition 2 (Eq. (22a)) and Lemma 9 both require the pointwise condition that \hat g_t(theta1,theta2) belongs to the convex hull of {\nabla U(lambda theta1 + (1-lambda) theta2)}, the interpolated \hat g_t does not satisfy this condition. If 'weights' instead refers to quadrature weights, their nonnegativity only justifies the integrated update, not the pointwise pathwise estimates. The proof of Theorem 2 is therefore incomplete as written.
  2. [Section 4.2.3, Lemma 6] Lemma 6 states an interpolation error of order ell^alpha sup ||d^alpha x_t / dt^alpha|| for a degree-(alpha-1) polynomial at alpha Chebyshev nodes. When this is applied to x_t = \nabla U(theta + t p), the alpha-th derivative is \nabla^{alpha+1} U (theta + t p) p^{otimes alpha}, for which Assumption 2 provides no bound; Assumption 2 bounds only \nabla^alpha U. The proof instead bounds d^{alpha-1} \nabla U / ds^{alpha-1}, which is one order lower and is not the statement of Lemma 6. This leaves the estimate of Delta_k(g) in the proof of Theorem 2 unjustified.
  3. [Section 4.2.3, Eq. (12a) and displayed recursion] The displayed recursion term 'eta (C eta L_alpha kappa^3 sqrt(d) + 2alpha/L)^{2(alpha-1)}' does not balance to the stated stepsize condition. From the preceding bound Delta_k(g) <= eta^{alpha-1} L_alpha^{alpha-1} ||p||^{alpha-1}, Lemma 9 gives E Delta_k(g)^2 <= (eta L_alpha)^{2(alpha-1)} (C kappa^3 sqrt(d) + 2alpha/L)^{2(alpha-1)}. Inserted into Proposition 2, the corresponding error contribution is O(eta^{1 + 2(alpha-1)}) = O(eta^{2alpha-1}). Requiring this term to be at most epsilon yields eta ~ epsilon^{1/(2alpha-1)} (up to d, kappa, L_alpha), not eta ~ epsilon^{-1/(alpha-1)} as claimed in Eq. (12a). In addition, the second term '2alpha/L' inside the parentheses appears to be missing a factor eta L_alpha. Thus the stepsize condition in the theorem does not follow from the displayed inequality.
minor comments (4)
  1. [Theorem 2 and Assumption 2] Theorem 2 states 'for some alpha >= 2', while Assumption 2 in Section 3.3 states 'for some alpha >= 3'; these should be reconciled.
  2. [Lemma 3 and Eq. (21)] The characteristic polynomial for the eigenvalues of S in Eq. (21), and the eigenvalue expressions used in Lemma 2, are asserted without derivation; providing the algebraic derivation or a symbolic verification would increase confidence in the continuous-time contraction rate.
  3. [Sections 3.3 and 4.2.3] The terminology for Chebyshev nodes is inconsistent: Section 3.3 uses alpha Chebyshev nodes, while Section 4.2.3 refers to '(alpha-1)-th order Chebyshev nodes'; the number of nodes and the degree of the interpolation polynomial should be stated consistently.
  4. [Throughout] Minor typographical issues: 'Lagrangian interpolation' should be 'Lagrange interpolation', 'close-form' should be 'closed form', 'Cauchy-Schwartz' should be 'Cauchy-Schwarz', and the phrase 'we apply utilize this dynamics' in the Discussion is ungrammatical.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the mixing-time derivations are self-contained, and the Chebyshev-weight concern is a correctness gap, not a circular reduction.

full rationale

The derivation chain is self-contained relative to its stated assumptions. The invariant distribution of the lifted (D+Q)∇H SDE is taken from the cited recipe [19,21], but that fact (p* ∝ e^{-H}) is a standard, directly checkable property of the generator and does not assert anything about mixing times or the d^{1/4} rate; the paper's novel content is the specific Lyapunov matrix S in equation (16b), the algebraic eigenvalue verification in Lemmas 2 through 5, and the splitting discretization in Section 3.4. The continuous-time contraction in Proposition 1 follows from the explicit Lyapunov matrix S rather than being assumed or fitted. The discrete-time one-step bound in Proposition 2 is obtained by synchronous coupling and direct estimation of the error terms I1, I2, and I3; the error terms are bounded using moment estimates from Lemma 9, which are themselves derived from the same contraction inequality, not from the target Wasserstein accuracy. For the ridge-separable case in Theorem 1, ΔU is set to the exact Newton-Leibniz integral, so Δ_k(g)=0, and the rate is obtained by balancing η^5 d against the contraction term; no parameter is fitted to the target measure, and no conclusion is used as an input. The Chebyshev-weight concern in Section 4.2.3 is a correctness or proof gap about pointwise nonnegativity of Lagrange basis functions, not a circular reduction; Theorem 2's claimed rate is not presupposed by its proof. The self-citations to the authors' earlier work are contextual or provide independent general facts, and none of them is a uniqueness theorem invoked to forbid alternatives. Hence no significant circularity is present.

Assumptions & free parameters 3 free parameters · 6 assumptions · 0 invented entities

The central claim rests on Assumptions 1 and 2, on a standard invariant-measure fact from the SDE literature, and on several technical interpolation assumptions that are asserted rather than fully derived. No new physical entities are introduced; the three-component lifted process is a mathematical construction, not an independently testable entity.

free parameters (3)
  • gamma (friction in third-order dynamics) = kappa
    Chosen by hand as kappa in all analysis; the contraction rate and the Lyapunov matrix are built around this choice.
  • xi (damping in third-order dynamics) = 2*kappa
    Chosen by hand as 2*kappa in all analysis; no derivation or robustness check is given.
  • stepsize eta = c*kappa^(-11/4)*d^(-1/4)*L^(1/4)*epsilon^(1/2) for Theorem 1; a min of two terms for Theorem 2
    The claimed rate depends critically on this scaling; the universal constant c is not specified, and the analysis assumes kappa and L are known.
assumptions (6)
  • domain assumption U is m-strongly convex and L-smooth (Assumption 1).
    Needed for the Hessian bounds mI<=H<=LI used in all contraction lemmas and moment bounds.
  • domain assumption U is alpha-times differentiable with tensor norm bound on grad^alpha U (Assumption 2).
    Used only in Theorem 2 to control Chebyshev interpolation error.
  • standard math The SDE (7) with matrices D and Q has invariant measure exp(-H).
    Invoked via references [19,21] to justify that the third-order dynamics target the desired distribution; standard but not proved in the paper.
  • ad hoc to paper Lagrange interpolation at Chebyshev nodes has nonnegative weights.
    Asserted in the proof of Theorem 2 without proof; generally false for Lagrange basis functions of degree at least two, and needed to place the interpolated gradient in the convex hull assumed by Proposition 2.
  • ad hoc to paper The scalar Chebyshev interpolation error bound (Lemma 6) extends to vector-valued functions with the same sup-norm factor.
    Used to bound the Euclidean norm of the interpolation error for the vector-valued path grad U; the paper cites standard scalar interpolation but does not derive the vector-valued version.
  • ad hoc to paper The approximator ghat_t belongs to conv({grad U(lambda*theta1+(1-lambda)*theta2)}).
    Assumed in Proposition 2. It holds for the exact ridge-separable choice, but for the Chebyshev approximator it depends on the nonnegative-weights claim.

how reviews work

0 comments
Cite this review

Pith. "Pith review of High-Order Langevin Diffusion Yields an Accelerated MCMC Algorithm." pith.science (2026). https://pith.science/paper/SD475ZUJ

@misc{pith2026190810859,
  author       = {Pith},
  title        = {Pith review of: High-Order Langevin Diffusion Yields an Accelerated MCMC Algorithm},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/SD475ZUJ}},
  note         = {Machine review of arXiv:1908.10859}
}
abstract

We propose a Markov chain Monte Carlo (MCMC) algorithm based on third-order Langevin dynamics for sampling from distributions with log-concave and smooth densities. The higher-order dynamics allow for more flexible discretization schemes, and we develop a specific method that combines splitting with more accurate integration. For a broad class of $d$-dimensional distributions arising from generalized linear models, we prove that the resulting third-order algorithm produces samples from a distribution that is at most $\varepsilon > 0$ in Wasserstein distance from the target distribution in $O\left(\frac{d^{1/4}}{ \varepsilon^{1/2}} \right)$ steps. This result requires only Lipschitz conditions on the gradient. For general strongly convex potentials with $\alpha$-th order smoothness, we prove that the mixing time scales as $O \left(\frac{d^{1/4}}{\varepsilon^{1/2}} + \frac{d^{1/2}}{\varepsilon^{1/(\alpha - 1)}} \right)$.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

36 extracted references · 31 canonical work pages

  1. [1]

    Abdulle, G

    A. Abdulle, G. Vilmart, and K. C. Zygalakis. Long time acc uracy of Lie-Trotter splitting methods for Langevin dynamics. SIAM J. Numer. Anal. , 53(1):1–16, 2015. (Cited on page 9.)

    work page 2015

  2. [2]

    Coupling and Convergence for Hamiltonian Monte Carlo

    N. Bou-Rabee, A. Eberle, and R. Zimmer. Coupling and conv ergence for Hamiltonian Monte Carlo. arXiv:1805.00452, 2018. (Cited on page 2.)

    work page Pith review arXiv 2018

  3. [3]

    A. A. Brown and M. C. Bartholomew-Biggs. Some effective met hods for unconstrained optimization based on the solution of systems of ordinary di fferential equations. J. Op- timiz. Theory App. , 62(2):211–224, 1989. (Cited on page 1.)

    work page 1989

  4. [4]

    Y. Cao, J. Lu, and L. Wang. Complexity of randomized algor ithms for underdamped langevin dynamics. arXiv preprint arXiv:2003.09906 , 2020. (Cited on page 2.)

    arXiv 2003

  5. [5]

    Chatterji, N

    N. Chatterji, N. Flammarion, Y.-A. Ma, P. Bartlett, and M . Jordan. On the theory of variance reduction for stochastic gradient Monte Carlo. In Proceedings of the 35th International Conference on Machine Learning (ICML) , volume 80, pages 764–773, 2018. (Cited on page 1.)

    work page 2018

  6. [6]

    Y. Chen, R. Dwivedi, M. J. Wainwright, and B. . Yu. Fast mix ing of Metropolized Hamil- tonian Monte Carlo: Benefits of multi-step gradients. Techn ical report, UC Berkeley, May

    work page

  7. [7]

    Cheng and P

    X. Cheng and P. L. Bartlett. Convergence of Langevin MCMC in KL-divergence. In Proceedings of the 29th International Conference on Algorith mic Learning Theory (ALT), pages 186–211, 2018. (Cited on page 1.)

    work page 2018

  8. [8]

    Cheng, N

    X. Cheng, N. S. Chatterji, Y. Abbasi-Yadkori, P. L. Bartl ett, and M. I. Jordan. Sharp convergence rates for Langevin dynamics in the nonconvex se tting. arXiv:1805.01648,

    arXiv

Show all 36 references
  1. [9]

    Cheng, N

    X. Cheng, N. S. Chatterji, P. L. Bartlett, and M. I. Jordan . Underdamped Langevin MCMC: A non-asymptotic analysis. In Proceedings of the 31st Conference on Learning Theory (COLT), pages 300–323, 2018. (Cited on pages 1, 2, and 5.) 18

    2018

  2. [10]

    A. S. Dalalyan. Theoretical guarantees for approximat e sampling from smooth and log- concave densities. J. Royal Stat. Soc. B , 79(3):651–676, 2017. (Cited on pages 1, 2, and 4.)

    2017

  3. [11]

    A. S. Dalalyan and A. G. Karagulyan. User-friendly guar antees for the Langevin Monte Carlo with inaccurate gradient. Stochastic Process. Appl. , 2019. (Cited on pages 1 and 2.)

    2019

  4. [12]

    A. S. Dalalyan and L. Riou-Durand. On sampling from a log -concave density using kinetic Langevin diffusions. arXiv:1807.09382, 2018. (Cited on page 2.)

    2018 arXiv

  5. [13]

    Durmus and E

    A. Durmus and E. Moulines. High-dimensional Bayesian i nference via the Unadjusted Langevin Algorithm. arXiv:1605.01559v4, 2018. (Cited on pages 1 and 2.)

    2018 arXiv

  6. [14]

    Dwivedi, Y

    R. Dwivedi, Y. Chen, M. J. Wainwright, and B. Yu. Log-con cave sampling: Metropolis- Hastings algorithms are fast! arXiv:1801.02309, 2018. (Cited on page 1.)

    2018 arXiv

  7. [15]

    M. Ledoux. The geometry of Markov diffusion generators. Ann Fac Sci Toulouse Math , 9(6):305–366, 2000. (Cited on page 4.)

    2000

  8. [16]

    Y.-T. Lee, Z. Song, and S. S. Vempala. Algorithmic theor y of ODEs and sampling from well-conditioned logconcave densities. arXiv:1812.0624 3, 2018. (Cited on pages 2, 3, and 7.)

    2018

  9. [17]

    Leimkuhler and X

    B. Leimkuhler and X. Shang. Adaptive thermostats for no isy gradient systems. SIAM J. Sci. Comput. , 38(2):A712–A736, 2016. (Cited on page 9.)

    2016

  10. [18]

    Y.-A. Ma, N. S. Chatterji, X. Cheng, N. Flammarion, P. L. Bartlett, and M. I. Jordan. Is there an analog of Nesterov acceleration for MCMC? arXiv: 1902.00996, 2019. (Cited on page 2.)

    1902 arXiv

  11. [19]

    Y.-A. Ma, T. Chen, and E. B. Fox. A complete recipe for sto chastic gradient MCMC. In Advances in Neural Information Processing Systems 28 (NIPS) , pages 2899–2907. 2015. (Cited on pages 5 and 11.)

    2015

  12. [20]

    Y.-A. Ma, Y. Chen, C. Jin, N. Flammarion, and M. I. Jordan . Sampling can be faster than optimization. arXiv:1811.08413, 2018. (Cited on page 1.)

    2018 arXiv

  13. [21]

    Y.-A. Ma, E. B. Fox, T. Chen, and L. Wu. Irreversible samp lers from jump and continuous Markov processes. Stat. Comput. , pages 1–26, 2018. (Cited on pages 5 and 11.)

    2018

  14. [22]

    Mangoubi and A

    O. Mangoubi and A. Smith. Rapid mixing of Hamiltonian Mo nte Carlo on strongly log-concave distributions. arXiv:1708.07114, 2017. (Cited on pages 2, 3, and 7.)

    2017 arXiv

  15. [23]

    Mangoubi and N

    O. Mangoubi and N. K. Vishnoi. Dimensionally tight runn ing time bounds for second- order Hamiltonian Monte Carlo. In Advances in Neural Information Processing Systems (NeurIPS) 32 , pages 6030–6040. 2018. (Cited on pages 2 and 3.)

    2018

  16. [24]

    R. M. Neal. MCMC using Hamiltonian dynamics. Handbook of Markov Chain Monte Carlo, 54:113–162, 2010. (Cited on page 4.)

    2010

  17. [25]

    Nesterov

    Y. Nesterov. Introductory Lectures on Convex Optimization: A Basic Course . Kluwer, Boston, 2004. (Cited on page 6.)

    2004

  18. [26]

    G. O. Roberts and J. S. Rosenthal. Optimal scaling for va rious Metropolis-Hastings algorithms. Statist. Sci. , 16(4):351–367, 2001. (Cited on page 1.) 19

    2001

  19. [27]

    Shen and Y

    R. Shen and Y. T. Lee. The randomized midpoint method for log-concave sampling. In Advances in Neural Information Processing Systems , pages 2098–2109, 2019. (Cited on pages 2 and 7.)

    2019

  20. [28]

    B. Shi, S. S. Du, M. I. Jordan, and W. J. Su. Understanding the acceleration phenomenon via high-resolution differential equations. arXiv preprint arXiv:1810.08907 , 2018. (Cited on page 1.)

    2018 arXiv

  21. [29]

    G. W. Stewart. Afternotes Goes to Graduate School: Lectures on Advanced Nu merical Analysis, volume 58. Siam, 1998. (Cited on page 16.)

    1998

  22. [30]

    Stoer and R

    J. Stoer and R. Bulirsch. Introduction to Numerical Analysis . Springer, New York, 3rd edition, 2002. (Cited on page 8.)

    2002

  23. [31]

    W. Su, S. Boyd, and E. Candes. A differential equation for m odeling Nesterov’s acceler- ated gradient method: Theory and insights. In Z. Ghahramani , M. Welling, C. Cortes, N. D. Lawrence, and K. Q. Weinberger, editors, Advances in Neural Information Pro- cessing Systems 27 , ...

    2014

  24. [32]

    C. Villani. Optimal Transport: Old and New . Wissenschaften. Springer, Berlin, 2009. (Cited on page 4.)

    2009

  25. [33]

    Wilson, B

    A. Wilson, B. Recht, and M. I. Jordan. A Lyapunov analysi s of momentum methods in optimization. arXiv:1611.02635, 2016. (Cited on page 1.) A Proof of Proposition 2 In this appendix, we prove Proposition 2, as previously stated in Section 4.2.1. Recall that this result provide...

    2016 arXiv

  26. [35]

    to the estimates for I1,I2 andI3, for η <min (1/γ, 1/ξ), we obtain: EI1(s) ≤Cκ 2η4L2 ( E ‖ ‖ ‖ ˜θkη −θ∗ ‖ ‖ ‖ 2 2 + E ‖˜pkη‖2 2 + E ‖˜rkη‖2 2 +d/L ) + 2E∆ k(g)2, EI2(s) ≤Cκ 4η4 ( E ‖ ‖ ‖ ˜θkη −θ∗ ‖ ‖ ‖ 2 2 + E ‖˜pkη‖2 2 + E ‖˜rkη‖2 2 +d/L ) , EI3(s) ≤ η4 L2 E sup kη≤s≤(k+1)η ‖...

  27. [36]

    A.5.3 Proof of Lemma 9 For notational convenience, we assume θ∗ = 0 in the proof of this lemma

    Consequently, sup kη≤s≤(k+1)η E ‖˜rs‖2 2 ≤ 30 ( E ‖ ‖ ‖ ˜θkη −θ∗ ‖ ‖ ‖ 2 2 + E ‖˜pkη‖2 2 + E ‖˜rkη‖2 2 +d/L ) , which completes the proof. A.5.3 Proof of Lemma 9 For notational convenience, we assume θ∗ = 0 in the proof of this lemma. This assumption can be made without loss o...

  28. [2019]

    (Cited on page 4.)

    arXiv:1905.12247. (Cited on page 4.)

    1905 arXiv

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.