A Randomized Block Subgradient Approach to Distributed Big Data Optimization

This paper introduces a novel distributed algorithm over static directed graphs for solving big data convex optimization problems in which the dimension of the decision variable can be extremely high and the objective function can be nonsmooth. In the proposed algorithm nodes in the network update and communicate only blocks of their current solution estimate rather than the entire vector. The algorithm consists of two main steps: a consensus step and a subgradient update on a single block of the optimization variable (which is then broadcast to neighbors). Agents are shown to asymptotically achieve consensus by studying a block-wise consensus protocol over random graphs. Then convergence to the optimal cost is proven in expected value by exploiting the consensus of agents estimates and randomness of the algorithm. Finally, as a numerical example, a distributed linear classification problem is solved by means of the proposed algorithm.