Venue: ICLR 2018 conference

Reviews:

final_score: rating: 8: Top 50% of accepted papers, clear accept
review_content: Authors propose sampling stochastic gradients from a monotonic function proportional to gradient magnitudes by using LSH. I found the paper relatively creative and generally well-founded and well-argued.

Nice clear example with least squares linear regression, though a little hard to tell how generalizable the given ideas are to other loss functions/function classes, given the authors seem to be taking heavy advantage of the inner product. 

Experiments: appreciated the wall clock timings.

SGD comparison: “fixed learning rate.” Didn't see how the initial (well constant here) step size was tuned? Why not use the more standard 1/t decay?

Fig 1: Suspicious CIFAR100 that test objective is so much better than train objective? Legend backwards?

Why were so many of the chosen datasets have so few training examples?

Paper is mostly very clearly written, though a bit too redundant and some sentences are oddly ungrammatical as if a word is missing - just needs a careful read-through. 

review_title: Creative Paper Worth Sharing

final_score: rating: 4: Ok but not good enough - rejection
review_content: The main contribution of this work is just a combination of LSH schemes and SGD updates. Since hashing schemes essentially reduce the dimension, LSH brings computational benefits to the SGD operation. The targeted issue is fundamentally important, and the proposed approach (exploiting LSH schemes) seems to be sound.  Specifically, LSH schemes fit into the SGD schemes since they hash two vectors to the same bucket with probability in proportional to their distance (here, inner product or Cosine similarity).

Strengths:  a sound approach; a simple and straightforward idea that is shown to work well in evaluations.

Weaknesses: 
1. The phrase of "computational chicken-and-egg loop" in the title and also in the main body is misleading and not accurate. The so-called "chicken-and-egg” issue concerns the causality dilemma: two causally related things, which comes the first. In the paper, the authors concerned "more accurate gradients" and "faster convergence"; their causality is very clear (the first leads to the second), and there is no causality dilemma. Even from a computational perspective, "SDG schemes aim for computational efficiency" and "stochastic makes the convergence slow down" are not a causality dilemma.  The reason behind is that the latter is the cost of the first one, just the old saying that "there is no such thing as a free lunch". Therefore, this disordered logic makes the title very misleading, and all the corresponding descriptions in the main body are obscured by "twisted" and unnatural logics. 
 
2. The depth is so limited. Besides a good observation that LSH fits well into SDG, there are no more in-depth results provided. The theorems (Theorems 1~3) are trivial, with loose relations with LSH.
	 
3. The LSH schemes are not correctly referred to. Since the similarity metric is inner-product, the authors are expected to refer to Cosine similarity and inner-product based LSHs, which were published recently in NIPS. It is not in depth to assume "any known LSH scheme" in Alg. 2. Accordingly again, Theorems 1~3 are unrelated with this specific kind of similarity metric (Cosine similarity).

4. As the authors tried hard to stick to the unnecessary (a bit bragging) phrase "computational chicken-and-egg loop", the organization and presentation of the whole manuscript are poor.

5. Occasionally, there are typos, and it is not good to use words in formulas. Please proof-read carefully.

review_title: A simple application of LSH but logically disordered

final_score: rating: 4: Ok but not good enough - rejection
review_content:   The main idea in the paper is fairly simple:

 The paper considers SGD over an objective of the form of a sum over examples of a quadratic loss.
The basic form of SGD selects an example uniformly.   Instead,  one can use any probability distribution over examples and apply inverse probability weighting to retain unbiasedness of the gradient.

  A good method (that builds on classic pps sampling) is to select examples with higher normed gradients with higher probability [Alain et al 2015].

  With quadratic loss,  the gradient increases with the inner product of the parameter vector (concatenated with -1) and the example vector x_i (concatenated with the label y_i).

  For the current parameter vector \theta,  we would like to sample examples so that the probability of sampling larger inner products is larger.

  The paper uses LSH structures, computed over the set of examples,
 to quickly sample examples with large inner products with the current parameter vector \theta.   Essentially, two vectors are hashed to the same bucket with probability that increases with their cosine similarity.
 So we select examples in the same LSH bucket as \theta (for rubstness, we use multiple LSH mappings).


strengths:  simple idea that can work well in the context of sampling examples for SGD

weaknesses: 

  The novelty in the paper is limited. The use of LSH for sampling is a common technique to sample more similar vectors with higher probability.  There are theorems,  but they are trivial, straightforward applications of importance sampling. 

 The paper is not well written. The presentation is much more complex that need be. References to classic weighted sampling are 

  The application is limited to certain loss functions for which we can compute LSH structures.  This excludes NN models and even the addition of regularization to the quadratic loss can affect the effectiveness.

review_title: Another application of LSH sampling

Meta-review: The reviewers think that the theoretical contribution is not significant on its own. The reviewers find the empirical aspect of the paper interesting, but more analysis of the empirical behavior is required, especially for large datasets. Even for small datasets with input augmentation (e.g. random crops in CIFAR-10) the pre-processing can become prohibitive. I recommend improving the manuscript for a re-submission to another venue and an ICLR workshop presentation.
Decision: Invite to Workshop Track