Stochastic Primal Dual Coordinate Method with Non-Uniform Sampling Based on Optimality Violations
This work addresses efficiency in stochastic optimization for machine learning practitioners, but it is incremental as it builds on existing primal-dual frameworks.
The authors tackled the problem of improving convergence speed in primal-dual stochastic optimization by proposing a non-uniform sampling method based on optimality violations, resulting in faster performance than state-of-the-art methods as demonstrated in numerical experiments.
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.