  In this paper, we present novel randomized algorithms for solving saddle
point problems whose dual feasible region is given by the direct product of
many convex sets. Our algorithms can achieve an ${\cal O}(1/N)$ and ${\cal
O}(1/N^2)$ rate of convergence, respectively, for general bilinear saddle point
and smooth bilinear saddle point problems based on a new prima-dual termination
criterion, and each iteration of these algorithms needs to solve only one
randomly selected dual subproblem. Moreover, these algorithms do not require
strongly convex assumptions on the objective function and/or the incorporation
of a strongly convex perturbation term. They do not necessarily require the
primal or dual feasible regions to be bounded or the estimation of the distance
from the initial point to the set of optimal solutions to be available either.
We show that when applied to linearly constrained problems, RPDs are equivalent
to certain randomized variants of the alternating direction method of
multipliers (ADMM), while a direct extension of ADMM does not necessarily
converge when the number of blocks exceeds two.
