Reviews: Stochastic Primal-Dual Method for Empirical Risk Minimization with O(1) Per-Iteration Complexity

I have decided not to increase my grade since my criticism on intuition & readability and time plots really depends on the quality of the re-write and the plots. In the rebuttal the authors have suggested that their method can be deduced using a saddle point formulation and they will include time plots, which I look forward to seeing. But still, it depends on the re-write. Furthermore on why I feel I cannot raise my grade, as pointed out by Reviewer 1, an application where data access is truly the bottleneck (such as a distributed setting) would be very welcome and would result in an excellent and well rounded paper i.e. good theoretical results, and a good practical result. This is the first time I've seen a O(1) per iteration cost, and thus I find the paper quite interesting in the regime where loading data is truly the bottleneck. On the downside, very little intuition or any form of a derivation of the algorithms is offered, making the paper only suitable for experts in convex optimization and proximal methods.