Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The paper considers the possibility of accelerating Hamiltonian Monte Carlo (HMC) methods for sampling from distributions $\pi$. For a $L$-smooth and $m$-convex $f$, the complexity of sampling from $\pi \;\alpha\; e^{-f}$ (via an "ideal method" that does not discretize time) is of the order $\kappa \log(1/\delta)$, where $\delta$ is the desired precision and $\kappa={L/m}$ is the condition number. The present paper shows that one can lower the complexity of the ideal method by a factor of $\sqrt{\kappa}$ when $f$ is quadratic (and so $\pi$ is Gaussian). This requires knowledge of $L$ and $m$, which one uses to choose special step sizes defined via Chebyshev polynomials. Experiments suggest that the same choice of weights works beyond the case of quadratic $f$; in fact the method seems to "beat the competition" even for nonconvex likelihoods. 
strength_and_weaknesses: *Strengths*

- This seems to be the first acceleration result for HMC.  
- The use of Chebyshev polynomials is somewhat interesting.

*Weaknesses*

- Unfortunately, the theory does not cover any cases of practical interest.
- The experimental success metrics are all defined in terms of effective sample size (ESS). This is a useful proxy of MCMC quality, but it does not prove convergence, nor does it quantify this convergence in harder problems. It would be nice to see other metrics as in: can one approximate the integrals of some "interesting/hard functions" from the MC trajectories of different methods?
- In line with the previous remark, it'd be nice to look at some *hard* distributions coming from real-life Bayesian statistics. What do the credible regions look like? Does one reobtain known results at lower cost?


clarity,_quality,_novelty_and_reproducibility: The paper is quite clear. I did not ceck the experiments carefully, but the code is well-documented and "looks reproducible". The approach also seems novel in this context.

I do not think the paper is of great interest, given that the theory is severely limited, and the experiments do not provide a clear indication of practical aspects of this method. One issue I would like to see explored is this: if the likelihood is complicated, maybe it's hard to compute $\kappa$. What does one do in practice? Is the method sensitive to the upper bound $L$ and the lower bound $m$?
summary_of_the_review: The paper has a nice idea, but, at it is present form, its interest is too limited from both theoretical and practical perspectives. 

UPDATE on Nov 30th

I have increased my "novelty" and overall scores. I thank the authors for their responses. To comment on a few points. 

a) I agree ESS is a standard surrogate for convergence. It would be nice, however, to see a problem with eg. a multimodal likelihood and show (empirically) that accelerated HMC converges faster than the standard method. 

b) I understand that the above point is (as the authors say) disjoint from their goals, as it'd go beyong the logconcave setting. However, given the lack of theoretical results for general logconcave f, I think the paper would greatly benefit from a more extensive empirical evaluation of the accelerated method in more practical settings. 

c) I thank the authors for the clarifiction regarding sensibility to the smoothness ans strong convexity parameters.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper proposed a time-varying integration method for accelerating the mixing of Hamiltonian Monte Carlo. In particular, when the potential $f$ is quadratic function, i.e., the target distribution is Gaussian, the ideal HMC with the proposed time-varying integration enjoy a $O(\sqrt{\kappa}\log(1/\epsilon))$ iteration complexity in terms of Wasserstein-2 distance. The authors further develop a practical HMC algorithm using the proposed integration time. Experimental results show that the developed algorithm can also lead to better sampling performance for the general smooth and strongly convex potentials.
strength_and_weaknesses: Strength:

* this paper proposes a novel time-varying integration method for HMC and proves a faster convergence compared to the constant-time integration method.
* this paper incorporated the proposed integration into a practical HMC algorithm and demonstrate its better performance in experiments.

weakness:
* The theory is limited to quadratic cases, while prior works cover all smooth and strong convex cases.
* The explanation of the acceleration effect of Chebyshev integration time is not clear.
* The stepsize is not tuned for HMC with constant-time integration (as mentioned in Section 4, the stepsize for HMC with constant integration time is set by (5)).

Questions:
* What’s the role of $\bar \Phi_K(\lambda)$ in the algorithm or theory? Why can equation (11) illustrate the acceleration of the proposed Chebyshev integration time?
* The authors mention that the permutation $\sigma$ is not needed in the analysis, does it mean that Theorem 1 holds for any permutation?
* (5) is only one choice of constant integration time, can we find a better choice to gain faster convergence? 
* It would be better to compare the total integration time of the proposed method and baselines.
* Following the previous comment, can we fix the total integration time and directly optimize the integration time in each iteration according to Lemma 2?

clarity,_quality,_novelty_and_reproducibility: The clarity needs to be improved, more explanations regarding why Chebyshev integration time can lead to acceleration need to be added.

Novelty and originality are acceptable, no prior works have shown similar results.

summary_of_the_review: My major concern is (1) the limitation of theory (i.e., only for quadratic potential) and (2) lack of thorough discussion and exploration of baseline method (e.g., constant integration time) in terms of both theory and experiment.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper proposes a new time-varying integration duration for HMC using the roots of Chebyshev polynomials. 
In a very restrictive setting, they paper proves an upper bound on the number of iterations required to reach Wasserstrain-2 distance less than an a specified error threshold. This setting is where exact HMC mechanism is applicable (i.e. the equations of motion can be solved in closed form). This closed-form solution only exists for Gaussian distributions (as far as I know).
Nonetheless, experiments shows that their scheme has benefits in case the target distribution is not Gaussian but is associated with a smooth strongly convex potential energy function.
 
strength_and_weaknesses: The paper is well-written and the proofs seem correct. Though, I should highlight I did not check all the proof details closely. 
The newly found bound is interesting though the studied theoretical setting, namely exact HMC (i.e. where the equations of motion are solved in closed-form) is only applicable to Gaussians and therefore, it is quite restrictive because clearly, for sampling from Gaussians there exist better algorithms and HMC is not used. 
Nonetheless, this theoretical finding may open the way for future theoretical works that consider more general families of distributions. 
Also, the presented empirical results show that the proposed algorithm can outperform the baseline on models other than Gaussian. 
  
clarity,_quality,_novelty_and_reproducibility: The paper is clearly written. The quality of the work is high. The found upper bound is novel (though, it covers a very restrictive setting) and the algorithm seems reproducible (though I have not checked the code). 

summary_of_the_review: This paper presents a new method to adapt the HMC's integration time. It is shown that on the experimental models, the proposed method can outperform the baseline. 
They also find new bounds for a very restrictive case where HMC's state evolution can be solved in closed-form. As such, I am not sure if it can be called significant. Nonetheless, I think this finding is interesting and valuable.  It may also open doors to future theoretical works.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper considers the technique of sampling from a Gibbs distribution via the Ideal Hamiltonian Monte-Carlo (HMC) method. Specifically, the ideal HMC method is derived by iterative running the HMC from the current spatial position, but with a resampled velocity for a certain period of integration time. The integration time plays a key role in proving the mixing time of the algorithm: It is known that even for the Gaussian case, with a constant integration time, the mixing time is proportional to $\Omega(\kappa)$. To improve this, this paper proposes the Chebyshev integration time, which are derived from the roots of the Chebyshev polynomials. It is proved that using the proposed integrating time, the resulting ideal HMC method enjoys a mixing time of order $O(\sqrt{\kappa})$, for the Gaussian case. The authors also provide empirical evidence that the improved rate generalizes to non-Gaussian tasks.
strength_and_weaknesses: Strength:
This paper proposes the Chebyshev integration time which leads to a provably faster instance of the Ideal HMC method, in the Gaussian case. Empirical evidence shows that the improved rate generalizes to non-Gaussian tasks.

Weakness:
The current theoretical result only applies to the Gaussian case. 

clarity,_quality,_novelty_and_reproducibility: Clarity: This paper is well-written in terms of presenting the proposed method. However, the intuition of why this Chebyshev integration time accelerates the Ideal HMC method remains unclear. 

Novelty: The proposed Chebyshev integration time is novel as it improves over the lower bound for constant integration time. Empirical evidence suggests that the same technique may also improve the efficiency of sampling for non-Gaussian tasks.
summary_of_the_review: The Chebyshev integration time is novel, but the current analysis is limited to the Gaussian case. Intuition behind the success of this technique is missing.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: This paper proposes a scheme of time-varying integration based on Chebyshev polynomials for Hamiltoian Monte Carlo (HMC) methods. For the case of quadratic potential function, it achieves faster convergence in terms of Wasserstein-2 distance. The improvement on the dependence on condition number is akin to acceleration in optimization.

Strengths:

+This is the first accelerated result for HMC

+The use of Chebyshev polynomials in HMC is somewhat novel

Weaknesses:

-The theory is limited to quadratic potential function (Gaussian case).

After the author's response and reviewer discussion, the most negative reviewer has raised the score. Plus, this paper receives strong support from the other reviewer.  Thus, I recommend acceptance. 

justification_for_why_not_higher_score: The theory is limited to quadratic potential function (Gaussian case).
justification_for_why_not_lower_score: It receives strong support from one reviewer
Decision: Accept: poster