This is an interesting work that presents the perhaps first theoretical guarantee for a widely used optimization technique of the problem of robust PCA. I think it has potential and should be somewhere between poster and oral. During the rebuttal period, I would suggest the authors to address the following minor concerns. That been said, it is not clear how one is able to know the true rank "r" and the corruption fraction "alpha". The projection step (Step 7 and Step 8) requires a knowledge of the incoherence parameter.

This paper presents a new non-parametric tensor regression method based on kernels. More specifically, the authors proposed a regularization based optimization approach with alternating minimization for non-parametric tensor regression model [15]. Moreover, the theoretical guarantee for the proposed method is presented the paper. Through experiments on various datasets, the proposed method compares favorably with existing state-of-the-art. The paper is clearly written and easy to read. I understand the key contribution of this paper is the theoretical analysis of the non-parametric tensor regression.

Overall, I found the paper interesting; the paper offers new theory as well as numerical results comparable to the state of the art on decently difficult datasets. Perhaps due to space constraints, an important part of the paper (section 3.2) - the inference algorithm - is poorly explained. In particular, I initially thought that the use of particles meant that the approximating distribution was a sum of Dirac delta functions - but that cannot be the case since, even with many particles, the'posterior' would degenerate into the MAP (note that in similar work, authors either use particles when p(x) involves discrete x variables, as in Kulkarni et al, or'smooth' the particles to approximate a continuous distribution, as in Gershman et al). Instead, it looks like the algorithm works directly on samples of the distribution q0, q1.. (hence the vague'for whatever distribution q that {xi}ni 1 currently represents'). It is tempting to consider q_i to be a kernel density estimate (mixture of normals with fixed width), and see if we can approximate equation 9 for that representation to be stable.

Technical quality: I think that the theory is very complete (bounds are given for pretty much everything relevant to the problem), and the experiments show that this method performs better on large/complicated models (the small/simple models have too little variance for extra servers to help, and the staleness prevents much benefits). I think the biggest limitation of the paper is the lack of comparison against the method in [14] (the paper mostly compares against the non-distributed -- 1 worker -- case, instead of a more standard distributed case). Novelty/originality: My impression is theoretical results are mostly a combination of proof techniques used in other SG-MCMC and asynchronous SGD papers (however, I'm not too sure that this claim is correct). Assuming this is true, I think the results are well-executed, but not too unique. Potential impact or usefulness: I think the theoretical analysis will be useful for people interested in how asynchrony affects SG-MCMC. However, I'm not too clear how much this will help for running SG-MCMC in practice.

Is this a fundamental bottleneck or an artifact the proof technique? What happens if we tolerate p(i, j, l) that do not depend on n? 3) As a result of the assumption that all clusters are growing linearly in n, Theorem 3 for L 2 gives suboptimal result for minimum cluster size (which is a bottleneck for clustering algorithms). In particular, the minimum cluster size has to be \Omega(n). In both the cases (convex algorithms and spectral clustering), p and q in SBM can be as small as Omega(polylog(n) / n). Minor point: It would be better to have the algorithm in the paper since a part of the paper is about guarantees for it.

Despite its usefulness, the proposed method is a bit trivial. Low-rank approximation and using randomized SVD for low-rank approximation are well known techniques. Besides, I have two minor comments: 1. Why the randomized algorithm can improve performance (lower objective value and higher recognition rate)? See Figure 1(a) and Figure 1(a)-(c).

I have one key concern, which may be a misunderstanding on my part as I did not check the supplementary section in detail. The update at each time step is computed using gradients of different parameter values (theta), some of which were generated arbitrarily many time steps ago. This dependence on previous samples means that the SAGA-LD chain is not Markov. The proofs seem to be based on a result for SG-MCMC chains, but I am not sure if the result easily applies to SAGA-LD because of the violation of the Markov property. Other than the above point, I think this is a very useful line of work.

REVIEW The results in Figure 2 look quite good, but why? Is it because kernelization or is it because of the simpler covariance structure? Overall no explanation on why the method performs better is given. Timing comparisons with the other factorizations are not presented, so is the method faster? If not, what happens if we increase the ranks for the other methods.

This paper addresses a topic that was proposed as future work in [32], and by design, much of its contents are adaptations of results found in [14] and [21]. Thus, the analysis is incremental. Nonetheless, the paper contributes a manifoldized algorithm and bridges a gap between convex optimization and Riemannian optimization. Furthermore, the paper provides a useful lemma to analyze Riemannian methods, which can have a lasting impact. My main concern with this paper is its presentation.

In supervised learning, one is interested in minimizing the empirical risk where efficient optimization algorithms become the key. First-order methods such as stochastic gradient descent and its variants are reasonably well understood admitting efficient implementation and parallelization techniques. However there has been a recent interest in making second-order methods such as Newton's method or L-BFGS method efficient for such large-scale problems. This paper is along this direction, presenting a new variant of the stochastic L-BFGS method that is efficient and robust in mainly two settings: The first arises in the presence of node failures in a distributed computing environment, the second occurs when one uses an adaptive batch size that varies over iterations for accelerating learning. The main idea is to form the Hessian estimate based on the overlap between consecutive batches (the intuition why this works is that we have less limitation in choosing the second-order information matrix compared to an estimate of the true gradient).