Appendix

In Appendix B, we provide additional experiments supporting our claims. A.1 Proof of Lemma 3.1 We begin with Lemma 3.3 of [2], which gives 1 2 nullx We begin with equation eq. B.1 Condition Number of A is 1 Figure 6: Speed ups with best possible stepsizes vs. batch size (noisy experiments with σ = 0 . Figure 7: Speed up vs. stepsizes for l Figure 8: Speed up vs. stepsizes for logistic regression. Figure 13: Speed ups with best possible stepsizes vs. batch size (noisy experiments with σ = 0 .