  This paper examines a variety of classical optimization problems, including
well-known minimization tasks and more general variational inequalities. We
consider a stochastic formulation of these problems, and unlike most previous
work, we take into account the complex Markov nature of the noise. We also
consider the geometry of the problem in an arbitrary non-Euclidean setting, and
propose four methods based on the Mirror Descent iteration technique.
Theoretical analysis is provided for smooth and convex minimization problems
and variational inequalities with Lipschitz and monotone operators. The
convergence guarantees obtained are optimal for first-order stochastic methods,
as evidenced by the lower bound estimates provided in this paper.
