Venue: ICLR 2017 conference

Reviews:

final_score: rating: 4: Ok but not good enough - rejection
review_content: Overall, the idea in this paper is interesting and the paper is well-written and well-motivated.  However, I think it is not ready to publish in ICLR for the following reasons:

- This paper is not related to representation learning. It may be more suitable for a general machine learning or data mining conference. 

- The proposed approach can only work for a small class of models and cannot apply to popular formulations,  such as SVM, logistic regression, and neural network. It is unclear why we want to use SGD for this specific type of formulations. For model like linear regression, the authors should compare their methods with linear programming approaches. Also, it is unclear why we need to develope parallel algorithm for linear regressio problems as they are relatively easy to solve unless the data are big (see next comment). 

- The dataset used in the paper are relatively small and can be only used for proving the concept. Most datasets considered in the paper can be solved in a few second using a single core CPU. Hogwild! is suitable for sparse dataset because of its asynchronized nature. On data that are very sparse, the proposed approach is only slightly better or is worse than Hogwild. For dense dataset, it is unclear why we need to use SYMSGD instead of simply parallelizing the gradient computation using GPUs. Put them together, the experiment results are not convincing. 

review_title: null

final_score: rating: 4: Ok but not good enough - rejection
review_content: This paper propose a parallel mechanism for stochastic gradient descent method (SGD) in case of gradient can be computed via linear operations (including least square linear regression and polynomial regression problems). The motivation is to recover the same effect compared with sequential SGD, by using a proposed sound combiner. To make such combiner more efficient, the authors also use a randomized projection matrix to do dimension reduction. Experiments shows the proposed method has better speedup than previous methods like Hogwild! and Allreduce.

I feel that there might be some fundamental misunderstanding on SGD.

''The combiner matrixM  generate above can be quite large and expensive to compute. The sequential SGD algorithm maintains and updates the weight vector w , and thus requires O(f)  space and time, where f  is the number of features. In contrast,M  is a f f  matrix and consequently, the space and time complexity of parallel SGD is O(f^2) . In practice, this would mean that we would need O(f) processors to see constant speedups, an infeasible proposition particularly for datasets that can have
thousands if not millions of features."

I do not think one needs O(f^2) space and complexity for updating M_i * v, where v is an f-dimensional vector. Note that M_i is a low rank matrix in the form of (I - a_i a_i'). The complexity and space can be reduced to O(f) if compute it by O(v - a_i (a_i' v)) equivalently. If M_i is defined in the form of the product of n number of rank 1 matrices. The complexity and space complexity is O(fn). In the context of this paper, n should be much smaller than f. I seriously doubt that all author's assumptions, experiments, and strategies in this paper are based on this incorrect assumption on space and complexity of SGD. 

Why one can have speedup is unclear for me. It is unclear what computations are in parallel and why this sequential algorithms can bring speedup if M_i*v is computed in the most efficient way.
I suggest authors to make the following changes to make this paper more clear and theoretically solid
- provide computational complexity per step of the proposed algorithm
- convergence rate analysis (convergence analysis is not enough): we would like to see how the dimension reduction can affect the complexity.

review_title: Why we can have speedup is unclear

final_score: rating: null
review_content: "In parameter-server Li et al. (2014a), each thread (or machine) periodically sends its model deltas to a server that applies them to a global model. In ALLREDUCE Agarwal et al. (2014), threads periodically reach a barrier where they compute a weighted-average of the local models. Obviously, these approaches can produce a model that is potentially different from what a sequential SGD would have produced on these examples."

The convergence of asynchronous SGD has been theoretically proven. Why do you think it is "potentially different from" the sequential algorithm?
review_title: convergence of asynchronous parallel algorithms

final_score: rating: null
review_content: Specifically, it is unclear from the paper whether does the gradient calculation utilizes the sparsity of the dataset.
It would be helpful to give a detailed description on how gradient is calculated, and time complexity analysis, given  N X M a sparse input data, with only Z entries

review_title: How is sparse algorithm implemented

final_score: rating: 6: Marginally above acceptance threshold
review_content: This paper describes a correction technique to combine updates from multiple SGD to make it statistically equivalent to sequential technique.
Comments
1) The proposed method is novel and interesting to allow update to be corrected even when the update is delayed.
2) The proposed theory can only be applied to square loss setting (with linear update rule), making it somewhat limited. This paper would be much more interesting to ICLR community, if the technique is applicable to general objective function and settings of deep neural networks.
3) The resulting technique requires book-keeping of a dimensional reduced combiner matrix, which causes more computation in terms of complexity. The authors argue that the overhead can be canceled with SIMD support for symbolic update. However, the normal update of SGD might also benefit from SIMD, especially when the dataset is dense.

Overall, even though the practical value of this work is limited by 2) and 3), the technique(specifically the correction rule) proposed in the paper could be of interest to people scaling up learning. I would encourage the author to extend the method to the cases of non-linear objective function which could make it more interesting to the ICLR community



review_title: review for Parallel Stochastic Gradient Descent with Sound Combiner

Meta-review: The reviewers largely agree that this paper is well written and presents an interesting, novel approach to parallelizing Stochastic Gradient Descent. However, the current formulation is restricted to linear regression models and requires sketching techniques to handle large number of features, although it is striking that very aggressive sketching (k~10) still works well. In this setting though, there are specialized randomized solvers such as Blendenpick (Avron et al) which sketch the data upfront to construct a high quality pre-conditioner for use with iterative methods. 
 The authors are encouraged to either compare with state of the art parallel randomized least squares solvers developed in the numerical linear algebra community (see papers by Michael Mahoney, Petros Drineas and others), or broaden the scope of the proposed methods to include models of current interest (e.g., DNNs). The latter would of course be of specific interest to the ICLR community.
Decision: Reject