Contents of Appendix

The above lemma is obtained by combining [ CGM19, Corollary 7] and VC-dimension bounds. We now prove the accuracy guarantee of Algorithm 1 . Here, we give the details of Algorithm 4 invoked in step 4 of Algorithm 2 . Note that the setup in Algorithm 2 is a special case of the above. Moreover, Algorithm 2 requires O ( m log ( m) log ( 1)) gradient computations.