The goal is to obtain such guarantees with quantities that can be computed from the data and the output of the clustering algorithms being compared. Providing such model free theoretical guarantees for clustering is of importance for both theoretical and practical purposes. Given that Spectral Clutering works well for all the models specified, why not use the same model estimator? In particular, it is not clear why the Laplacian is used for PFM while the adjacency matrix is used for the SBM. Also, the results for PFM is for weighted ME whereas for SBM it is in terms of ME.

This paper presents a randomized method for decomposing a symmetric, orthogonal tensor that is "nearly low rank". The fact that the tensor is symmetric and composed of orthogonal components may sound restrictive, but this is exactly the sort of tensor decomposition problem that comes up in spectral methods that solve Latent Dirichlet Allocation problems. So, it's an interesting model to study. The method introduced very closely follows work in a paper from NIPS 2015, "Fast and guaranteed tensor decomposition via sketching" which uses a standard tensor power method for decomposition, but speeds up each iteration by accelerating the required tensor contractions (vector dot products against the tensor) via randomized sketching techniques. This paper uses the same algorithm, but instead of using sketches based on "random projections", which take random linear combinations of all of the components of the tensor, it uses a subsampling technique to approximate the contractions. The authors main selling point is that this approach should allow for better running times since they don't have to touch every entry in the tensor with each iteration.

This is a successive work correcting previous research on using KL averaging combining subset estimators. I think the most appealing point for using KL averaging, despite the computational issue, is its power in dealing with latent variable models. There is another line of work in using geometric median to combine subset estimators the authors might want to compare to, for example, Minsker (2013) and Hsu and Sabato (2013). These algorithms are simple and efficient in most cases, but might not be doing well for latent variable models. The variance reduction technique used in this article is very similar to the de-bias technique used in Javanmard and Montanari (2015) and Lee et a. (2015), so the theoretical contribution is kind of limited.

I am not qualified to evaluate this work in term of its relevance within the literature. Therefore my judgment is only about the paper content itself. Also, I have only reviewed the proofs contained in the main paper the one of Lemma A.1. Theorem 3.2 guarantees a significant improvement upon the passive learner characterized by 3.1. I find the example in line2 141-143 about the 1/sqrt(m) order very helpful and I suggest the authors to include it in the introduction as well.

This paper has some strong points and some not so strong points. The main strong point is that using BDMC to assess convergence of MCMC operators is a beautifully simple idea, and easy to implement, which in my opinion means that this work is potentially high impact. This is particularly true in the context of probabilistic programming systems, which indeed are the envisioned use case here, and I think all such systems would do well to at least implement this method. The authors cite an arxiv submission on BDMC as existing work, but (I think wisely) choose to devote a relatively large amount of space to reiterating its description. Unfortunately this does mean that the main technical contributions presented in sections 3.1 and 3.2 are somewhat rushed, and it is unfortunately also here where the writing quality slips a bit.

Thank you for the submission. There are a few points of clinical clarity. The more targeted goal that is in line with other models in this area is to predict clinical deterioration (a shift in patient condition that requires a higher level of care). The goal of "clinical state" is less about understanding what it is but how shifts in the state drive an intervention (i.e. ICU transfer) (2) The authors should clarify the use case they describe.

Summary: The paper presents a provably consistent, polynomial-time algorithm (that they call consistent robust regression, or CRR) for linear regression with corrupted samples under the oblivious adversary model. The algorithm is a simple iterative hard thresholding (IHT) procedure, and the authors show that this algorithm exhibits linear convergence. The analysis is supported by some representative synthetic numerical results. Strengths: Quality: Somewhat surprisingly, this method appears to be the first consistent procedure for robust linear regression, i.e., the parameter estimation error vanishes as the number of samples tends to infinity. Other estimation procedures (such as LASSO-type methods) seem to only provide solutions with error comparable to the noise level, even in the large sample limit.

The paper studies stochastic convex optimization in a distributed master/workers framework, where on each round each machine out of m produces a stochastic gradient and sends it to the master, which aggregates these into a mini-batch. In this paper the authors allow a fraction of alpha of the machines to be Byzantine, i.e., they do not need to report valid stochastic gradients but may produce arbitrary vectors, even in an adversarial manner. The goal is to aggregate the reports of the machines and to converge to an optimal solution of the convex objective despite the malicious Byzantine machines. The authors present a novel variant of minibatch-SGD which tackles the difficulty the dealing with Byzantine machines. They prove upper-bounds on the convergence and nearly optimal matching lower-bounds on any algorithm working in such framework, and in this sense the results are quite satisfactory.

For example, one would expect some discussion about extracting motifs in the context of a concrete PPL. Also, the paper assumes that the motifs can be extracted at the beginning of inference (Algorithm 1). However, in PPLs the graph structure changes with different values of the latent variables, so it doesn't appear applicable.

This paper studies learning over-parametrized single hidden layer ReLU neural networks for multi-class classification via SGD and the corresponding generalization error. They consider a mixture data distribution where each class has well-separated and compact support. The authors show SGD applied on the considered learning model achieves good prediction error with high probability under suitable assumptions. As a result even in severely over-parametrized models, SGD can generalize well although the network has enough capacity to fit arbitrary labels. The main insight in the theoretical analysis appears to be the observation that in the over-parametrized case, many ReLU neurons don't change their activation pattern when initialized randomly.