  We develop stochastic first-order primal-dual algorithms to solve a class of
convex-concave saddle-point problems. When the saddle function is strongly
convex in the primal variable, we develop the first stochastic restart scheme
for this problem. When the gradient noises obey sub-Gaussian distributions, the
oracle complexity of our restart scheme is strictly better than any of the
existing methods, even in the deterministic case. Furthermore, for each problem
parameter of interest, whenever the lower bound exists, the oracle complexity
of our restart scheme is either optimal or nearly optimal (up to a log factor).
The subroutine used in this scheme is itself a new stochastic algorithm
developed for the problem where the saddle function is non-strongly convex in
the primal variable. This new algorithm, which is based on the primal-dual
hybrid gradient framework, achieves the state-of-the-art oracle complexity and
may be of independent interest.
