Venue: ICLR 2022 Conference

Reviews:

final_score: rating: null
review_content: I have not been able to reproduce Figure 1a. I would be very grateful if someone can confirm my result or correct my mistake.

---

### My attempt

1. Download code from Supplementary Material.
2. Go to folder `code/verifyDependenceOnStepSize`.
3. Run `mkdir results`.
4. Run `for j in {1..100}; do printf '%d\n' $j; done | parallel python verify_dependence_on_h_nonlinear_potential.py --seed {}`.
5. Extract result by a python script.

Cost:
Step 4 takes about 212 minutes for each process. Different processes can be paralleled, so the experiment can be reproduced within 4 hours with 128-Thread processor.

---

Step 5. Extract result by a python script
```
import os
import numpy as np

hs = sorted(list(set(f.split("|")[1].split("=")[1] for f in os.listdir("results"))))

means = [
    np.mean(
        [
            np.load(f"results/sample_mean|h={h}|d=2|n_samples=1000000|part={i}.npy")[-1]
            for i in range(1, 101)
        ],
        0,
    )
    for h in hs
]
groundtruth = -np.ones(2) / 2
errors = np.linalg.norm(means - groundtruth, axis=1)

fmt = "{:<10} {:<20}"
print(fmt.format("step size", "error of mean"))
print(fmt.format("x-value", "y-value"))
for h, error in zip(hs, errors):
    print(fmt.format(h, error))

# plot
import matplotlib.pyplot as plt

plt.plot(np.array([float(h) for h in hs]), errors)
plt.xlabel("step size")
plt.ylabel("error of mean")
plt.xscale("log")
plt.yscale("log")
plt.show()
```

---
### Result
```
step size  error of mean
x-value    y-value
0.0078125  6.155751193279832e-05
0.015625   3.24395818680134e-05
0.03125    0.00012469951134488403
0.0625     0.00011271019977054319
0.125      0.00012402092738382037
0.25       0.00012676214501006623
0.5        0.00013291926615112697
1          0.0003001348227226792
2          6.805572349740432e-05
```

---
### Explain the method

Step 4 is due to authors' comment:

> Each run of the script gave one portion of data and then we aggregated and averaged the results to produce Fig 1a.

> we used `n_samples=int(1e6)` for each single job, but run the script with 100 different seeds. So altogether `1e8` independent samples are used.

I don't know seeds used by authors, thus I arbitrarily choose 1 to 100.

Explanation of script in step 5: 
Retrieve last column for each npy file, because that is for last iteration.
Calculate mean of these 100 points, because that is mean of total `1e8` samples.
Calculate the 2-norm difference to ground truth $[-0.5,-0.5]$, because that is "error of mean" reported as y-axis in Figure 1a.

---
### Explain the result

My plot is not even similar to Figure 1a, which has nice alignment with $O(h)$.

At small step size regime, my y-axis value is much larger than data in Figure 1a.
At large step size regime, my y-axis value is much smaller than data in Figure 1a.
In my result, there is not significant correlation between estimated "error of mean" and step size. However in Figure 1a, the experiment fit a power law precisely.
review_title: Discussion on Reproducibility Issue

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The paper proposes an accelerated MCMC method for sampling, motivated by Nesterov's Accelerated Gradient (NAG) method. Starting from the high resolution ODE of NAG obtained in Shi et al, the paper applies a two stage mechanism to remove the Hessian-dependency. The obtained first order ODE system serves as the backbone of the proposed diffusion process, Hessian-Free High-Resolution (HFHR) dynamics. Discretization the HFHR dynamics leads to the proposed sampling method. Theoretical convergence are provided for both the continuous and the discretized variant, showing acceleration to existing underdamped Langevin method (ULD). 
main_review: The paper is very technical and not easy to follow. The main contribution of the paper is to provide an accelerated first order diffusion process in continuous time, yielding a novel sampling method after discretization. I have a few questions/concerns to be clarified regarding the claims in the paper:

1 Acceleration in continuous time 
Comparing to the rate obtained in Dalalyan 2020, the proposed algorithm improves by a factor of $\kappa$. However, I am confused as no improvement is achieved for the function $f(x,y) = mx^2+Ly^2$, this seems contradictory to the claim, do I misunderstand anything? Is it related to the time scaling? 

2 Discretization 
When discretizing, the paper applies a second-order symmetric composition. What is the motivation behind this step? What would be the benefit compared to applying forward Euler discretization? 

3 Acceleration in discrete time 
Unless we show that the constant term is improved by a non-trivial factor (L, or $\kappa$ for example), I wouldn't call it an acceleration as those are only upper bounds in the analysis. 

4 ULD = HFHR(0,$\gamma$)
I understand that the continuous ODE are equivalent by taking $\alpha = 0$, is the discretized algorithm still follows the same equivalence? (for instance, different discretization method may be applied)

5 Comments on Experiments 
a. In figure 2, it seems surprising to me that only 2 iterations is enough to reach $\epsilon$ closeness, which may suggest the problem is too easy
b. In Figure 3, why does some figure only has $\alpha=0.1$ and the others has $\alpha = 0.1, 0.5, 1$

summary_of_the_review: Overall, I believe the theoretical result of the paper has merit but the presentation need to be improved
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: This paper introduces Hessian-Free High-Resolution SDE inspired by Accelerated Gradient (NAG). The author shows that continuous solution achieves an acceleration over the underdamped Langevin. A discrete algorithm also has speed-up with a constant factor.
main_review: This paper has solid theoretical analysis. 
However the author missed an important comparison with randomized midpoint method (Shen & Lee, 2019). 
I think the author proved an iteration complexity that is worse to the method in that paper. This invalidates author's claim on constant factor speed-up over underdamped Langevin dynamics.

Specific Comments:
1) In Assumption A1, $m \lVert y-x \rVert \leq \lVert \nabla f(y)-\nabla f(x) \rVert \leq L \lVert y-x \rVert$ seems insufficient to establish m-stronly-convex and L-smooth.

2) Does this paper consider "log-concave" case? In the introduction, author said " will consider the setup of log-concave / log-strongly- concave target distributions". However, it seems Assumption A1 require $m > 0$. 

3) On page 9, author wrote "(strongly) log-concave assumptions required in Theorem 5.2", why there is a bracket? Does it imply that Theorem 5.2 could be applied in log-concave case?

4) In Remark 5.5, at the last line, the author claimed "steps needed by ULD can be halved by HFHR". Which algorithm is the author referring to for "ULD". Is it algorithm in (Cheng et al. 2018) or HFHR with $\alpha=0$? It seems these two algorithms are actually different.

5) In section 6.1, author proposed to use error of mean as a surrogate of 2-Wasserstein distance. Although error of mean is a lower bound, how tight it is? In figure 2, the mean value at $\alpha=0.5$ in the Figure 2 seems close to 1, which means HFHR achieves $\varepsilon\leq0.1$ accuracy in just one iteration. Clearly one iteration is not enough for burn-in. Does it means error of mean is a bad indicator of mixing?

6) In figure 1, could the author also add lines for ULD and randomized midpoint method?
summary_of_the_review: I thinks this paper could be improved substantially, but currently would like to recommend reject.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This stuyd focused on developing a Hessian-free high-resolution Nesterov’s Acceleration approach which proves converging faster and being  non-trivial (not a time-rescaling trick).
main_review: This paper introduces a Hessian-free high-resolution Nesterov’s Acceleration approach which proves faster convergence than both Underdamped and Overdamped Langevin Dynamics. In addition, it also proves that the acceleration cannot be achieved by time-rescaling. Experiments results support the argument in optimization acceleration as well as the theoretical results. 

Some questions the reviewer minds:

-The theorem 5.1 depends on the assumption on \gamma and \alpha. If such an assumption often holds in real applications.

-It is will be better to demonstrate the acceleration superiority in with a more complex network and a large-scale dataset.
summary_of_the_review: The reviewer thinks this paper contributes a new and effective gradient based optimization solver. Overall, the reviewer would like to recommend acceptance.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The author proposed an accelerated-gradient-based MCMC method based on Nesterov's accelerated gradient (NAG). In continuous time, the algorithm is able to achieve a tremendous acceleration over the underdamped Langevin algorithm. Numerical schemes can propose a speed-up with a constant factor.

main_review: This paper builds a NAG-based MCMC sampler, which is named as Hessian-Free High-Resolution (HFHR($\alpha, \gamma$)) and generalizes the underdamped Langevin (also can be written as HFHR($0, \gamma$)) with an additional gradient drift and Brownian motion for the update of the position variable. 

**Pros**: The most prominent feature of the extended algorithm yields much faster exponential convergence with **rate $O(L)$**  in continuous time than the standard underdamped Langevin algorithm  **(Cheng'18, rate $O(\frac{m}{L})$, Dalalyan'20, rate $O(\frac{m}{\sqrt{L}})$)**. Although the acceleration becomes less significant in numerical algorithms due to an increase of discretization error, some speed-up by a constant factor can be still achieved.

**Cons**:  the writing is not very clear, which affects the readability experience and made me hard to check the details. For example 1) the derivation of Formula (6) is slightly ad-hoc and more related work or motivations are suggested; 2) at the end of section B, some link on the definitions of notations may be suggested; 3) page 24, $H_t$ is derived based on Taylor expansion instead of saying nothing is better for presenting to the readers.

Remark: Theorem 5.1 is checked carefully; Theorem 5.2 is not; the logic seems to be reasonable.

Minor issues: 

1. Experiments conducted on section 6.2 is non-convex and doesn't match the theory.

2. Missing part in related works: Replica-exchange (a.k.a parallel tempering): 

[1]. Accelerating Nonconvex Learning via Replica Exchange Langevin Diffusion. ICLR'19

[2]. Non-convex Learning via Replica Exchange Stochastic Gradient MCMC. ICML'20


Cheng'18: Underdamped Langevin MCMC: A non-asymptotic analysis. COLT'18.

Dalalyan'20: A. S. Dalalyan and L. Riou-Durand. On sampling from a log-concave density using kinetic Langevin diffusions. Bernoulli


summary_of_the_review: The NAG-based MCMC sampler extends the underdamped Langevin with a drift term and Brownian motion and is proved faster than the alternative. I would recommend this paper to be accepted.
review_title: null

final_score: rating: 1: strong reject
review_content: summary_of_the_paper:  This paper discuss the accelerated-gradient-based MCMC method and propose some rigorous proof.
main_review: I do not think the problem addressed by this paper does not make sense.  The gradient-based algorithm added by the noise in the convex case does not play the essentially different role with that without the noise.  
summary_of_the_review: Please the authors refer to 

Bin Shi, Weijie Su and Michael I. Jordan,  On Learning Rates and Schrödinger Operators, https://arxiv.org/abs/2004.06977

Bin Shi, On the Hyperparameters in Stochastic Gradient Descent with Momentum, https://arxiv.org/abs/2108.03947
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: This paper introduces a stochastic process called HFHR. The SDEs of HFHR is derived by rewriting Nesterov’s Accelerated Gradient (NAG) into phase-space representation, formulating it as ODEs, and then injecting noise into both position and momentum variables. HFHR can be used for sampling because it has stationary distribution as the target distribution. A discretization of HFHR is given by operator splitting and Euler integration. A mixing time bound of $\widetilde{O}(\sqrt{d}/\varepsilon)$ is obtained for sampling log-strong-concave-and-smooth target distribution with extra third-order growth condition.
main_review: Strengths:
The HFHR process seems novel and has interesting connections with NAG. The paper is mostly clear and easy to follow.

Weakness:
1. HFHR has noise injected into position directly

This property is actually harmful for discretization because directly coupling Brownian motion into $q_t$ makes the trajectory of $q_t$ extremely non smooth and make it hard to estimate $\nabla f(q_t)$.

The ULD avoid directly inject noise into position to achieve acceleration compared to the overdamped LD.
HFHR, unlike from ULD, has noise term $dW_t$ in position. However it still achieve same asymptotic convergence as certain discretized ULD at the price of an extra condition on higher order derivative.

2. Rely on additional third-order growth condition

Although this condition is weaker than Hessian Lipschitz and has been used in prior art to accelerate the convergence of LD [Li et al., 2021], it still makes the convergence guarantee weaker than many discretized ULD, which have same or better asymptotic convergence speed and don't require third-order growth condition.

3. The condition number $\kappa$ dependence and third-order growth constant $G$ dependence in iteration complexity is unclear

The main paper doesn't specify the asymptotic dependence of $\kappa$ and $G$ but hide it in the constant $C$. Including that information in the main paper would be appreciated.

According the appendix page 20, where C is defined, I guess that the $\kappa$ dependence is $O(\kappa^{3/2})$ and $G$ dependence is $O(G)$. Could the author help to verify the above statements?

4. Iteration complexity is worse than certain discretization of ULD

Although the authors cited [Shen & Lee, 2019], they didn't discuss methods in this paper at all.

The randomized midpoint method is a special discretization of ULD, which achieves $\widetilde{O}(d^{1/3}/\varepsilon^{2/3})$ iteration complexity and doesn't require third-order growth condition.

5. The method is not well motivated

According to the paper, HFHR is motivated by one question "how to appropriately inject noise to NAG algorithm in discrete time". We should note that, although there are underlying connections between optimization and sampling, injecting noise into a good optimization method doesn't necessarily yield a good sampling algorithm.
Unfortunately, this paper seems like this is the case. More specifically, discrete HFHR with $\alpha \neq 0$ have worse iteration complexity compared to certain discretization of ULD.

6. Points in Figure 2 is biased estimation

If I understand correctly, the y-axis value in Figure 2 is smallest number $k$ such that $\lVert \mathbb{E} {\mu_k} q-\mathbb{E} \mu q \rVert \leq \varepsilon$.
In order to estimate $\mathbb{E} {\mu_k} q$, $\frac{1}{n} \sum_i^{n} q_k^{(i)}$ is calculated for $n=1000$ samples (according to line 3 in generate_config.py) which are generated and run in parallel for $k$ iterations.

$\frac{1}{n} \sum_i^{n} q_k^{(i)}$ is indeed unbiased estimation of $\mathbb{E} {\mu_k} q$. However 
$\min k$ $s.t. \lVert \frac{1}{n} \sum_i^{n} q_k^{(i)}-\mathbb{E} \mu q \rVert \leq \varepsilon $
 is a biased estimation of 
$\min k$ $s.t. \lVert \mathbb{E} {\mu_k} q-\mathbb{E} \mu q \rVert \leq \varepsilon$.

Typo:

dt is missing in eq 6.
Bracket error on 3rd-to-last line on page 8. 
summary_of_the_review: The method is novel in the sense that it is derived based on the idea "inject noise into Nesterov’s Accelerated Gradient".
However the derived theory is not significant as it rely on extra assumptions and has worse iteration complexity.
review_title: null

Meta-review: The paper considers the high resolution continuous limit of Nesterov's Accelerated Gradient (NAG) algorithm and its connections to sampling (MCMC methods). The paper develops a Hessian-Free High Resolution (HFHR) ODE and injects noise into it to obtain an accelerated sampling algorithm. Further, the paper provides a discrete-time variant of the algorithm by appropriately discretizing HFHR using simple discretization schemes. For strongly log-concave potential functions (log-densities), the paper proves convergence of the order $\tilde{O}(\sqrt{d}/\epsilon)$ in Wasserstein-2 distance. In the asymptotic sense, the result matches the convergence of the underdamped Langevin algorithm; however, the paper argues that the constants in the proposed algorithm are smaller and empirically shows that the proposed algorithm is faster in practice. The main contributions of the paper are theoretical; however, the theoretical results are supplemented by numerical experiments.

Overall, the reviewers found the contributions interesting and the theoretical contributions of the paper technically sound. The main concerns that were not completely addressed were related to the presentation of the results and reproducibility of some of the numerical experiments. While both seem minor and possible to address, ultimately there was not enough support to recommend acceptance. However, the paper is solid and merits acceptance after suitable revisions. Thus, the authors are encouraged to revise the paper and resubmit it to one of the conferences in the equivalence class of ICLR.
Decision: Reject