where we assume that the function \(f:^d \rightarrow \)  is smooth, convex, and potentially high dimensional. This problem commonly arises in empirical risk minimization [1]}.
State-of-the-art approaches for minimization of convex ERM objectives with large numbers of data points include variants of stochastic gradient descent (SGD) such as SVRG [2]}, SARAH [3]} and a plethora of others. Alternatively, one can approach the ERM problem via a dual formulation, where fast coordinate minimization techniques such as SDCA [4]}, or parallel coordinate descent [5]}, [6]} can be applied. This is especially desirable in distributed and parallel environments [7]}, [8]}, [9]}. These approaches are closely related to methods that subsample the Hessian [10]}, [11]}, [12]}.
