  In this paper we introduce a class of novel distributed algorithms for
solving stochastic big-data convex optimization problems over directed graphs.
In the addressed set-up, the dimension of the decision variable can be
extremely high and the objective function can be nonsmooth. The general
algorithm consists of two main steps: a consensus step and an update on a
single block of the optimization variable, which is then broadcast to
neighbors. Three special instances of the proposed method, involving particular
problem structures, are then presented. In the general case, the convergence of
a dynamic consensus algorithm over random row stochastic matrices is shown.
Then, the convergence of the proposed algorithm to the optimal cost is proven
in expected value. Exact convergence is achieved when using diminishing (local)
stepsizes, while approximate convergence is attained when constant stepsizes
are employed. The convergence rate is shown to be sublinear and an explicit
rate is provided in the case of constant stepsizes. Finally, the algorithm is
tested on a distributed classification problem, first on synthetic data and,
then, on a real, high-dimensional, text dataset.
