Workshop track -ICLR 2018 LSH-SAMPLING BREAKS THE COMPUTA- TIONAL CHICKEN-AND-EGG LOOP IN ADAP- TIVE STOCHASTIC GRADIENT ESTIMATION
Stochastic Gradient Descent or SGD is the most popular optimization algorithm for large-scale problems. SGD estimates the gradient by uniform sampling with sample size one. There have been several other works that suggest faster epoch wise convergence by using weighted non-uniform sampling for better gradient estimates. Unfortunately, the per-iteration cost of maintaining this adaptive distribution for gradient estimation is more than calculating the full gradient. As a result, the false impression of faster convergence in iterations leads to slower convergence in time, which we call a chicken-and-egg loop. In this paper, we break this barrier by providing the first demonstration of a sampling scheme, which leads to superior gradient estimation, while keeping the sampling cost per iteration similar to that of the uniform sampling. Such an algorithm is possible due to the sampling view of Locality Sensitive Hashing (LSH), which came to light recently. As a consequence of superior and fast estimation, we reduce the running time of all existing gradient descent algorithms. We demonstrate the benefits of our proposal on both SGD and AdaGrad.
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.