Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 5: Marginally below acceptance threshold
review_content: ##  Summary of the paper
The authors focused on the fact that there are two types of stochasticity in SG-MCMCs, one is the intrinsic randomness of MCMC and the other is the randomness introduced by gradient subsampling. Then the authors proposed coupling these randomnesses so that the final variance is reduced. Experimental results support that the proposed coupling seems promising.

## Strong and weak points of the paper
### Strong points
- Provided a new connection between importance sampling and stochastic gradient.
- Provided an asymptotic analysis for the variance reduction in Theorem 4, which seems novel variance analysis.

### Weak points
- I am not sure the approximations introduced in Sec 4.3 are valid theoretically and numerically. I commend these points in the below.

## Rating
- Clarity: Well written, easy to read, although I did not check the proof of Theorem 4.
- Correctness: I did not check all the proof in detail.
- Novelty: The idea seems very interesting and important in the community.

## Comments and Questions
- Q) the authors introduced several approximations, e.g., setting M=1,  setting x as the equibirum points, to implement the index sampling efficiently. How those approximations affect the final variance theoretically ? Especially, although the authors provided the variance analysis in Theorem 4, I think it is unclear how these approximations affect the upper bound of the variance in Eq.(6) explcitely.

- Q) could you explain why the approximation of $r_{k+1}=r_k$ in Sec 4.3 is valid and when this approximation is not valid ? At first sight I thought that this equilibrium condition is definitely wrong at an early stage of the underdamped Langevin dynamics.

- Q) In Fig 1.d to 1.f, the authors studied the impact of M. It seems that the larger M are, the worse results are obtained. Is this correct ? I thought that increasing M means increasing the number of Markov chains for the index sampling and it should improve the performance.
review_title: The authors provide the novel connection between stochastic gradient and importance sampling.

final_score: rating: 4: Ok but not good enough - rejection
review_content: This paper proposes a non-uniform sampling method for stochastic gradient minibatches for SG-MCMC. By sampling the indices of the stochastic gradients according to a parameter-specific (exponentially weighted) non-uniform distribution, the paper shows that it exactly matches the transition kernel of full batch gradient MCMC (for underdamped langevin dynamics) in Theorem 2. Although this exponentially weight distribution is intractable, the paper presents an approximate sampler in Algorithm 1 (that both uses a 1-step Metropolis Hastings approximation and a deterministic approximation for the $x$ term $r_{k+1} = r_k$). Finally the paper compares Algorithm 1 with other SGMCMC methods in a small synthetic Gaussian example, bayesian logistic regression on Covertype data, and a Bayesian neural network on MNIST.  

The idea to non-uniformly sample the random stochastic gradient index to match SGULD is clever. The paper would benefit from additional editing: the notation and presentation of ideas is unclear + difficult to parse in some sections.   

This paper should be rejected. Although the particular non-uniform random sampling scheme is novel, it is not clear how the two approximations (MH and $x$) in Algorithm 1 affect the error of the sampler in practice. Although the experiments show some benefit of Algorithm 1 over vanilla SGMCMC, they are not strongly convincing or exhaustive and do not analyze the error introduced in Algorithm 1. I believe with significant editing and additional experiments, this paper would be more competitive, but as it stands, it should be rejected. 
  
Although Theorems 1-4 may be interesting for the non-uniform sampling scheme for stochastic gradient indices (Eq 4), in practice, Algorithm 1 is different due to the two approximations. In particular, I am concerned about the approximation for $x$ (especially since the definition of $x$ seems circular). Although it may appear that the approximation $r_{k+1} = r_k$ works well for your experiments, this may not be the case in general. Clarity on when this approximation is justified and when it is not would help build confidence in this approximation. I would have liked to have seen how the performance of Algorithm 1 compared to the theory (Theorem 3 or 4) for the theoretical sampler using (Eq 4) or the full batch "ground truth" MCMC (Eq 3).

review_title: Recommendation to Reject

final_score: rating: 6: Marginally above acceptance threshold
review_content: ##########################################################################
Summary:

The paper proposes an alternative to the uniform sampling scheme used for constructing mini-batches in stochastic gradient sampling algorithms. The proposed scheme, called Exponentially Weighted Stochastic Gradient (EWSG), is devised such its transition kernel matches that of the batch gradient descent. The proposed scheme is shown to achieve better results than the uniform sampling one.

##########################################################################
Reason for score:

I'm oscillating between accepting the paper and rejecting it. Overall there are good merits to the paper, however there are some aspects on which I would like to have some further clarifications from the authors.

##########################################################################
Pros:

1. The paper is overall well written with a proper formulation and justification of the problem it addresses. The proposed solution is analysed both theoretically and empirically and the results show the advantage of the proposed method with respect to the uniform sampling scheme.

2. The subject the paper addresses is of importance to the ML community and I believe the advances brought by the paper are sufficient to warrant its acceptance. 

##########################################################################
Cons:

1. I have some concerns regarding the practical implementation of the proposed scheme in general. Overall, I appreciated the discussion about the choice of the hyper-parameters. However, my concerns stems from the fact that you have two intertwining Markov chains, one for the quantity we wish to perform inference on and one for the indices. From figure 1(a) we can see that there is a slower convergence of the EWSG method with respect to the SGLD one, though this slower converge is compensated by the better accuracy. My question is whether in all practical situations I will eventually reach a better accuracy than SGLD within an acceptable computational budget?
On the same note, in the paper you deal only with the case of one item per mini-batch. You address in the appendix the extension to mini-batch sizes greater than one. However, when we consider mini-batch sizes different than one, for some mini-batch sizes the number of possible combinations is greater than the number of elements in the data set. The sampling over the indexes will lead to sampling the "best" mini-batches, however would the advantage of the proposed method still be retained within a fixed computational budget in such a scenario given that there are more possibilities that need exploring?  

2. Another issue stems from the fact that the method requires access to the full dataset, or at least to be able to retrieve items from it. There are situations in which the full dataset is distributed across different computational nodes, thus on one node I would have only a limited subset of data. Assuming we can recombine the results from each node to get a global estimate, would it still be beneficial to run your proposed method on each node such that to improve accuracy or in such a case running SGLD would suffice? This question is related to the assumption that you make at the beginning of section 4.1 that n >> d and I'm just wondering if there are any advantages of using your proposed method when the number of data items is still greater than the dimension, but not significantly.

3. I have a minor issue with the plots in figure 1: the values on the ordinate axis are sometimes very difficult to see and read, you could increase the font given that there still is space available before reaching the margins of the page.
review_title: The paper proposes an innovative sampling scheme to construct the minibatches used in stochastic gradient algorithms. 

Meta-review: This paper describes a non-uniformly weighted version of SGMCMC, combining aspects of SG methods and importance sampling. The idea is interesting and novel, but unfortunately the authors have not made a compelling case for the resulting algorithm being a practical addition to the literature. The experimental analysis is not particularly compelling, and there are key concerns raised about practical implementation, and about the validity of the approximations raised. I hope that the authors will continue along this interesting line of work and add additional explorations of the approximations and improved experimental analysis.
Decision: Reject