  One of the most attractive recent approaches to processing well-structured
large-scale convex optimization problems is based on smooth convex-concave
saddle point reformu-lation of the problem of interest and solving the
resulting problem by a fast First Order saddle point method utilizing
smoothness of the saddle point cost function. In this paper, we demonstrate
that when the saddle point cost function is polynomial, the precise gra-dients
of the cost function required by deterministic First Order saddle point
algorithms and becoming prohibitively computationally expensive in the
extremely large-scale case, can be replaced with incomparably cheaper
computationally unbiased random estimates of the gradients. We show that for
large-scale problems with favourable geometry, this randomization accelerates,
progressively as the sizes of the problem grow, the solution process. This
extends significantly previous results on acceleration by randomization, which,
to the best of our knowledge, dealt solely with bilinear saddle point problems.
We illustrate our theoretical findings by instructive and encouraging numerical
experiments.
