  In this work we develop a new algorithm for regularized empirical risk
minimization. Our method extends recent techniques of Shalev-Shwartz [02/2015],
which enable a dual-free analysis of SDCA, to arbitrary mini-batching schemes.
Moreover, our method is able to better utilize the information in the data
defining the ERM problem. For convex loss functions, our complexity results
match those of QUARTZ, which is a primal-dual method also allowing for
arbitrary mini-batching schemes. The advantage of a dual-free analysis comes
from the fact that it guarantees convergence even for non-convex loss
functions, as long as the average loss is convex. We illustrate through
experiments the utility of being able to design arbitrary mini-batching
schemes.
