Although there is still room for improvement (e.g., it's unclear that the dependence on the symmetry of the gradient distribution is fundamental), overall the reviewers agreed that this paper is interesting, well-written, and provides interesting new insights into an important set of algorithms.