This paper presents a new analysis for proximal stochastic gradient Langevin algorithm. All the reviewers recognized the intellectual merits with minor concerns. I would suggest the authors to carefully revise their paper based the reviewers' comments.

This is a novel combination of existing techniques that appears well-formulated with intriguing experimental results. In particular, this work leverages the strengths stochastic gradient MCMC methods with stochastic approximation to form an adaptive empirical Bayesian approach to learning the parameters and hyperparameters of a Bayesian neural network (BNN). My best understanding is that by optimizing the hyperparameters (rather than sampling them), this new method improves upon existing approaches, speeding up inference without sacrificing quality (especially in the model compression domain). Other areas of BNN literature could be cited, but I think the authors were prudent not to distract the reader from the particular area of focus. This work demonstrates considerable theoretical analysis and is supported by intriguing experimental evidence.

EDIT: After reading the author's rebuttal, I changed my assessment of the paper to an accept. The paper is well written and it does a good job at explaining the intuition behind the proposed algorithm. I appreciated the inclusion of the small dimensional toy example as it illustrates in a simple and clear manner the adaptability property of the algorithm. My main concern with the proposed algorithm is that, in my opinion, it is most suitable for small dimensional problems only. The provided examples further justify my impression given that posterior distribution to sample from is of reduced dimension. Consequently, I'm having a hard time justifying the interest of the ML community with respect to the proposed sampling algorithm considering its perceived limited scope.

The authors should be commended on writing and submitting a interesting paper on an important topic: adaptive MCMC with an "active" set of samples for estimating a proposal distribution online. The ergodicity theoretical contribution outweighed the deficiencies noted by the reviewers. It would be great if the authors, when working towards the camera-ready, heed the reviewer advice; particularly as it relates to covering related work.

The highlighted phenomenon (the convergence of a short-run MCMC while training EBMs) seems to be novel and very interesting. The conventional wisdom is that a simple MCMC algorithm like Langevin dynamics would take a long time to converge close to the stationary distribution of the EBM when initialized far from it. The paper argues that in fact if the EBM is trained by generating negative samples from a short-run MCMC, then the short-run MCMC chain would in fact converge close to the data distribution (the authors argue that the "closeness" is related to moment matching). The theoretical argument for explaining this phenomenon seems suggestive, but ultimately didn't convince the reviewer (even convergence of the algorithm seems to be not explained, and section 4.2 seems particularly weak - it's not clear what the "generalized moment matching objective" is trying to achieve). However the empirical evidence for the convergence of short-run MCMC in EBMs seems very compelling - the training procedure for the model is significantly simpler than other procedures used to train EBMs, yet produces highly competitive results on several image datasets.

A new energy-based generative model for images is proposed. The paper suggests to run Langevin dynamics in the data domain to create artificial samples, and updating the model parameters based on these synthesized images in an'analysis by synthesis' framework. The generative model allows for unconditional generation and interpolation. It is interesting that short-run MCMC can be used in this context despite not being converged. The effect of the hyperparameter K (number of MCMC steps) could have been more explored.

Additional Feedback: I very much enjoyed the paper, and I congratulate the authors on their work. The experimental results by themselves do not necessarily provide a compelling reason to use NKF over previous models. But I think the idea is an important and straight-forward one, addressing a variety of weaknesses of previous models. On the other hand, the omission of any discussion of the non-additive noise seemed problematic to me. Minor comments: [L262]: [5] is a textbook, please be more specific in the ref.

We thank you for your submission. Reviewers agree that the paper is novel and of interest to the Neurips community. Please address carefully reviewers comments in your camera ready version.

UPDATE: I've read the other reviews and the rebuttal. I am keeping my score - this is a good paper. The study of Stochastic Gradient Descent in overparametrized setting is a popular and important trend in a recent development of huge-scale optimization for deep-learning. The authors propose a very basic and classical method, consisting from the well-known algorithmical blocks (SGD Armijo-type line search) together with its first theoretical justification under "interpolation assumption". The proof of convergence (for example, Theorem 2) mainly consists from the standard arguments (which are used for the proof of the classical non-stochastic Gradient Method under Lipschitz-continuous gradients).

This paper brings a classic idea into the present and makes progress on a vexing problem with SGD --- setting the step size. The authors provide theoretical evidence as well as emipirical evidence that their method is useful. The assumptions may be somewhat limiting; one version requires strong convexity and when that is relaxed, other assumptions must be made. But this work points to a path that may be useful in the long-run. An important way of contribution in ML is bridging fields; that could mean bringing in ideas that are state-of-the-art in other fields or it could mean revisiting classic ideas in new ways.