  We introduce a primal-dual stochastic gradient oracle method for distributed
convex optimization problems over networks. We show that the proposed method is
optimal in terms of communication steps. Additionally, we propose a new
analysis method for the rate of convergence in terms of duality gap and
probability of large deviations. This analysis is based on a new technique that
allows to bound the distance between the iteration sequence and the optimal
point. By the proper choice of batch size, we can guarantee that this distance
equals (up to a constant) to the distance between the starting point and the
solution.
