We thank the reviewers for their comments.$
Reviewer 1: 
Thank you for the positive feedback. Regarding your comment on Section 2.3, we relied on the more general framework of Lin, Mairal, Harchaoui. We will make this section more clear.

Reviewer 2 + 3: 
It seems your main concern is the lack of experimental results. SDCA is implemented in state-of-the-art packages for SVM and has been shown many times to produce excellent experimental results. The goal of this paper is to extend it and to interpret it as a variance reduced SGD. While it is true that experiments with non-convex or non-regularized problems would help, we thought that the theoretical contribution is the main point of this paper and numerical experiments would be a distraction. We hoped that the reviewers will appreciate the elegance and simplicity of the proofs, hence we preferred to use the budget of 9 pages for including the proofs of all claims, instead of "wasting" space on experiments.