The goal of improving testing for differences between graphs is clearly relevant to neuroimaging and other application domains. While the specifics are somewhat incremental, I think this is a great idea, and reasonably well executed. Major issues: * Please explain specifically which gradients are used to get from (4) to (5). This derivation seems incorrect if one takes separate derivatives with respect to \beta_1 and \beta_2. How do you end up with a sum of terms (and not two separate terms)?

As the "LS" of ALS suggests, each iteration of ALS for tensor decomposition amounts to solving a least squares regression problem. The main contribution of this submission is then to observe that good upper bounds on the leverage scores of the underlying matrix can be quickly approximated due to special structure of the matrix, namely Theorem 3.2 of the submission. This is the only, albeit important, novel observation of this paper. Once Theorem 3.2 is obtained, filling in the other details is standard. From this one observation, they are able to compare quite favorably with [37] (see Figure (a) on page 8).

I enjoyed reading this paper, not being terribly familiar with work on survival analysis but very comfortable with GPs it was a bit of a struggle for me to understand certain parts of the paper initially and there still might be things that I've misunderstood and not being completely familiar with the background material my novelty rating should be taken with a grain of salt. Initially I was confused about the model as it seemed very specific but not particularly well motivated. After a bit or reading up on related material I understood that this is very related to Gaussian Cox process, a reference would clarify things here or making the connection in the introductions two last paragraphs clearer between "our prior" and the Gaussian Cox process. The paper is clearly written and well but I wish the authors would make their contributions clearer without the reader having to resort to go through all the related material. This is especially true for Section 3 and the data augumentation.

In Theorem 1, the error rate is as expected since max{q,r} theta* _{2,0} is approximately the number of parameters in the model. I think the factor of max{q,r} should not be omitted from Section 1.1, last paragraph so as not to be misleading. I am surprised however that the same factor of max{q,r} is not present in the error rate in Theorem 2, being replaced instead by (q r) inside the logarithm. This result should be checked since if I understand correctly, the number of parameters is still something like q or r times theta*_s _{2,0}. If Theorem 2 is correct as currently stated then a more thorough justification in words is needed.

The main idea of the paper is an interesting and, at least to me, novel one. Sections 1 to 3 are extremely well written, while the second half of the paper seems a bit more hurried. It would be worthwhile pointing out early in the paper that the proposed approach applies only when the canonical link is used (currently stated in line 92). However, the authors say: "Motivated by the results in the previous section, we design a computationally efficient algorithm for any GLM task that is as simple as solving the least squares problem; it is described in Algorithm 1." The "any" suggests that the canonical link is not required.

Technical quality: I have two doubts regarding the proof of their Lemma 2: 1. The authors argue, in the case of \phi_{C}(X) \epsilon_1\phi_{c_1}, the claim holds trivially. I don't see how this goes through. First, I don't see why A {c_1}(C,l) \phi_{C}(X). As I understand it, A {c_1}(C,l) is the expected cost of C while \phi_{C}(X) is the actual cost of C (random quantity).

It allows using "Option I" (taking the final iterate of the inner iteration), as is done in practice. They also propose to use a scaled version of Barzilai-Borwein to set the step-sizse for SVRG (and heuristically argue that this could also be useful for classic stochastic gradient methods too). Their experiments show that this adaptive step-size is competitive with fixed step-sizes. Clarity: The paper is very clearly-written and easy to understand (though many grammar issues remain). Significance: Although several heuristic adaptive step-size strategies exist in the literature, this is the first theoretically-justified method. It sill depends on constants that we don't know in general, but I believe is a step towards black-box SG methods. Details: Independent of the SVRG/SG results, the authors give a nice way to bound the step-size for the BB method. Normally, BB leads to a much faster rate than using a constant step-size, but in the SVRG setting your theory/experiments are just showing that it does as well as the best step-size (which is good, but it isn't better than the best step size). Finally, the paper would be much stronger if it compared to the two existing strategies that are used in practice: 1.

The paper studies the problem of minimizing the average of a finite sum of convex functions over a convex domain using stochastic algorithms that, opposed to most popular methods, apply WITHOUT-replacement sampling to the data. More specifically, the paper considers methods that first randomly permute the functions, and then process the functions via incremental updates one at a time, making at most a single pass over the data (hence the data is only shuffled once). There are three main motivations for considering stochastic methods with without-replacement sampling: 1. it is observed many times empirically (and to the best of my knowledge this is what ML practitioners really do) that applying random shuffles to the data and then apply incremental updates works better than with-replacement SGD. 2. After the data is randomly permuted, these algorithms require only sequential access to the memory, which is much more efficient than standard with-replacement SGD methods that require random access to perform the updates. Since the main setting under consideration here is when making at most a single pass, it sounds plausible to assume that the data is already stored in some random permutation, and hence the algorithm is fully sequential, and there is no need to even artificially permute the data. In a distributed setting in which data is partitioned to several machine (not assuming the data is sampled i.i.d from a distribution), it is more natural and efficient to analyze without-replacement algorithms.

There are several points that need clarification, from the most important to the less important one: * One key missing point is the reason to exist of the k {2r/d} factor which appears in (14). The only motivation is intuition, but I do not get it at all. It must be introduced rigorously. If I am not mistaken, epsilon in (45), epsilon can be chosen arbitrarily small. If this is the case, then (47) is wrong, even for Mahalanobis, since is enforces the Hessian to be essentially spherical.

This paper makes some pretty critical mistakes regarding previous work. For one, they cite [8], but they should in fact be citing Cohen et al. "Dimensionality Reduction for k-Means Clustering and Low Rank Approximation" This is not just a typo - the authors go on to state a result of [8] about operator norm rather than the result of the Cohen et al. paper - namely, the Cohen et al. paper achieves O(k/eps 2) rescaled columns deterministically for exactly the same problem considered in this submission - see part 5 of Lemma 11 and section 7.3 based on BSS. This is much stronger than the O(k 2/eps 2) rescaled columns achieved in the submission. This directly contradicts their sentence "Our main result is the first algorithm for computing an (k,eps)-coreset C of size independent of both n and d". The authors also say later [8,7] minimize the 2-norm - [8] is the wrong reference again!