Exploiting the Structure: Stochastic Gradient Methods Using Raw Clusters *
The amount of data available in the world is growing faster than our ability to deal with it. However, if we take advantage of the internal structure, data may become much smaller for machine learning purposes. In this paper we focus on one of the fundamental machine learning tasks, empirical risk minimization (ERM), and provide faster algorithms with the help from the clustering structure of the data. We introduce a simple notion of raw clustering that can be efficiently computed from the data, and propose two algorithms based on clustering information. Our accelerated algorithm ClusterACDM is built on a novel Haar transformation applied to the dual space of the ERM problem, and our variance-reduction based algorithm ClusterSVRG introduces a new gradient estimator using clustering. Our algorithms outperform their classical counterparts ACDM and SVRG respectively.
The paper introduces two new algorithms: cluster version of accelerated coordinate descent methods (Cluster ACDM) and cluster version of stochastic variance reduced gradient method (Cluster SVRG). The basic idea is to study how it is possible  to improve these methods using additional information on the data; in particular: clustering information. The authors define several notions of raw clusters (different for the two methods; but related) – and explain how these can be efficiently computed. Using the clustering information, the SVRG and ACDM methods are then accelerated. The resulting complexity results are better than the results for the previous variants – as they do not make use of such extra closeting information. The theoretical findings are sufficiently conclusively confirmed by experiments; with insightful commentary.   For ACDM, the new approach can be seen as a new preconditioner enhanced by a novel Haar transform (specific rotations on each cluster highlighting average direction in each cluster and suppressing individual directions in a stochastic sense); and for SVRG, the the new Cluster SVRG method can be seen as an algorithm interpolating between SVRG and SAGA; with further reduction of variance of the stochastic gradient enabled by reduction in “outdatedness” via utilizing clustering information.  In general, this is a beautifully written paper, with elegant new results in an important area of ML. 
The initial motivation seems to be the work of Hoffman et al on the use of clustering to speedup stochastic methods for ERM. Their method was not proved to converge to the optimal due to the use of biased stochastic gradients. Also, that work seemed to work only for small clusters due to the approach chosen. This papers goes a long way to develop the basic idea into a satisfying theoretical framework which also gives rise to efficient implementations.  This paper is truly a pleasure to read – a very fine example of academic exposition. The results are innovative, and yet intuitively explained. The theory seems correct; and the experiments show that the methods work better than the competing approaches considered. I believe that several people might pick up this work in an attempt to use it / extend the results.     Question 1: Can Assumption B.3 be removed or replaced by something that can be verified from assumptions on the problem only (and not on the algorithm itself)? Can you prove that in some cases \xi is finite? What value does it have? How large can it be?  Question 2: What are the challenges associated with extending the Cluster ACDM results to non-quadratic losses?  Question 3: Is Haar transform necessary? What other transforms can have the same effect on the dual problem?  Small issues: 1. Line 60: improve -> expect 2. Line 125: can be -> to be 3. Line 178: H_{cl} is not from R^n 4. Lines 263 and 266: same as -> same time as 5. Line 296: ride -> ridge