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. In this paper, we proposed a novel LSH-based sampler with a reduction to the gradient estimation variance. We achieved it by sampling with probability proportional to the L 2 norm of the instances gradients leading to an optimal distribution that minimizes the variance of estimation. More remarkably, LSD is as computationally efficient as SGD but achieves faster convergence not only epoch wise but also time wise.Peilin Zhao and Tong Zhang. Stochastic optimization with importance sampling for regularized loss minimization. In Proceedings of the 32nd International Conference on Machine Learning (ICML-15), pp. 1-9, 2015.A EPOCH PLOTS AND PROOFS Theorem 3. Let S be the bucket that sample x m is chosen from in Algorithm 2. Let p m be the sampling probability associated with sample x m . Suppose we query a sample with ✓ t . Then we have an unbiased estimator of the full gradient: DISPLAYFORM0 Proof. DISPLAYFORM1 Theorem 4. The Trace of the covariance of our estimator is: DISPLAYFORM2 Proof.
We improve the running of all existing gradient descent algorithms. Authors propose sampling stochastic gradients from a monotonic function proportional to gradient magnitudes by using LSH.  Considers SGD over an objective of the form of a sum over examples of a quadratic loss.