  We study primal-dual type stochastic optimization algorithms with non-uniform
sampling. Our main theoretical contribution in this paper is to present a
convergence analysis of Stochastic Primal Dual Coordinate (SPDC) Method with
arbitrary sampling. Based on this theoretical framework, we propose Optimality
Violation-based Sampling SPDC (ovsSPDC), a non-uniform sampling method based on
Optimality Violation. We also propose two efficient heuristic variants of
ovsSPDC called ovsSDPC+ and ovsSDPC++. Through intensive numerical experiments,
we demonstrate that the proposed method and its variants are faster than other
state-of-the-art primal-dual type stochastic optimization methods.
