We thank all the reviewers for their time in giving us reviews and feedback. One point deserves specific comment: R1, R2, and R4 all had questions about the relationship between hypertree width and hierarchy width, and how this relates to the comparison between Gibbs sampling and exact inference techniques. When hierarchy width is bounded, the hypertree width is similarly bounded (Statement 1 in our paper). This means that for the models we focus on, where Gibbs mixes in polynomial time, exact inference also runs in polynomial time. However, for graphs with sufficiently small weights (such as the Paleontology model we mention), the polynomial exponent for Gibbs will be smaller than for exact sampling.

SUMMARY: This paper studies the effect of noise correlation in some models of multi-output regression. It argues that a method that does not benefit from the correlation, such as Ordinary Least Squares (OLS), may perform much worse than a method that does, such as Maximum Likelihood Estimation (MLE). For certain linear models (Pooled model and Seemingly Unrelated Regression), which are studied in the paper, the MLE estimator requires the joint optimization of the covariance and regression weights. This is a non-convex problem. Alternative Minimization (AltMin) algorithm is an approach to solve the problem by iteratively optimizing the covariance and the weights.

The paper proposes a mechanism for explaining Bayesian inference and network plasticity in the brain using an algorithm very similar to Stochastic Gradient Langevin Dynamics. Clarity: The paper is well written. Even though my background is machine learning and not neuroscience, I was able to follow most of the paper. Originality: The mechanism itself is well studied in the machine learning literature where it is called Stochastic Gradient Langevin Dynamics (SGLD) (see Ref[1] and analysis in Ref[2]). This is also well known in physics where it is usually called the Langevin equation with noisy force (see e.g.

Weaknesses: The paper is technically heavy for my expertise, so I can only raise questions about its content. Might they be naive, discussing them in the paper would help other readers to understand the scope of this work. A first concern is about the fact that the paper presents solely (Theorem 1) the PAC-Bayes bound of McAllester (1999), converging at rate sqrt(1/m). Since this pioneer work, many variations on the PAC-Bayes bounds have been proposed. Notably, Seeger (2002)'s and Catoni (2007)'s bounds are known to converge at rate 1/m when the empirical risk is zero (see also Guedj (2019) for a up-to-date overview of PAC-Bayes literature).

Summary and Contributions: Statistical property estimation is an important and active area at the intersection of theoretical computer science, statistics, and information theory. For example, a basic question in this realm: given n iid samples from an unknown discrete distribution p, how well can we estimate the entropy H(p), and what is an efficient algorithm for doing so? Recent efforts have shown that, for any symmetric property, the profile maximum likelihood estimator is universally minimax optimal for a wide range of parameters. While this at first seemed like a purely theoretical result, algorithmic efforts quickly caught up to show that 1) efficient approximation of the profile maximum likelihood estimator is possible and 2) approximate profile maximum likelihood estimation suffices for minimax optimality. In this context, this paper refines recent approximation algorithms from exp(-\sqrt{n} log n) to exp(-k log n) where k is the number of observed frequencies, with k O(\sqrt{n}).

This paper proposes new and substantial improvements to the algorithmic side of the PLM estimation problem. New theoretical tools are introduced and the analysis is refined and deep. The authors seem to have adequately addressed all of the concerns in the rebuttal.

The paper proposes to learn proposal distributions for sequential Monte Carlo (SMC) in nonlinear state-space models (SSMs). The method (NASMC) parameterizes the proposals as (recurrent) neural networks (RNNs) which are trained to fit the filtering distribution obtained with SMC. The approach is evaluated in three different setups: (a) state inference; (b) Bayesian learning (inference) of model parameters; (c) ML parameter learning with approximate (SMC) inference as inner loop. Results suggest that the the adaptive proposals outperform naive proposals (the prior) and also techniques such as the extended Kalman Particle filter and the Unscented Particle Filter (where the latter two are applicable). For ML learning of NN SSMs the approach performs similar to recently proposed stochastic variational approaches.

High-dimensional neural spike train analysis with generalized count linear dynamical systems This paper describes a general exponential-family model (called the "generalized count" (GC) distribution) for multi-neuron spike count data. The model accounts for both under-dispersed and over-dispersed spike count data, and has Poisson, Negative Binomial, Bernoulli, and several other classic models as special cases. The authors give a clear account of the relationship to other models, and demonstrate the need for a model to capture under-dispersed counts in primate motor cortex. They then describe an efficient method for maximum-likelihood fitting (and demonstrate concavity of the log-likelihood). They derive an efficient variational Bayesian inference method and apply the model to data from primate motor cortex, showing that it accounts more accurately for variance and cross-covariance of spike count data, compared to a model with Poisson observations.

Additional Feedback: page 1, last para: this is confusing to read. The reference cited here is Babai's paper. Why is the slowness of current graph isomorphism algorithms relevant to the problem of producing isomorphism-injective graph representations? Definition 3: a minor point, but it is useful to say what is meant by size (e.g., #edges, or size of description of the graph) After definition 7, it is useful to formally define the notion of "universal function approximator", as this could be interpreted in different ways The notation of multi-function in Definition 6 uses a double arrow, but it doesn't seem to get used consistently like that. It is used with a single arrow in Definition 7. Also the notion is confusing, since it is not a function into the range but into its power set.

Each reviewer believes that the paper is poorly written. The reviewers, though, have agreed that (i) the problem is interesting, that (ii) the theoretical results seem to hold, and that (iii) they are interesting. On the other hand, it is not clear whether a quick revision would solve all or many of the readability issues.